IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

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

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/24076

Files in this item

File Description Format
PDF Lenz_John.pdf (711KB) (no description provided) PDF
Title: Extremal graph theory: Ramsey-Turán numbers, chromatic thresholds, and minors
Author(s): Lenz, John E.
Director of Research: Balogh, József
Doctoral Committee Chair(s): West, Douglas B.
Doctoral Committee Member(s): Balogh, József; Kostochka, Alexandr V.; Furedi, Zoltan
Department / Program: Mathematics
Discipline: Mathematics
Degree Granting Institution: University of Illinois at Urbana-Champaign
Degree: Ph.D.
Genre: Dissertation
Subject(s): Extremal Graph Theory Turan's Theorem Minors
Abstract: 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/\alpha(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\alpha(G) - \Theta(\log \alpha(G)))}$ as a minor.
Issue Date: 2011-05-25
URI: http://hdl.handle.net/2142/24076
Rights Information: Copyright 2011 John E. Lenz
Date Available in IDEALS: 2011-05-25
Date Deposited: 2011-05
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 310
  • Downloads this Month: 6
  • Downloads Today: 0

Browse

My Account

Information

Access Key