You are here
Two Ramseyrelated Problems
 Date Issued:
 2019
 Abstract/Description:
 Extremal combinatorics is one of the central branches of discrete mathematics and has experienced an impressive growth during the last few decades. It deals with the problem of determining or estimating the maximum or minimum possible size of a combinatorial structure which satisfies certain requirements. In this dissertation, we focus on studying the minimum number of edges of certain cocritical graphs. Given an integer r \geq 1 and graphs G, H_1, . . . , H_r, we write G \rightarrow (H_1, . . . , H_r) if every rcoloring of the edges of G contains a monochromatic copy of H_i in color i for some i \in {1, . . . , r}. A graph G is (H_1, . . . , H_r)cocritical if G \nrightarrow (H_1, . . . , H_r), but G+uv \rightarrow (H_1, . . . , H_r) for every pair of nonadjacent vertices u, v in G. Motivated in part by Hanson and Toft's conjecture from 1987, we study the minimum number of edges over all (K_t,\mathcal{T}_k)cocritical graphs on n vertices, where \mathcal{T}_k denotes the family of all trees on k vertices. We apply graph bootstrap percolation on a not necessarily K_tsaturated graph to prove that for all t \geq 4 and k \geq max{6, t}, there exists a constant c(t,k) such that, for all n \geq (t1)(k1)+1, if G is a (K_t,\mathcal{T}_k)cocritical graph on n vertices, then e(G) \geq ((4t9)/2+\lceil k/2 \rceil /2)nc(t,k). We then show that this is asymptotically best possible for all sufficiently large n when t \in {4, 5} and k \geq 6. The method we developed may shed some light on solving Hanson and Toft's conjecture, which is wide open.We also study Ramsey numbers of even cycles and paths under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles, and a Gallai kcoloring is a Gallai coloring that uses at most k colors. Given an integer k \geq 1 and graphs H_1, . . . , H_k, the GallaiRamsey number GR(H_1, . . . , H_k) is the least integer n such that every Gallai kcoloring of the complete graph K_n contains a monochromatic copy of H_i in color i for some i \in {1, . . . , k}. We completely determine the exact values of GR(H_1, . . . , H_k) for all k \geq 2 when each H_i is a path or an even cycle on at most 13 vertices.
Title:  Two Ramseyrelated Problems. 
27 views
13 downloads 

Name(s): 
Zhang, Jingmei, Author Song, Zixia, Committee Chair Zhao, Yue, Committee Member Martin, Heath, Committee Member Turgut, Damla, Committee Member University of Central Florida, Degree Grantor 

Type of Resource:  text  
Date Issued:  2019  
Publisher:  University of Central Florida  
Language(s):  English  
Abstract/Description:  Extremal combinatorics is one of the central branches of discrete mathematics and has experienced an impressive growth during the last few decades. It deals with the problem of determining or estimating the maximum or minimum possible size of a combinatorial structure which satisfies certain requirements. In this dissertation, we focus on studying the minimum number of edges of certain cocritical graphs. Given an integer r \geq 1 and graphs G, H_1, . . . , H_r, we write G \rightarrow (H_1, . . . , H_r) if every rcoloring of the edges of G contains a monochromatic copy of H_i in color i for some i \in {1, . . . , r}. A graph G is (H_1, . . . , H_r)cocritical if G \nrightarrow (H_1, . . . , H_r), but G+uv \rightarrow (H_1, . . . , H_r) for every pair of nonadjacent vertices u, v in G. Motivated in part by Hanson and Toft's conjecture from 1987, we study the minimum number of edges over all (K_t,\mathcal{T}_k)cocritical graphs on n vertices, where \mathcal{T}_k denotes the family of all trees on k vertices. We apply graph bootstrap percolation on a not necessarily K_tsaturated graph to prove that for all t \geq 4 and k \geq max{6, t}, there exists a constant c(t,k) such that, for all n \geq (t1)(k1)+1, if G is a (K_t,\mathcal{T}_k)cocritical graph on n vertices, then e(G) \geq ((4t9)/2+\lceil k/2 \rceil /2)nc(t,k). We then show that this is asymptotically best possible for all sufficiently large n when t \in {4, 5} and k \geq 6. The method we developed may shed some light on solving Hanson and Toft's conjecture, which is wide open.We also study Ramsey numbers of even cycles and paths under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles, and a Gallai kcoloring is a Gallai coloring that uses at most k colors. Given an integer k \geq 1 and graphs H_1, . . . , H_k, the GallaiRamsey number GR(H_1, . . . , H_k) is the least integer n such that every Gallai kcoloring of the complete graph K_n contains a monochromatic copy of H_i in color i for some i \in {1, . . . , k}. We completely determine the exact values of GR(H_1, . . . , H_k) for all k \geq 2 when each H_i is a path or an even cycle on at most 13 vertices.  
Identifier:  CFE0007745 (IID), ucf:52404 (fedora)  
Note(s): 
20190801 Ph.D. Sciences, Mathematics Doctoral This record was generated from author submitted information. 

Subject(s):  cocritical graphs  saturation number  Ramseyminimal  Gallai coloring  GallaiRamsey number  rainbow triangle  
Persistent Link to This Record:  http://purl.flvc.org/ucf/fd/CFE0007745  
Restrictions on Access:  public 20190815  
Host Institution:  UCF 