Ramsey theory: The Erdős-Gyárfás problem and ordered size Ramsey questions

Heath, Emily

Permalink

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

Description

Title

Ramsey theory: The Erdős-Gyárfás problem and ordered size Ramsey questions

Author(s)

Heath, Emily

Issue Date

2021-04-19

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

Balogh, József

Doctoral Committee Chair(s)

Kostochka, Alexandr

Committee Member(s)

• Ford, Kevin
• English, Sean

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• graph theory
• extremal combinatorics
• Ramsey number
• ordered graphs
• paths

Abstract

In this thesis, we study several variations of the following fundamental problem in Ramsey theory: Given a graph G, what is the minimum order n of a complete graph K_n with the property that every coloring of its edges with red and blue contains a monochromatic copy of G? First, we consider a generalization of this question which asks, given integers n, p, and q, how many colors are needed to color the edges of the complete graph on n vertices so that each clique with p vertices receives at least q colors. This so-called generalized Ramsey number f(n,p,q) was first studied systematically by Erdős and Gyárfás, who used a probabilistic argument to give an upper bound for all p and q. Until very recently, this original bound had been improved in the case where p=q only for p in {3,4,5}. In Chapter 2 and in joint work with Cameron, we build on earlier results of Mubayi and Conlon, Fox, Lee, and Sudakov to construct colorings that improve the upper bound when p=q for several other small values of p. In Chapter 3, together with Balogh, English, and Krueger, we prove new lower bounds on f(n,p,q) for several families of (p,q) by further developing the color energy technique of Fish, Pohoata, and Sheffer. Next, we consider variants of the Ramsey problem in the setting of ordered graphs, which are simple graphs with a total ordering on their vertices. This work, joint with Balogh, Clemen, and Lavrov, is motivated by the well-known Erdős-Szekeres Theorem, which states that every red-blue coloring of the edges of the ordered complete graph on n^2+1 vertices must contain a monochromatic increasing path with at least n edges. In Chapter 4, we study the size Ramsey version of this problem, considering the minimum number of edges rather than vertices needed in an ordered graph with this Ramsey property. Our main innovation is the use of inhomogeneous random graphs to give an upper bound on the ordered size Ramsey number of the ordered path which matches our lower bound up to a polylogarithmic factor. In Chapter 5, we strengthen the Erdős-Szekeres Theorem by characterizing the ordered graphs on n^2+1 vertices for which any red-blue edge-coloring contains a monochromatic ordered path, showing that these graphs all contain the same minimal substructure. Finally, using similar methods, we give improved bounds on an online version of the ordered size Ramsey problem for ordered paths.

Graduation Semester

2021-05

Type of Resource

Thesis

Permalink

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

Copyright and License Information

Copyright 2021 Emily Heath

Owning Collections