# Some Ramsey-type Theorems Open Access

## Retter, Troy (2016)

Permanent URL: https://etd.library.emory.edu/concern/etds/qr46r1285?locale=en
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.

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