Some Ramsey-type Theorems Open Access

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

Rights statement

• 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	Laney Graduate School
Department	Math and Computer Science
Degree	PhD
Submission	Dissertation
Language	English
Research Field	Mathematics
Keyword	probabilistic combinatorics ramsey theory
Committee Chair / Thesis Advisor	Rodl, Vojtech, Emory University
Committee Members	Huang, Hao, Emory Duffus, Dwight A, Emory University Rucinski, Andrzej, Visiting Gould, Ronald J, Emory University

Last modified

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Some Ramsey-type Theorems ()	2018-08-28 12:37:35 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions