Upper bounds on R(3,k) - Probabilistic Combinatorics

Theorem 5.2 (Shearer, 1980s). Assuming that:

$G$ a triangle-free graph on $n$ vertices
max degree $d$

Then

α (G) \geq (1 + o (1)) \frac{n}{d} (\log d),

where $o (1) \to 0$ as $d \to \infty$ .

Remark. Given $G$ on $n$ vertices with maximum degree $d$ , we can use greedy algorithm to show $α (G) \geq \frac{n}{d + 1}$ : pick a vertex not adjacent to anything picked so far, and chuck away its neighbours. At each iteration, we use up at most $d + 1$ vertices, hence we can run the algorithm for at least $\frac{n}{d + 1}$ steps.

Theorem 5.2 beats this simple argument by a factor of $\log d$ , under the additional assumption that $G$ is triangle-free.

Fact (Jensen’s inequality). Let

φ

be a convex function on

ℝ

. Let

X

be a random variable. Then

Proof.

\begin{array}{l} \sum_{x \in V (G)} \sum_{y \sim x} d (y) & = \sum_{x} \sum_{y} d (y) 𝟙_{x \sim y} \\ = \sum_{y} d (y) \sum_{x} 𝟙_{x \sim y} \\ = \sum_{y} d {(y)}^{2} \end{array}

The inequality follows by Jensen. □

Now we will prove Shearer, 1980s (in fact a slight strengthening). We discussed earlier that the proof will involve repeatedly removing vertices and tracking a density increase. Shearer found a very elegant way of tracking this, that makes the proof very clean and magical looking, but the key idea is really the sketch argument given above.

Note

f (d) \in (0, 1)

for

1 < d

