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.

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
Department
Degree
Submission
Language
  • English
Research field
Keyword
Committee Chair / Thesis Advisor
Committee Members
Last modified

Primary PDF

Supplemental Files