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

This dissertation investigates several questions in extremal graph theory and the theory of graph minors. It consists of three independent parts; the first two parts focus on questions motivated by Turan's Theorem and the third part investigates a 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 number of 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 study the Ramsey-Turan numbers for several graphs and hypergraphs, proving two conjectures of Erdos, Hajnal, Simonovits, Sos, and Szemeredi. In joint work with Jozsef Balogh, 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 on RT(n,\tk{r}{s},o(n)), where \tk{r}{s} is the r-uniform hypergraph formed from K_s by 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 >= 0 such that the subfamily of \mathcal{F} consisting of hypergraphs with minimum degree at least $c\binom{n}{r-1}$ has bounded chromatic number. The problem of chromatic thresholds of graphs has been well studied, but there have been no previous results about the chromatic thresholds of r-uniform hypergraphs 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 hypergraphs with bounded chromatic number. Corollaries of this result show that the 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 sequence of vertex deletions, edge deletions, and edge contractions. Hadwiger's famous conjecture from 1943 states that every t-chromatic graph G has K_t as a minor. Hadwiger's Conjecture implies the following weaker conjecture: every graph G has K_{\left\lceil n/α(G) \right\rceil} as a minor, where \alpha(G) is the independence number of 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α(G) - \Theta(\log α(G)))} as a minor.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Lenz, John E.

Contributors dc:contributor

• Balogh, József
• West, Douglas B.
• Kostochka, Alexandr V.
• Furedi, Zoltan

• Extremal Graph Theory
• Turan's Theorem
• Minors

Statement dc:rights

• Copyright 2011 John E. Lenz

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/24076

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/24076