Topics in Ramsey Theory Open Access
Dellamonica Jr., Domingos (2012)
Published
Abstract
Abstract
In this dissertation we discuss two results in Ramsey Theory.
Result I: the sizeRamsey 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 2coloring of the edges of G. In 1990, Beck studied the
sizeRamsey
number of trees: he introduced a tree invariant β(·), and
proved that the
sizeRamsey 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 sizeRamsey 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 tsets 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 tset in G' depends only on the
graphdistance metric
induced in G' by the ordered tset.
Table of Contents
Contents
1 Introduction 1
2 The sizeRamsey 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
 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 

Topics in Ramsey Theory ()  20180828 16:20:26 0400 

Supplemental Files
Thumbnail  Title  Date Uploaded  Actions 
