Extremal graph theory: Ramsey-Turán numbers, chromatic thresholds, and minors

Extremal Graph Theory;"Turans Theorem";Minors

Lenz, John E.

关键词: Extremal Graph Theory;    "Turans Theorem";    Minors;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/24076/Lenz_John.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

This dissertation investigates several questions in extremal graph theory and thetheory of graph minors.It consists of three independent parts; the first two parts focuson questions motivated by Turan's Theorem and the third part investigatesa problem related to Hadwiger's Conjecture.Let H be a graph, t an integer, and f(n) a function.The t-Ramsey-Turan number of H, RT_t(n,H,f(n)), is the maximum numberof edges in an n-vertex, H-free graph with K_t-independence number less than f(n), where the K_t-independence number of a graph G is the maximum number of vertices in a K_t-free induced graph of G.In the first part of this thesis, we studythe Ramsey-Turan numbers for several graphs and hypergraphs, proving two conjecturesof Erdos, Hajnal, Simonovits, Sos, and Szemeredi.In joint work with JozsefBalogh, our first main theorem is to provide the first lower bounds of order \Omega(n^2) on RT_t(n,K_{t+2},o(n)).Our second main theorem is to prove lower bounds onRT(n,\tk{r}{s},o(n)), where \tk{r}{s} is the r-uniform hypergraph formed from K_sby adding r-2 new vertices to every edge.Let \mathcal{F} be a family of r-uniform hypergraphs.Introduced by Erdos and Simonovits, the chromatic threshold of \mathcal{F} is the infimum of the values c >= 0such that the subfamily of \mathcal{F} consisting of hypergraphs with minimum degreeat least $c\binom{n}{r-1}$ has bounded chromatic number.The problem of chromatic thresholds of graphs has beenwell studied, but there have been no previous results about the chromatic thresholds of r-uniformhypergraphs for r >= 3.Our main result in this part of the thesis, in joint work with Jozsef Balogh,Jane Butterfield, Ping Hu, and Dhruv Mubayi, is to prove a structural theorem about hypergraphswith bounded chromatic number.Corollaries of this result show thatthe chromatic threshold of the family of F-free hypergraphs is zero for several hypergraphs F,including a hypergraph generalization of cycles.A graph H is a minor of a graph G if starting with G, one can obtain H by a sequenceof vertex deletions, edge deletions, and edge contractions.Hadwiger's famous conjecturefrom 1943 states that every t-chromatic graph G has K_t as a minor.Hadwiger's Conjectureimplies the following weaker conjecture: every graph G has $K_{\left\lceil n/\alpha(G) \right\rceil}$ as a minor, where \alpha(G) is the independence numberof G.The main theorem in the last part of this thesis, in joint work with Jozsef Balogh and Hehui Wu, is to prove that every graph has$K_{n/(2\alpha(G) - \Theta(\log \alpha(G)))}$ as a minor.