DMAT_L11

PHP and Ramsey theory

Theorem 1(General form of PHP).

Let $X$ be a finite set. You have $r$ colors ${1, 2, \dots, r}$ . $∣ X ∣ \geq \sum_{i = 1}^{r} a_{i} - r + 1$ guarantees existence of $a_{1}$ points colored $1$ or $a_{2}$ points colored 2, or so on.

Now, Let $X$ be the vertex set of a graph. $r$ color all edges (subsets of size 2). What is the condition on $∣ X ∣$ such that, given positive integers ${a_{1}, a_{2}, \dots, a_{r}}$ , for some $i$ , there exists a subset of $X$ of size $a_{i}$ all of whose edges have the same color?

Notation: $R^{*} (no. of colors, subset size; a_{1}, a_{2}, \dots, a_{r})$ is the minimum number of $∣ X ∣$ such that the above property is satisfied. For example, $R^{*} (2, 2; 3, 3) = 6$ , $R^{*} (2, 2; 3, 4) = 9$ . We know that $43 \leq R^{*} (2, 2; 5, 5) \leq 46$ , but do not know its exact value.

Theorem 2(Ramsey's theorem).

Given positive integers $r$ , $k$ , $a_{1}$ , $a_{2}$ , …, $a_{r}$ , for any r-coloring of $(k X)$ where $X$ is a finite universe,
$c : (k X) \to {a_{1}, a_{2}, \dots, a_{r}},$
there exists a positive integer $R^{*} (r, k; a_{1}, a_{2}, \dots, a_{r})$ such that if $∣ X ∣ \geq R^{*} (r, k; a_{1}, a_{2}, \dots, a_{r})$ then for any coloring $c$ there is an $i$ and a subset of size $a_{i}$ in $X$ such that every $k$ -subset of $X$ is colored $i$ .

We will first prove a simpler version: The existence of $R^{*} (2, 2; a_{1}, a_{2})$ .

Proof
Induction on $a_{1} + a_{2}$ . Let $∣ X ∣ = n$
$n \geq R^{*} (2, 2; a_{1} - 1, a_{2}) + R^{*} (2, 2; a_{1}, a_{2} - 1)$ works, and those two exist because of the induction hypothesis.
Thus, $R^{*} (2, 2; a_{1}, a_{2}) \geq R^{*} (2, 2; a_{1} - 1, a_{2}) + R^{*} (2, 2; a_{1}, a_{2} - 1)$ .

We can bound $R^{*} (2, 2; a_{1}, a_{2})$ using induction.

R^{*} (2, 2; a_{1}, a_{2}) \leq (a _{1} - 1 a _{1} + a _{2} - 2) .

Theorem 3(Claim).

$R^{*} (2, 2; l, l) \geq c 2^{l /2}$ .

Proof
Let $X$ be an n-vertex complete graph. Our goal is to make $n$ as large as possible such that $X$ does not satisfy Ramsey’s condition, $i$ . $e$ , $X$ has no red l-clique or a blue l-clique.

Consider a random 2-coloring of the edges of $X$ . Let $[n]$ be the vertex set.
Sample space = set of all 2-colorings, of size $2^{(2 n)}$ . The distribution is uniform.

For each subset $S$ of size $l$ , Let $E_{S}$ be the event that $S$ is a red clique or a blue clique. Now,

P (E_{S}) = \frac{1}{2 ^{(2 l)}} + \frac{1}{2 ^{(2 l)}} = \frac{2}{2 ^{(2 l)}} .

P S \in (l [ n ]) ⋃ E_{S} \leq S \in (l [ n ]) \sum P (E_{S}) \leq (l n) \frac{2}{2 ^{(2 l)}}

so, we want

(l n) \frac{2}{2 ^{(2 l)}} < 1.

Get a bound for $n$ .

NoNotes

Graph View

DMAT_L11

PHP and Ramsey theory

Backlinks