Files in this item
Files  Description  Format 

application/pdf Lenz_John.pdf (711kB)  (no description provided) 
Description
Title:  Extremal graph theory: RamseyTurá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 UrbanaChampaign 
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 tRamseyTuran number of H, RT_t(n,H,f(n)), is the maximum number of edges in an nvertex, Hfree graph with K_tindependence number less than f(n), where the K_tindependence number of a graph G is the maximum number of vertices in a K_tfree induced graph of G. In the first part of this thesis, we study the RamseyTuran 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 runiform hypergraph formed from K_s by adding r2 new vertices to every edge. Let \mathcal{F} be a family of runiform 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}{r1}$ 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 runiform 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 Ffree 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 tchromatic 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:  20110525 
URI:  http://hdl.handle.net/2142/24076 
Rights Information:  Copyright 2011 John E. Lenz 
Date Available in IDEALS:  20110525 
Date Deposited:  201105 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois