Files in this item
Files | Description | Format |
---|---|---|
application/pdf ![]() | (no description provided) |
Description
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)
-
Dissertations and Theses - Mathematics
-
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois