Files in this item



application/pdfButterfield_Jane.pdf (603kB)
(no description provided)PDF


Title:Forbidden substructures: induced subgraphs, Ramsey games, and sparse hypergraphs
Author(s):Butterfield, Jane
Director of Research:Balogh, József
Doctoral Committee Chair(s):Kostochka, Alexandr V.
Doctoral Committee Member(s):Balogh, József; West, Douglas B.; Lidicky, Bernard
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):induced subgraph
Ramsey theory
extremal combinatorics
Abstract: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.
Issue Date:2012-09-18
Rights Information:Copyright 2012 Jane Butterfield
Date Available in IDEALS:2012-09-18
Date Deposited:2012-08

This item appears in the following Collection(s)

Item Statistics