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

Butterfield, Jane

Permalink

https://hdl.handle.net/2142/34320 Copy

Description

Title

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

Author(s)

Butterfield, Jane

Issue Date

2012-09-18T21:11:13Z

Director of Research (if dissertation) or Advisor (if thesis)

Balogh, József

Doctoral Committee Chair(s)

Kostochka, Alexandr V.

Committee Member(s)

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

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(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.

Graduation Semester

2012-08

Permalink

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

Copyright and License Information

Copyright 2012 Jane Butterfield

Owning Collections