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

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

Theorem 5.1 (Ajtai-Komlós-Szemerédi, 1980s + Shearer 80s). $R (3, k) \leq (1 + o (1)) \frac{k^{2}}{\log k}$ .

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.

Remark. If we take $G \sim G (n, \frac{d}{n})$ and modify, for $d ≪ \sqrt{n}$ , one can show that there exist graphs with no triangles and

α (G) \leq (2 + o (1)) \frac{n}{d} \log d .

So Theorem 5.2 is in some sense sharp.

In fact, understanding what happens between these $1 + o (1)$ and $2 + o (1)$ cases is a big open problem.

Sketch pad:

Idea I: Greedily build an independent set $\geq \frac{n}{d + 1}$ .
Idea II: Choose a set at random?? Choose each vertex with probability $p$ . But note that if $p ≫ \frac{1}{d}$ , then for each vertex, we are likely to pick $p d ≫ 1$ of its neighbours.
Idea III: Use Local Lemma? Too much dependence.
Idea IV: Combine Ideas I and II by using a random greedy process. Take a vertex, remove its neighbours. Then using the triangle-freeness, we should get that density decreases.

Heuristic: Let’s say we build an independent set $I$ using this process with $| I | = p n$ . Assumption: “the set $I$ looks like a random set of its density – apart from the fact that it’s independent”.

Let’s consider the largest $p$ we can hope for. Say a vertex $v$ is open if $N (v) \cap I = \emptyset$ .

We might expect
$ℙ_{p} (v is open) \overset{!}{\approx} {(1 - p)}^{d} .$

Note that $ℙ_{p} (v is open) ≪ p$ then process is basically over (“amount of vertices left that we could potentially use is $≪$ than the number of vertices we have so far, so not really any point in trying to collect them”). So solve ${(1 - p)}^{d} = p$ . First estimate that we need $p = \frac{1}{d^{1 + o (1)}}$ , and then using this we can solve to get
$p = (1 + o (1)) \frac{\log d}{d} .$

Fact (Jensen’s inequality). Let $φ$ be a convex function on $ℝ$ . Let $X$ be a random variable. Then

𝔼 φ (X) \geq φ (𝔼 X) .

Fact. Let $G$ be a graph with average degree $d = \frac{2 e (G)}{n}$ . Then

\sum_{x \sim V (G)} \sum_{y \sim x} d (y) = \sum_{x \in V (G)} d {(x)}^{2} \geq n d^{2}

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.

Define

f (d) = \frac{d \log d - d + 1}{{(d - 1)}^{2}} .

Note $f (d) \in (0, 1)$ for $1 < d$ , $f^{'} (d) < 0$ and $f^{″} (d) \geq 0$ . We have

f (x) \geq f (x_{0}) + (x - x_{0}) f^{'} (x_{0})

by remainder form of Taylor’s theorem.

Theorem 5.3 (Shearer on $f (d)$ ). Assuming that:

$G$ an $n$ vertex graph
triangle-free
average degree $d$

Then

α (G) \geq f (d) n .

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

We have shown

c \frac{k^{2}}{{(\log k)}^{2}} \leq R (3, k) \leq (1 + o (1)) \frac{k^{2}}{\log k} .

Kim showed $R (3, k) = Θ (\frac{k^{2}}{\log k})$ .

Triangle-free process: Define the random graph process ${(G_{i})}_{i}$ . Given $G_{i}$ define

O_{i} = {e \in {[n]}^{(2)} : G_{i} + e ⁄ \supset K_{3}} .

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.

Remark. There is some similarity between the triangle-free process and the first proof of Theorem 5.2 that we saw: both are about a process where each step is uniformly random once we condition on a desired property. So we might expect a related theorem to hold for the triangle-free process, and indeed this is the case.

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)$ :

Theorem 5.4 (Shearer upper bound on $R (3, k)$ ). $R (3, k) \leq (1 + o (1)) \frac{k^{2}}{\log 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