Files in this item
Files  Description  Format 

application/pdf HEATHDISSERTATION2021.pdf (627kB)  (no description provided) 
Description
Title:  Ramsey theory: The ErdősGyárfás problem and ordered size Ramsey questions 
Author(s):  Heath, Emily 
Director of Research:  Balogh, József 
Doctoral Committee Chair(s):  Kostochka, Alexandr 
Doctoral Committee Member(s):  Ford, Kevin; English, Sean 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(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 socalled 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 wellknown ErdősSzekeres Theorem, which states that every redblue 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ősSzekeres Theorem by characterizing the ordered graphs on n^2+1 vertices for which any redblue edgecoloring 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. 
Issue Date:  20210419 
Type:  Thesis 
URI:  http://hdl.handle.net/2142/110495 
Rights Information:  Copyright 2021 Emily Heath 
Date Available in IDEALS:  20210917 
Date Deposited:  202105 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois