Two Ramsey-related 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 co-critical graphs. Given an integer r \geq 1 and graphs G, H_1, . . . , H_r, we write G \rightarrow (H_1, . . . , H_r) if every r-coloring 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)-co-critical if G \nrightarrow (H_1, . . . , H_r), but G+uv \rightarrow (H_1, . . . , H_r) for every pair of non-adjacent 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)-co-critical 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_t-saturated 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 (t-1)(k-1)+1, if G is a (K_t,\mathcal{T}_k)-co-critical graph on n vertices, then e(G) \geq ((4t-9)/2+\lceil k/2 \rceil /2)n-c(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 k-coloring is a Gallai coloring that uses at most k colors. Given an integer k \geq 1 and graphs H_1, . . . , H_k, the Gallai-Ramsey number GR(H_1, . . . , H_k) is the least integer n such that every Gallai k-coloring 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 Ramsey-related Problems.	45 views 23 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 co-critical graphs. Given an integer r \geq 1 and graphs G, H_1, . . . , H_r, we write G \rightarrow (H_1, . . . , H_r) if every r-coloring 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)-co-critical if G \nrightarrow (H_1, . . . , H_r), but G+uv \rightarrow (H_1, . . . , H_r) for every pair of non-adjacent 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)-co-critical 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_t-saturated 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 (t-1)(k-1)+1, if G is a (K_t,\mathcal{T}_k)-co-critical graph on n vertices, then e(G) \geq ((4t-9)/2+\lceil k/2 \rceil /2)n-c(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 k-coloring is a Gallai coloring that uses at most k colors. Given an integer k \geq 1 and graphs H_1, . . . , H_k, the Gallai-Ramsey number GR(H_1, . . . , H_k) is the least integer n such that every Gallai k-coloring 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):	2019-08-01 Ph.D. Sciences, Mathematics Doctoral This record was generated from author submitted information.
Subject(s):	co-critical graphs -- saturation number -- Ramsey-minimal -- Gallai coloring -- Gallai-Ramsey number -- rainbow triangle
Persistent Link to This Record:	http://purl.flvc.org/ucf/fd/CFE0007745
Restrictions on Access:	public 2019-08-15
Host Institution:	UCF

In Collections

ETD Collection

Search In

You are here

In Collections