2026-09-20T18:52:36Z https://www.ideals.illinois.edu/oai-pmh

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

Balogh, József Kostochka, Alexandr V. Balogh, József West, Douglas B. Lidicky, Bernard Butterfield, Jane 2012-09-18T21:11:13Z 2012-09-18T21:11:13Z 2012-08 2012-09-18T21:11:13Z 2012-08 We study problems in extremal combinatorics with respect to forbidden induced subgraphs, forbidden colored subgraphs, and forbidden subgraphs. In Chapter 2, we determine exactly which graphs H have the property that almost every H-free graph has a vertex partition into k cliques and independent sets and provide a characterization. Such graphs contain homogeneous sets of size linear in the number of vertices, and so this result provides a strong partial result toward proving the Erdos-Hajnal conjecture. In Chapter 3, we study a Ramsey-type game in an online and random setting. The player must color edges of K_n in an order chosen uniformly at random, and loses when she has created a monochromatic triangle. We provide upper bounds on the threshold for the number of edges the player is almost surely able to paint before losing in the k-color game. When k > 2, these upper bounds provide the first separation from the online threshold. In Chapter 4, we consider the family of 3-uniform hypergraphs that do not contain a copy of F_5, sometimes called the generalized triangle. We extend known extremal results to the sparse random setting, proving that with probability tending to 1 the largest subgraph of the random 3-uniform hypergraph that does not contain F_5 is tripartite. Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-07-06T19:38:09Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Butterfield_Jane.pdf: 602646 bytes, checksum: f1612ece7e2be057a2e2c6db56ae9841 (MD5) Made available in DSpace on 2012-09-18T21:11:13Z (GMT). No. of bitstreams: 2 Butterfield_Jane.pdf: 602646 bytes, checksum: f1612ece7e2be057a2e2c6db56ae9841 (MD5) license.txt: 4066 bytes, checksum: 7d2abce2d202f25c5b3733c122749966 (MD5) http://hdl.handle.net/2142/34320 en Copyright 2012 Jane Butterfield induced subgraph Ramsey theory extremal combinatorics Forbidden substructures: induced subgraphs, Ramsey games, and sparse hypergraphs Mathematics 1257 Mathematics 0439 University of Illinois at Urbana-Champaign Dissertation Ph.D. PHD:Mathematics -UIUC 10KS0439PHD