Some Ramseytype Theorems Open Access
Retter, Troy (2016)
Published
Abstract
We consider three Ramseytype 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_tfree 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 t2 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 hsubdivision 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 qcoloring 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
SizeRamsey Numebrs of Short Subdivisions...............................27
Ramsey Number Involving Large Girth Graphs and Hypergraphs...86
Bibliography.............................................................................118
About this Dissertation
 Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
School  

Department  
Degree  
Submission  
Language 

Research Field  
Keyword  
Committee Chair / Thesis Advisor  
Committee Members 
Primary PDF
Thumbnail  Title  Date Uploaded  Actions 

Some Ramseytype Theorems ()  20180828 12:37:35 0400 

Supplemental Files
Thumbnail  Title  Date Uploaded  Actions 
