{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/110495"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/110495","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Ramsey theory: The Erdős-Gyárfás problem and ordered size Ramsey questions","abstract":"DSpace SAF Submission Ingestion Package generated from Vireo submission #16387 on 2021-09-16 at 16:42:26","abstract_html":"DSpace SAF Submission Ingestion Package generated from Vireo submission #16387 on 2021-09-16 at 16:42:26","abstract_has_math":false,"creators":["Heath, Emily"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Balogh, József","Kostochka, Alexandr","Ford, Kevin","English, Sean"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-09-17T01:11:01Z","date_published":"2021-09-17T01:11:01Z","updated_at":"2026-07-22T22:24:50Z","subjects":["graph theory","extremal combinatorics","Ramsey number","ordered graphs","paths"],"languages":["en"],"rights":["Copyright 2021 Emily Heath"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/110495","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Balogh, József","Kostochka, Alexandr","Ford, Kevin","English, Sean"]},{"key":"dc:creator","label":"Author","values":["Heath, Emily"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2021-09-17T01:11:01Z","2021-04-19","2021-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["graph theory","extremal combinatorics","Ramsey number","ordered graphs","paths"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2021 Emily Heath"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/110495"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["DSpace SAF Submission Ingestion Package generated from Vireo submission #16387 on 2021-09-16 at 16:42:26","Made available in DSpace on 2021-09-17T01:11:01Z (GMT). No. of bitstreams: 8 HEATH-DISSERTATION-2021.pdf: 627179 bytes, checksum: a88d8e50ccf0cffa5a8bf0dc2ee441d3 (MD5) main.tex: 226989 bytes, checksum: 5fbe54c7c467d800f10d3a5b6907bcf7 (MD5) thesisbib.bib: 17813 bytes, checksum: 1ffaaa31107b131c25e229979e2d7720 (MD5) uiucthesis2014.cls: 17010 bytes, checksum: cf854ccf88a513db922dfe38a16c6cef (MD5) uiucthesis2014.dtx: 63348 bytes, checksum: c3f1a9f0b4c72650d0e09b8ed905b50e (MD5) uiucthesis2014.sty: 16899 bytes, checksum: 2fdf059ac3f5686499bd52dba2590f10 (MD5) LICENSE.txt: 4208 bytes, checksum: c76cb24c250cbd04155236ceacc93f28 (MD5) PROQUEST_LICENSE.txt: 4554 bytes, checksum: e8b27784600c725a211071378d9e9708 (MD5) Previous issue date: 2021-04-19","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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2021-09-16 without embargo terms","The student, Emily Heath, accepted the attached license on 2021-04-17 at 18:01.","The student, Emily Heath, submitted this Dissertation for approval on 2021-04-17 at 18:28.","This Dissertation was approved for publication on 2021-04-19 at 16:21."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Ramsey theory: The Erdős-Gyárfás problem and ordered size Ramsey questions"]}]}],"canonical_facts":{"dc:contributor":["Balogh, József","Kostochka, Alexandr","Ford, Kevin","English, Sean"],"dc:creator":["Heath, Emily"],"dc:date":["2021-09-17T01:11:01Z","2021-04-19","2021-05"],"dc:description":["DSpace SAF Submission Ingestion Package generated from Vireo submission #16387 on 2021-09-16 at 16:42:26","Made available in DSpace on 2021-09-17T01:11:01Z (GMT). No. of bitstreams: 8 HEATH-DISSERTATION-2021.pdf: 627179 bytes, checksum: a88d8e50ccf0cffa5a8bf0dc2ee441d3 (MD5) main.tex: 226989 bytes, checksum: 5fbe54c7c467d800f10d3a5b6907bcf7 (MD5) thesisbib.bib: 17813 bytes, checksum: 1ffaaa31107b131c25e229979e2d7720 (MD5) uiucthesis2014.cls: 17010 bytes, checksum: cf854ccf88a513db922dfe38a16c6cef (MD5) uiucthesis2014.dtx: 63348 bytes, checksum: c3f1a9f0b4c72650d0e09b8ed905b50e (MD5) uiucthesis2014.sty: 16899 bytes, checksum: 2fdf059ac3f5686499bd52dba2590f10 (MD5) LICENSE.txt: 4208 bytes, checksum: c76cb24c250cbd04155236ceacc93f28 (MD5) PROQUEST_LICENSE.txt: 4554 bytes, checksum: e8b27784600c725a211071378d9e9708 (MD5) Previous issue date: 2021-04-19","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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2021-09-16 without embargo terms","The student, Emily Heath, accepted the attached license on 2021-04-17 at 18:01.","The student, Emily Heath, submitted this Dissertation for approval on 2021-04-17 at 18:28.","This Dissertation was approved for publication on 2021-04-19 at 16:21."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/110495"],"dc:language":["en"],"dc:rights":["Copyright 2021 Emily Heath"],"dc:subject":["graph theory","extremal combinatorics","Ramsey number","ordered graphs","paths"],"dc:title":["Ramsey theory: The Erdős-Gyárfás problem and ordered size Ramsey questions"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:50Z"}