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

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

Theorem 5.1 (Ajtai-Komlos-Szemeredi, 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. 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 .

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 $p ≫ \frac{1}{d}$ , so 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 increases.

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 = \frac{1}{d^{1 + o (1)}} \to p = (1 + o (1)) \frac{\log d}{d} .$

Fact. Let $φ$ be a covex 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. □

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 (x) - 1) f (d^{'}),

where

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

and

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

by triangle-free property.

We have

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

We want

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

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

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

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

\begin{array}{l} 1 + f^{'} (d) (- \frac{2}{n} \sum_{x} \sum_{y \sim x} 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. □

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

Proof. Choose an independent set $I$ uniformly at random among all independent sets. We’ll show

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

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

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

Note, fix $I$ ,

\sum_{v \in V (G)} X_{v} \leq d | I | + d | I | \leq 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)$ ( $N (J)$ here 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^{'}]$ .

𝔼 (X_{v} | I \cap F = J) = \frac{d}{2^{l - 1} + 1} + (\frac{l - 1}{2}) (\frac{2^{l - 1}}{2^{l - 1} + 1}) \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 . □

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}$ .

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