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

Butterfield, Jane

Advanced Search

Search IDEALS This Collection

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
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