Size Ramsey number of a graph - Probabilistic Combinatorics

7 Size Ramsey number of a graph

Definition 7.1 ( $G$ -¿ $H$ ). Let $G$ , $H$ be graphs. We write

G \to H

to mean every red / blue colouring of $G$ contains a monochromatic $H$ .

Example. $K_{6} \to K_{3}$ .

Example. $R (k) = \min {n : K_{n} \to K_{k}}$ .

Question: How few edges can a graph $G$ have with $G \to H$ ?

Definition 7.2 (Size Ramsey number). The size Ramsey number of $H$ is

\hat{r} (H) = \min {e (G) : G \to H} .

Theorem 7.3. $\hat{r} (K_{k}) = (\binom{R (k)}{2})$ .

7.1 The size Ramsey number of the path

Straightforward bounds:

2 k \leq \hat{r} (P_{k}) \leq {(c k)}^{2} .

The upper bound is by using the bound on Ramsey numbers of sparse graphs proved last section.

Surprisingly:

Theorem 7.4 (Beck, ’83). $\hat{r} (P_{k}) \leq C k$ , for some constant $C > 0$ .

Theorem 7.5 (Beck, ’83 (Beck 2)). There exists $c, C > 0$ , such that the following holds: Let $p = \frac{C}{n}$ and let $G \sim G (n, p)$ . Then

ℙ (G \to P_{k}) = 1 - o (1)

where $k = c n$ .

Definition 7.6. Let $G$ be a graph on $n$ vertices. Say that $G$ is $δ$ -pseudorandom if all sets $A, B \subset V (G)$ which are disjoint and $| A |, | B | \geq 8 n$ have $e (A, B) > 0$ .

Lemma 7.7. Assuming that:

$δ > 0$

Then there exists

C \geq \frac{4}{δ^{2}}

such that if

p = \frac{C}{n}

and

G \sim G (n, p)

then

ℙ (G is δ -pseudorandom) = 1 - o (1) .

Proof. For $A, B \in {[n]}^{(δ n)}$ disjoint,

\begin{array}{l} ℙ (e (A, B) = 0) & = {(1 - p)}^{| A | | B |} \\ \leq e^{- p δ^{2} n^{2}} \\ \leq e^{- C δ^{2} n} \end{array}

Then

\begin{array}{l} 𝔼 (# of A, B \in {[n]}^{(δ n)} with e (A, B) = 0) & \leq 2^{2 n} \cdot e^{- C δ^{2} n} \\ \to 0 \end{array}

So done by Markov. □

Lemma 7.8. Assuming that:

$G$ a graph on $n$ vertices
$G ⁄ \supset P_{k}$
$a, b \in ℤ_{\geq 0}$ such that $a + b = n - k$

Then there exist disjoint

A, B \subset V (G)

with

| A | = a

| B | = b

and

e (A, B) = 0

Proof. We apply the following “Depth first search algorithm”. We maintain a partition $V (G) = A \cup B \cup P$ where $P$ is a path. First set $A = V (G)$ , $B = P = \emptyset$ . We now repeat the following until $A = \emptyset$ :

(1) If $P = \emptyset$ , then move a vertex from $A$ into $P$ .
(2) If $P \neq \emptyset$ , let $v$ be the end of the path $P$ . If $\exists u \in N (v) \cap A$ , we move $u$ to the end of $P$ . If $N (v) \cap A = \emptyset$ , we move $v$ into $B$ .

We note that since $G$ is $P_{k}$ -free, we have $| P | \leq k$ and therefore

| A \cup B | = | A | + | B | \geq n - k

always.

Also note that at each step we:

Either decrease $A$ by $1$ ; or
We increase $| B |$ by $1$ .

Since $| A | = n$ at the start and $| A | = 0$ at the end, there must be some time for which $| A | = a$ and $| B | \geq b$ .

Now since $e (A, B) = 0$ at all times, we are done. □

Proof of Beck, ’83 (Beck 2). Let $G$ be a graph on $n$ vertices that is $δ$ -pseudorandom with $δ = \frac{1}{16}$ . Let $k = 𝜀 n$ , where $𝜀 > 0$ we choose later. We show $G \to P_{k}$ . So assume not. Let $G = G_{R} \cup G_{B}$ where $G_{R} ⁄ \supset P_{k}$ , $G_{B} ⁄ \supset P_{k}$ . Apply lemma to both $G_{R}$ and $G_{B}$ to find $A, B, A^{'}, B^{'} \subset V (G)$ with $| A | = | B | = | A^{'} | = | B^{'} | = (\frac{1}{2} - \frac{𝜀}{2}) n$ and such that $A, B$ have no red edges between then and $A^{'}, B^{'}$ have no blue edges between them.

Note

| (A \cup B) \cap A^{'} | \geq (\frac{1}{2} - \frac{𝜀}{2}) n .

Without loss of generality assume

| A \cap A^{'} | \geq (\frac{1}{4} - 𝜀) n .

| A \cap B^{'} | \leq | A | - | A \cap A^{'} | \leq (\frac{1}{4} - 2 𝜀) n .

Thus

| B \cap B^{'} | \geq (\frac{1}{4} - 4 𝜀) n .

So $A \cap A^{'}$ and $B \cap B^{'}$ have no edges between them in $G$ , which contradicts the $δ$ -pseudorandomness if $𝜀 = \frac{1}{32}$ . So $G \to P_{k}$ .

So by Lemma 7.7 (which said that $G (n, \frac{C}{n})$ is $δ$ -pseudorandom with high probability), we are done. □

Proof of Beck, ’83. Enough to prove for $k$ sufficiently large. We set $k = 𝜀 n$ as before, $δ = \frac{1}{16}$ and let $C > \frac{4}{δ^{2}}$ . Then $G \sim G (n, p)$ satisfies

G \to P_{k} whp .

Now note

ℙ (e (G) \geq p n^{2}) \leq \frac{𝔼 e (G)}{p n^{2}} \leq \frac{1}{2} .

So (at least) $\frac{1}{2} - o (1)$ proportion of all such graphs work. □