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

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2021

Author dc:creator

• Heath, Emily

Contributors dc:contributor

• Balogh, József
• Kostochka, Alexandr
• Ford, Kevin
• English, Sean

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

Statement dc:rights

• Copyright 2021 Emily Heath

Language dc:language

en

Handle dc:identifier

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

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F110495