서브메뉴
검색
Induced Subgraph Density
Induced Subgraph Density
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20260202103510
- ISBN
- 9798280747845
- DDC
- 510
- 서명/저자
- Induced Subgraph Density
- 발행사항
- [Sl] : Princeton University, 2025
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2025
- 형태사항
- 276 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 86-12, Section: B.
- 주기사항
- Advisor: Seymour, Paul.
- 학위논문주기
- Thesis (Ph.D.)--Princeton University, 2025.
- 초록/해제
- 요약This thesis develops ideas and techniques from extremal, probabilistic, and structural graph theory to investigate the edge distribution of graphs with forbidden induced subgraphs. The thesis' main focus is the Erdos--Hajnal conjecture from 1977 that says for every graph H there exists c0 such that every n-vertex graph with no induced copy of H has a clique or stable set of size at least nc. Partial results on the conjecture presented (all joint with Alex Scott and Paul Seymour) include:a log log improvement over the general bound 2c√ log n of Erdos--Hajnal from 1977 (also joint with Matija Bucic);a proof of the conjecture when H is the five-vertex path, which was the last open case of the problem of proving the conjecture for every $H$ with five vertices (first posed by Gyarfas in 1997);a proof of the conjecture in the setting of graphs of bounded VC-dimension, which was posed independently by Chernikov, Starchenko, and Thomas and by Fox, Pach, and Suk;a proof of the conjecture for infinitely many prime graphs H, which was asked by Chudnovsky in 2014;a proof of the bound 2(log n)1-o(1) when H is an arbitrary path; and a proof of the conjecture for excluding a hole and an antihole, and for excluding an arbitrary induced (≥4)-subdivision of H and its complement.The ideas developed in the thesis are also adapted to give applications in the area of χ-boundedness which studies the induced subgraphs of graphs with chromatic number much larger than clique number.These include an approximation of the Gyarfas--Sumner conjecture (joint with Alex Scott and Paul Seymour);a proof that graphs with bounded clique number and no induced subdivision of any given graph have polylogarithmic chromatic number (joint with Alex Scott and Paul Seymour), which extends a result of Fox and Pach on the chromatic number of string graphs;several new instances for which the polynomial Gyarfas--Sumner conjecture holds;and a log log improvement over the χ-binding function ωlogω of graphs with no induced five-vertex path proved by Scott, Seymour, and Spirkl.
- 일반주제명
- Mathematics
- 일반주제명
- Theoretical mathematics
- 키워드
- Subgraph density
- 키워드
- Graph coloring
- 기타저자
- Princeton University Applied and Computational Mathematics
- 기본자료저록
- Dissertations Abstracts International. 86-12B.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008260126s2025 us c eng d■001000017357430
■00520260202103510
■006m o d
■007cr#unu||||||||
■020 ▼a9798280747845
■035 ▼a(MiAaPQ)AAI32003298
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a510
■1001 ▼aNguyen, Huy Tung.
■24510▼aInduced Subgraph Density
■260 ▼a[Sl]▼bPrinceton University▼c2025
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2025
■300 ▼a276 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 86-12, Section: B.
■500 ▼aAdvisor: Seymour, Paul.
■5021 ▼aThesis (Ph.D.)--Princeton University, 2025.
■520 ▼aThis thesis develops ideas and techniques from extremal, probabilistic, and structural graph theory to investigate the edge distribution of graphs with forbidden induced subgraphs. The thesis' main focus is the Erdos--Hajnal conjecture from 1977 that says for every graph H there exists c0 such that every n-vertex graph with no induced copy of H has a clique or stable set of size at least nc. Partial results on the conjecture presented (all joint with Alex Scott and Paul Seymour) include:a log log improvement over the general bound 2c√ log n of Erdos--Hajnal from 1977 (also joint with Matija Bucic);a proof of the conjecture when H is the five-vertex path, which was the last open case of the problem of proving the conjecture for every $H$ with five vertices (first posed by Gyarfas in 1997);a proof of the conjecture in the setting of graphs of bounded VC-dimension, which was posed independently by Chernikov, Starchenko, and Thomas and by Fox, Pach, and Suk;a proof of the conjecture for infinitely many prime graphs H, which was asked by Chudnovsky in 2014;a proof of the bound 2(log n)1-o(1) when H is an arbitrary path; and a proof of the conjecture for excluding a hole and an antihole, and for excluding an arbitrary induced (≥4)-subdivision of H and its complement.The ideas developed in the thesis are also adapted to give applications in the area of χ-boundedness which studies the induced subgraphs of graphs with chromatic number much larger than clique number.These include an approximation of the Gyarfas--Sumner conjecture (joint with Alex Scott and Paul Seymour);a proof that graphs with bounded clique number and no induced subdivision of any given graph have polylogarithmic chromatic number (joint with Alex Scott and Paul Seymour), which extends a result of Fox and Pach on the chromatic number of string graphs;several new instances for which the polynomial Gyarfas--Sumner conjecture holds;and a log log improvement over the χ-binding function ωlogω of graphs with no induced five-vertex path proved by Scott, Seymour, and Spirkl.
■590 ▼aSchool code: 0181.
■650 4▼aMathematics
■650 4▼aTheoretical mathematics
■653 ▼aSubgraph density
■653 ▼aErdos-Hajnal conjecture
■653 ▼aGraph coloring
■690 ▼a0405
■690 ▼a0642
■71020▼aPrinceton University▼bApplied and Computational Mathematics.
■7730 ▼tDissertations Abstracts International▼g86-12B.
■790 ▼a0181
■791 ▼aPh.D.
■792 ▼a2025
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17357430▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
