Forbidden substructures: induced subgraphs, Ramsey games, and sparse hypergraphs

induced subgraph;Ramsey theory;extremal combinatorics

Butterfield, Jane

关键词: induced subgraph;    Ramsey theory;    extremal combinatorics;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/34320/Butterfield_Jane.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

We study problems in extremal combinatorics with respect to forbidden induced subgraphs,forbidden colored subgraphs, and forbidden subgraphs. In Chapter 2, we determine exactlywhich graphs H have the property that almost every H-free graph has a vertex partitioninto 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 thefirst separation from the online threshold.In Chapter 4, we consider the family of 3-uniform hypergraphs that do not contain acopy of F_5, sometimes called the generalized triangle. We extend known extremal results tothe sparse random setting, proving that with probability tending to 1 the largest subgraphof the random 3-uniform hypergraph that does not contain F_5 is tripartite.