Current Search: Zhang, Jingmei (x)


Title

Two Ramseyrelated Problems.

Creator

Zhang, Jingmei, Song, Zixia, Zhao, Yue, Martin, Heath, Turgut, Damla, University of Central Florida

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, ....
Show moreExtremal 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.
Show less

Date Issued

2019

Identifier

CFE0007745, ucf:52404

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0007745