Topics in Ramsey Theory Pubblico

Abstract

Abstract
In this dissertation we discuss two results in Ramsey Theory.
Result I: the size-Ramsey number of a graph H is the smallest number
of edges a graph G must have in order to force a monochromatic copy of H
in every 2-coloring of the edges of G. In 1990, Beck studied the size-Ramsey
number of trees: he introduced a tree invariant β(·), and proved that the
size-Ramsey number of a tree T is at least β(T)/4. Moreover, Beck showed
an upper bound for this number involving β(T), and further conjectured
that the size-Ramsey number of any tree T is of order β(T). We answer his
conjecture affirmatively. Our proof uses the expansion properties of random
bipartite graphs.
Result II: We prove the following metric Ramsey theorem. For any con-
nected graph G endowed with a linear order on its vertex set, there exists a
graph R such that in every coloring of the t-sets of vertices of R it is possible
to find a copy G' of G inside R satisfying the following two properties:
• the distance between any two vertices x, y ∈ V(G') in the graph R is
the same as their distance within G';
• the color of each t-set in G' depends only on the graph-distance metric
induced in G' by the ordered t-set.

Table of Contents

Contents
1 Introduction 1
2 The size-Ramsey number of trees 4
2.1 Introduction
2.1.1 Organization of the chapter
2.1.2 The lower bound
2.2 Preliminaries
2.3 Outline of a simpler case
2.4 Properties of random bipartite graphs
2.5 Auxiliary results
2.6 An embedding scheme for trees
2.6.1 Description of the algorithm
3 Distance preserving Ramsey graphs
3.1 Introduction
3.2 Proof of Lemma 3.19
3.3 The base of the induction
3.4 Proof of Theorem 3.11
3.4.1 Proof of Theorem 3.11
3.4.2 An unordered version of Lemma 3.10
3.5 Proof of Lemma 3.35

Bibliography

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
Parola chiave	Ramsey theory
Committee Chair / Thesis Advisor	Rodl, Vojtech, Emory University
Committee Members	Duffus, Dwight A, Emory University Gould, Ronald J, Emory University

Ultima modifica

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Topics in Ramsey Theory ()	2018-08-28 16:20:26 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions