Some Ramsey-type Theorems Öffentlichkeit
Retter, Troy (2016)
Published
Abstract
We consider three Ramsey-type problems. Extending the concept of the Ramsey numbers, Erdos and Rogers introduced the function f_{s,t}(n)=min { max { |W| : W subseteq V(G) and G[W] contains no K_s} }, where the minimum is taken over all K_t-free graphs G of order n. We establish that for every s greater than 2 there exist constants c_1 and c_2 such that f_{s,s+1}(n) is less than or equal to c_1 (log n)^{c_2} n^{1/2}. We also prove that for all t-2 greater than or equal to s greater than or equal to 4, there exists a constant c_3 such that f_{s,t}(n) is less than or equal to c_3 n^{1/2}. In doing so, we give a partial answer to a question of Erdos. To state our second problem, we introduce some notation. For a graph S, the h-subdivision S^{(h)} is obtained by replacing each edge with a path of length h+1. For any graph S of maximum degree d on s greater than s_0(h,d,q) vertices, we show there exists a graph G with (log s)^{20h} s^{1+1/(h+1)} edges having the following Ramsey property: any coloring of the edges of G with q colors yields a monochromatic copy of the subdivided graph S^{(h)}. This result complements work of Pak regarding `long' subdivisions of bounded degree. Another question of Erdos, answered by Rodl and Rucionski, asks if for every pair of positive integers q and k, there exist a graph H having grith k and the property that every q-coloring of the edges of H yields a monochromatic cycle C_k. Here, we establish that such a graph exists with at most r^{O(k^2)} k^{O(k^3)} vertices, where r = r_{q}(C_k) is the q color Ramsey number for the cycle C_k. We also consider two closely related problems.
Table of Contents
Introduction..............................................................................1
A Function of Erdos and Rogers...................................................6
Size-Ramsey Numebrs of Short Subdivisions...............................27
Ramsey Number Involving Large Girth Graphs and Hypergraphs...86
Bibliography.............................................................................118
About this Dissertation
School | |
---|---|
Department | |
Degree | |
Submission | |
Language |
|
Research Field | |
Stichwort | |
Committee Chair / Thesis Advisor | |
Committee Members |
Primary PDF
Thumbnail | Title | Date Uploaded | Actions |
---|---|---|---|
|
Some Ramsey-type Theorems () | 2018-08-28 12:37:35 -0400 |
|
Supplemental Files
Thumbnail | Title | Date Uploaded | Actions |
---|