f^{'} (d) < 0

and

f^{″} (d) \geq 0

. We have

Proof. Let $v \in V (G)$ . Define $G^{'} = G - N (v) - v$ . We have

α (G) \geq 1 + α (G^{'}) \geq 1 + (n - d (v) - 1) f (d^{'}),

where

d^{'} = average degree of G^{'} = \frac{2 e (G^{'})}{(n - d (v) - 1)}

and

e (G^{'}) = e (G) - \sum_{y \sim v} d (y)

by triangle-free property.

Using the earlier working, we have

\begin{array}{l} α (G) & \geq 1 + f (d) (n - d (v) - 1) + (d^{'} - d) f^{'} (d) (n - d (v) - 1) \\ \geq f (d) n - f (d) (d (v) + 1) + f^{'} (d) (2 e (G^{'}) - 2 e (G) + d \cdot d (v) + d) + 1 \\ \geq f (d) n - f (d) (d (v) + 1) + f^{'} (d) (2 e (G) - 2 \sum_{y \sim v} d (y) - 2 e (G) + d \cdot d (v) + d) + 1 \end{array}

We want

f (d) (d (v) + 1) \leq f^{'} (d) (- 2 \sum_{y \sim v} d (y) + d \cdot d (v) + d) + 1 .

We claim this holds on average. Average of left hand side is

\frac{1}{n} \sum_{v \in V (G)} f (d) (d (v) + 1) = f (d) (d + 1) .

Average of right hand side is (using $f^{'} (d) < 0$ ),

\begin{array}{l} \frac{1}{n} \sum RHS & = 1 + f^{'} (d) (- \frac{2}{n} \sum_{v} \sum_{y \sim v} d (y) + d^{2} + d) \\ \geq 1 + f^{'} (d) (- 2 d^{2} + d^{2} + d) \\ = 1 + f^{'} (d) (d - d^{2}) \end{array}

In fact, $f$ satisfies the differential equation

f (x) (x + 1) = f^{'} (x) (x - x^{2}) + 1 .

So the inequality holds on average, and thus there exists a good choice of $v$ for the induction. □

In this proof, note that this function

f

is not essential to the proof and is just helpful to make the presentation as short as possible.

We now give another proof of Theorem 5.2, but with some constant

c

instead of

1 + o (1)

, and this time we’ll assume the maximum degree is bounded rather than the average degree:

Second proof of Theorem 5.2. Choose an independent set $I$ uniformly at random among all independent sets. We’ll show

𝔼 | I | \geq c \frac{n}{d} \log d .

This is an example of what is known as the “hard-core model”. It is called “hard” because we have a hard constraint on every edge (we require that each edge is not present).

Let $X_{v}$ , for $v \in V (G)$ , be defined by

X_{v} = d \cdot 𝟙_{v \in I} + | N (v) \cap I | .

Note, for fixed $I$ ,

\sum_{v \in V (G)} X_{v} = \sum_{v \in V (G)} d \cdot 𝟙_{v \in I} + | N (v) \cap I | \leq d | I | + d | I | = 2 d | I | .

\sum_{v} 𝔼 X_{v} \leq 2 d \cdot 𝔼 | I |,

and so enough to show

𝔼 X_{v} \geq c \log d,

for $\forall v \in V (G)$ and some $c > 0$ .

Now fix $v \in V (G)$ and define

L = N (v) \cup {v}, F = V (G) - v - N (v) .

We now bound

𝔼 X_{v} \geq \min_{J \subset F} 𝔼 (X_{v} | I \cap F = J) .

So now fix some $J \subset F$ . We consider $I \cap L^{'}$ where $L^{'} = L ∖ N (J)$ and $N (J)$ means ${y : \exists x \in J, x \sim y}$ . Let $l = | L^{'} |$ .

Now observe that $I \cap L^{'}$ is uniform over all independent sets in $G [L^{'}]$ . So since $I \cap L^{'}$ is either ${v}$ or any subset of $L^{'} ∖ {v}$ , we have

𝔼 (X_{v} | I \cap F = J) = \frac{d}{2^{l - 1} + 1} + (\frac{l - 1}{2}) (\frac{2^{l - 1}}{2^{l - 1} + 1}) .

We are happy with this inequality, because if $l$ is large, then the second term is large, and if $l$ is small then the first term is large.

Continuing the above calculation, we have

𝔼 (X_{v} | I \cap F = J) \geq \max {\frac{d}{2^{l - 1} + 1}, \frac{l - 1}{4}} .

Now solve

\frac{d}{2^{l - 1} + 1} = \frac{l - 1}{4},

which is $4 d = (l - 1) (2^{l - 1} + 1)$ , so $l = c \log d$ . So

𝔼 (X_{v} | I \cap F = J) \geq c \log d,

and thus $𝔼 X_{v} \geq c \log d$ as desired. □

5.1 Recap of

R (3, k)

bounds proved in this course

Triangle-free process: Define the random graph process

{(G_{i})}_{i}

. Given

G_{i}

define

Now sample

e_{i + 1} \sim O_{i}

uniformly at random, and define

G_{i + 1} = G_{i} + e_{i + 1}

This method is not what Kim used, but it was used by others later to improve the lower bound.

Up until very recently, every proof of lower bound on

R (3, k)

has used a variant of the triangle-free process.

The Ramsey numbers

R (3, k)

are still of interest, as there is now interest in determining the right constant.

We now finish this section by using Theorem 5.2 to deduce the upper bound on

R (3, k)

Proof. Let $n = (1 + δ) \frac{k^{2}}{\log k}$ . If there is a vertex of degree $\geq k$ in the blue graph then we have an independent set of size $k$ because the blue graph must be triangle-free, otherwise done. So the max degree of blue graph is $\leq k$ .

So apply Shearer, 1980s to get (for large $k$ ) that

\begin{array}{l} α (G) & \geq (1 + o (1)) \frac{n}{k} \log k \\ = (1 + o (1)) (1 + δ) \frac{k^{2}}{(\log k) k} \log k \\ \geq k \end{array}

(where $G$ is the blue graph). □

5 Upper bounds on R(3,k)

5.1 Recap of R(3,k) bounds proved in this course

5 Upper bounds on $R (3, k)$

5.1 Recap of $R (3, k)$ bounds proved in this course