Current Search: ramseyminimal (x)
View All Items
 Title
 ON SATURATION NUMBERS OF RAMSEYMINIMAL GRAPHS.
 Creator

Davenport, Hunter M, Song, ZiXia, University of Central Florida
 Abstract / Description

Dating back to the 1930's, Ramsey theory still intrigues many who study combinatorics. Roughly put, it makes the profound assertion that complete disorder is impossible. One view of this problem is in edgecolorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H1,...,Hk) if every kedgecoloring of G contains a monochromatic copy of Hi in color i for some i=1,2,...,k. If c is a (red, blue)edgecoloring of G, we say c is a bad coloring if G contains...
Show moreDating back to the 1930's, Ramsey theory still intrigues many who study combinatorics. Roughly put, it makes the profound assertion that complete disorder is impossible. One view of this problem is in edgecolorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H1,...,Hk) if every kedgecoloring of G contains a monochromatic copy of Hi in color i for some i=1,2,...,k. If c is a (red, blue)edgecoloring of G, we say c is a bad coloring if G contains no red K3or blue K1,t under c. A graph G is (H1,...,Hk)Ramseyminimal if G arrows (H1,...,Hk) but no proper subgraph of G has this property. Given a family F of graphs, we say that a graph G is Fsaturated if no member of F is a subgraph of G, but for any edge xy not in E(G), G + xy contains a member of F as a subgraph. Letting Rmin(K3, K1,t) be the family of (K3,K1,t)Ramsey minimal graphs, we study the saturation number, denoted sat(n,Rmin(K3,K1,t)), which is the minimum number of edges among all Rmin(K3,K1,t)saturated graphs on n vertices. We believe the methods and constructions developed in this thesis will be useful in studying the saturation numbers of (K4,K1,t)saturated graphs.
Show less  Date Issued
 2018
 Identifier
 CFH2000291, ucf:45881
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFH2000291
 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