IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

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

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/34320

Files in this item

File Description Format
PDF Butterfield_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
Discipline: Mathematics
Degree Granting Institution: University of Illinois at Urbana-Champaign
Degree: Ph.D.
Genre: Dissertation
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
URI: http://hdl.handle.net/2142/34320
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)

Show full item record

Item Statistics

  • Total Downloads: 110
  • Downloads this Month: 4
  • Downloads Today: 0

Browse

My Account

Information

Access Key