# Topics in Ramsey Theory Open Access

## Dellamonica Jr., Domingos (2012)

Permanent URL: https://etd.library.emory.edu/concern/etds/8k71nj083?locale=en
Published

## 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.

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