2026-09-21T04:53:28Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/24076 2023-07-10 col_2142_16340 col_2142_5131 com_2142_16339 com_2142_8903 com_2142_5130

Balogh, József West, Douglas B. Balogh, József Kostochka, Alexandr V. Furedi, Zoltan Lenz, John E. 2011-05-25T14:50:19Z 2011-05-25T14:50:19Z 2011-05-25T14:50:19Z 2011-05 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. Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-04-19T14:01:30Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Lenz_John.pdf: 711479 bytes, checksum: 820469361595f9cfaca3764034494144 (MD5) Made available in DSpace on 2011-05-25T14:50:19Z (GMT). No. of bitstreams: 2 Lenz_John.pdf: 711479 bytes, checksum: 820469361595f9cfaca3764034494144 (MD5) license.txt: 4057 bytes, checksum: 524a96613b8e7c4002c63f110bb3dd0d (MD5) http://hdl.handle.net/2142/24076 en Copyright 2011 John E. Lenz Extremal Graph Theory Turan's Theorem Minors Extremal graph theory: Ramsey-Turán numbers, chromatic thresholds, and minors Mathematics 1257 Mathematics 0439 University of Illinois at Urbana-Champaign Dissertation Ph.D. PHD:Mathematics -UIUC 10KS0439PHD