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

Lenz, John E.

Permalink

https://hdl.handle.net/2142/24076 Copy

Description

Title

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

Author(s)

Lenz, John E.

Issue Date

2011-05-25T14:50:19Z

Director of Research (if dissertation) or Advisor (if thesis)

Balogh, József

Doctoral Committee Chair(s)

West, Douglas B.

Committee Member(s)

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

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(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.

Graduation Semester

2011-05

Permalink

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

Copyright and License Information

Copyright 2011 John E. Lenz

Owning Collections