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

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2012

Author dc:creator

• Butterfield, Jane

Contributors dc:contributor

• Balogh, József
• Kostochka, Alexandr V.
• West, Douglas B.
• Lidicky, Bernard

• induced subgraph
• Ramsey theory
• extremal combinatorics

Statement dc:rights

• Copyright 2012 Jane Butterfield

Language dc:language

en

Handle dc:identifier

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

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/34320