The Ramsey numbers R(3,k) - Probabilistic Combinatorics

2 The Ramsey numbers $R (3, k)$

Theorem (Erdos-Szekeres, 1935). $R (l, k) \leq (\binom{k + l - 2}{l - 1})$ .

Proof. Induction. See e.g. GT. □

Note. $R (k) = R (k, k) \leq (\binom{2 (k - 1)}{k - 1}) \sim c \frac{4^{k}}{\sqrt{k}}$ .

Corollary. $R (3, k) \leq k^{2}$ .

Idea 1: If randomly colour $K_{n}$ , we have $\sim \frac{1}{8} (\binom{n}{3})$ triangles $⇝$ :(

Idea 2: We want to bias our distribution in favour of $K_{k}$ – colour “red”. Say $G \sim G (n, p)$ . Sad news: if $p ≫ \frac{1}{n}$ then $G$ contains a $K_{3}$ with high probability. $⇝$ :(

Theorem (Erdos, 1960s). $R (3, k) \geq c {(\frac{k}{\log k})}^{3 ∕ 2}$ for some $c > 0$ .

Proof sketch. Sample $G \sim G (n, p)$ , then define $\tilde{G} = G - (a vertex from each triangle)$ . For this to work we need $\frac{# vertices}{2} > # triangles$ . So $\frac{n}{2} > p^{3} (\binom{n}{3})$ . So take $p \sim n^{- 2 ∕ 3}$ . □

Remark. This is called the “deletion method”.

Fact (Markov). Let $X$ be a non-negative random variable. Let $t > 0$ . Then

ℙ (X \geq t) \leq \frac{𝔼 X}{t} .

That is

ℙ (X \geq s 𝔼 X) \leq \frac{1}{s},

for any $s > 0$ .

Fact. For $1 \leq k \leq n$ we have

(\binom{n}{k}) \leq {(\frac{e n}{k})}^{k}

and

(\binom{n}{k}) \geq {(\frac{n}{k})}^{k} .

Definition 2.1 (Independence number). Let $G$ be a graph. Then $I \subset V (G)$ is independent if $x ⁄ \sim y$ in $G$ for all $x, y \in I$ .

We use $α (G) = size of the largest independent set$ .

Note. We are trying to construct a triangle free graph on $k^{3 ∕ 2 - o (1)}$ vertices with $α (G) < k$ .

Lemma 2.2. Assuming that:

$\frac{1}{n} ≪ p \leq \frac{1}{2}$
$G \sim G (n, p)$

Then

α (G) \leq (2 + o (1)) \frac{\log n p}{p},

with probability tending to $1$ as $n \to \infty$ (known as “with high probability (w.h.p.)”).

Remark. We actually have $=$ in this lemma.

Proof. Let $k = (2 + δ) \frac{\log n p}{p}$ , for some $δ > 0$ . Let $X$ be the random variable that counts the number of independent $k$ sets in $G$ .

\begin{array}{l} 𝔼 X & = 𝔼 \sum_{I \in {[n]}^{(k)}} 𝟙_{I is independent} \\ = \sum_{I \in {[n]}^{(k)}} ℙ (I is independent) \\ = (\binom{n}{k}) {(1 - p)}^{(\binom{k}{2})} \\ \leq {(\frac{e n}{k})}^{k} e^{- p (\binom{k}{2})} \\ \leq {(\frac{e n}{k} \cdot e^{- (\frac{k - 1}{2}) p})}^{k} \\ \to 0 \end{array}

by plugging in $k$ . So by Markov

ℙ (X \geq 1) \leq 𝔼 X \to 0 . □

We have a method for bounding the probability that $X$ is large: Markov says that $ℙ (X > t) \leq \frac{𝔼 X}{t}$ . What about bounding the probability that it is small?

Fact: Let $X$ be a random variable with $𝔼 X$ , $Var X$ finite. Then for all $t > 0$ ,

ℙ (| X - 𝔼 X | \geq t) \leq \frac{Var X}{t^{2}} .

Reminder:

Var X = 𝔼 X^{2} - {(𝔼 X)}^{2} = 𝔼 {(X - 𝔼 X)}^{2} .

Lemma 2.3. Assuming that:

$\frac{1}{n} ≪ p \leq 1$
$G \sim G (n, p)$

Then

# triangles in G = (1 + o (1)) p^{3} (\binom{n}{3})

with high probability.

Proof. Let $X$ be the random variable counting the number of triangles in $G$ . Note

X = \sum_{T \in {[n]}^{(3)}} 𝟙_{T^{(2)} \subset G} .

Mean is straightforward:

𝔼 X = p^{3} (\binom{n}{3}) .

Variance is a little more tricky. First:

X^{2} = \sum_{S, T \in {[n]}^{(3)}} 𝟙_{S^{(2)}, T^{(2)} \subset G} .

We can write

\begin{array}{l} 𝔼 X^{2} & = \sum_{S, T \in {[n]}^{(2)}} ℙ (T^{(2)}, S^{(2)} \subset G) \\ {(𝔼 X)}^{2} & = \sum_{S, T \in {[n]}^{(2)}} ℙ (T^{(2)} \subset G) ℙ (S^{(2)} \subset G) \end{array}

Since the pairs of events are independent whenever $| S^{(2)} \cap T^{(2)} | = 0$ , we have

\begin{array}{l} Var X & \leq \sum_{\begin{array}{c} S, T \in {[n]}^{(2)} \\ | S^{(2)} \cap T^{(2)} | = 1 \end{array}} \\ \leq p^{5} n^{4} + 𝔼 X \end{array}

Now note

\begin{array}{l} ℙ (| X - 𝔼 X | \geq δ 𝔼 X) & \leq \frac{Var X}{δ^{2} {(𝔼 X)}^{2}} \\ \leq \frac{p^{5} n^{4}}{δ^{2} {(𝔼 X)}^{2}} + \frac{1}{δ^{2} 𝔼 X} \\ \leq C \frac{p^{5} n^{4}}{{(n^{3} p^{3})}^{2}} + \frac{1}{δ^{2} 𝔼 X} \\ \leq C \frac{1}{n^{2} p} + \frac{1}{δ^{2} 𝔼 X} \\ \to 0 \end{array}

□

Recall that before we showed that for $G \sim G (n, p)$ , $\frac{1}{n} ≪ p \leq \frac{1}{2}$ , we have

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

with high probability.

Proof of lower bound on $R (3, k)$ . Set $n = {(\frac{k}{\log k})}^{3 ∕ 2}$ , $p = n^{- 2 ∕ 3}$ . Let $G \sim G (n, p)$ and let $\tilde{G}$ with a vertex deleted from each triangle. Then with high probability we have

\begin{array}{l} α (\tilde{G}) & \leq α (G) \\ \leq (2 + o (1)) \frac{\log n p}{p} \\ \leq (\frac{2}{3} + o (1)) n^{2 ∕ 3} \log n \\ \leq (\frac{2}{3} + o (1)) \frac{k}{\log k} (\log k^{3 ∕ 2}) \\ \leq (1 + o (1)) k & (*) \end{array}

We also have with high probability:

\begin{array}{l} | V (\tilde{G}) | & \geq n - (# of triangles in G) \\ \geq n - (1 + o (1)) \frac{p^{3} n^{3}}{6} \\ = n - (1 + o (1)) \frac{n}{6} \\ \geq \frac{n}{2} & (* *) \end{array}

So with high probability ( $*$ ) and ( $* *$ ) hold. So there must exist a graph $\tilde{G}$ on $\frac{n}{2} = \frac{1}{2} {(\frac{k}{\log k})}^{3 ∕ 2}$ with no triangles and independence number $< k$ (actually not quite, but would have worked if we multiply one of the parameters by a constant or something). □

Definition (Chromatic number). Let $G$ be a graph. The chromatic number of $G$ is the minimum $k$ such that there exists $χ : V (G) \to [k]$ such that no edge has both ends in the same colour.

$χ (G)$ denotes the chromatic number.

Similar to the above lower bound on $R (3, k)$ , Erdős proved:

Theorem (Erdős). There exist graphs $G$ with arbitrarily large chromatic number and arbitrarily large girth, i.e. for all $g, k \in ℕ$ there exists $G$ with girth $> g$ and $χ (G) > k$ .

Idea: let’s delete an edge from each triangle, instead of a vertex (we have a lot more edges to spend than we have vertices!).

For this we need

p^{3} n^{3} ≪ p n^{2}

so $p = \frac{γ}{\sqrt{n}}$ . For some small $γ > 0$ .

Danger: when we delete an edge from each triangle, we need to ensure that we don’t hurt $α (G)$ .

Theorem 2.4 (Erdos, 1960s). $R (3, k) \geq c \frac{k^{2}}{{(\log k)}^{2}}$ for some $c > 0$ .

To prove this, it is enough to prove for sufficiently large $n$ that there exists a triangle free graph on $n$ vertices with

α (G) \leq C n^{\frac{1}{2}} \log n

for some $C > 0$ .

This is because we can set $k = C \sqrt{n} \log n$ , and then get $n = c \frac{k^{2}}{{(\log k)}^{2}}$ .

More sketching of the idea: we know $α (G) \leq 2 \frac{\log n}{p}$ .

What if $k > 2 \frac{\log n p}{p}$ ? Then there must be an edge (because $α (G) < k$ .

Not very impressive.

What if $k > 100 \frac{\log n p}{p}$ ? Then we actually get a lot of edges: expect $p k^{2}$ , and can guarantee $\frac{p k^{2}}{16}$ .

Lemma 2.5. Assuming that:

$\frac{1}{n} ≪ p \leq \frac{1}{2}$
$G \sim G (n, p)$
$k > C \frac{\log n}{p}$

Then with high probability every set of size

\geq k

G

induces

\frac{p k^{2}}{16}

edges.

Proof. Fix $t = \frac{p k^{2}}{16}$ and fix a set $S$ with size $| S | = k$ .

\begin{array}{l} ℙ (e (G [S]) < t) & \leq \sum_{i = 0}^{t} (\binom{(\binom{k}{2})}{i}) p^{i} {(1 - p)}^{(\binom{k}{2}) - i} \\ \leq t (\binom{(\binom{k}{2})}{t}) p^{t} {(1 - p)}^{(\binom{k}{2}) - t} \\ \leq t [{(\frac{e k^{2}}{2 t})}^{t} p^{t}] e^{- p [(\binom{k}{2}) - t]} \\ \leq t {(e 8)}^{\frac{p k^{2}}{16}} e^{- p (\binom{k}{2}) ∕ 2} \\ \leq k^{2} {[{(e 8)}^{1} e^{- 4 + o (1)}]}^{\frac{p k^{2}}{16}} \\ \leq e^{- α p k^{2}} \end{array}

for some $α > 0$ .

We now union bound on all $S \in {[n]}^{(k)}$ .

\begin{array}{l} ℙ (\exists S \in {[n]}^{(k)} such that e ([S]) < t) & \leq (\binom{n}{k}) ℙ (e (G [S]) < t) \\ \leq {(\frac{e n}{k})}^{k} e^{- α k^{2} p} \\ = {(\frac{e n}{k} \cdot e^{- α k p})}^{k} \\ \leq {(e n p {(\frac{1}{p n})}^{α C})}^{k} \end{array}

(using $k p \geq C \log n$ ) which $\to 0$ for $C > \frac{1}{α}$ . □

Lemma 2.6. Assuming that:

$F = {A_{i}}_{i}$ be a collection of events
$E_{t}$ , for $t \in ℕ$ , be the event that t independent events of $F$ occur

Then

ℙ (E_{t}) \leq \frac{1}{t!} {(\sum_{i} ℙ (A_{i}))}^{t} .

Remark. $t! = t^{t} e^{- t} \sqrt{2 π t} (1 + o (1))$ .

We will use $t! \geq t^{t} e^{- t} ∕ 2$ for large $t$ in the above lemma to get:

ℙ (E_{t}) \leq 2 {(\frac{e 𝔼 (# of A_{i} that hold}{t})}^{t} .

Proof. Let $I = {(A_{i_{1}}, \dots, A_{i_{k}}) : A_{i_{1}}, \dots, A_{i_{k}} are independent}$ .

\begin{array}{l} 𝟙_{E_{t}} & \leq \frac{1}{t!} \sum_{(A_{i_{1}}, \dots, A_{i_{k}} \in I} 𝟙_{A_{i_{1}} \cap \dots \cap A_{i_{k}}} \\ ℙ (E_{t}) & \leq \sum_{(A_{i_{1}}, \dots, A_{i_{k}}) \in I} ℙ (A_{i_{1}} \cap \dots \cap A_{i_{k}}) \\ \leq \frac{1}{t!} \sum_{i_{1}, \dots, i_{t}} ℙ (A_{i_{1}}) \dots ℙ (A_{i_{k}}) \\ = \frac{1}{t!} {(\sum_{i} ℙ (A_{i}))}^{t} □ \end{array}

Theorem. Assuming that:

$n \geq 2$

Then there exists a triangle-free graph

G

n

vertices with

α (G) \leq C \sqrt{n} \log n .

Proof. Let $n$ be large. Let $p = \frac{γ}{\sqrt{n}}$ for some $γ > 0$ . Let $G \sim G (n, p)$ , and let $\tilde{G}$ be $G$ with a maximal collection of edge disjoint triangles $T$ removed, i.e. $\tilde{G} = G - T$ .

Clearly $\tilde{G}$ is triangle-free. We let $Q$ be the event that every set of size $k$ , where $k = C \sqrt{n} \log n$ contains at least $\frac{p k^{2}}{16}$ edges. We now consider

ℙ (α (\tilde{G}) \geq k) = ℙ (α (\tilde{G}) \geq k \cap Q) + ℙ (α (\tilde{G}) \geq k \cap Q^{c}) .

ℙ (α (\tilde{G}) \geq k) \leq \underset{(*)}{\underset{⏟}{ℙ (α (\tilde{G}) \geq k \cap Q)}} + o (1) .

We now union-bound

\begin{array}{l} (*) & \leq (\binom{n}{k}) ℙ (I independent in \tilde{G} \cap Q) \\ = (\binom{n}{k}) ℙ (T intersects I in \geq \frac{p k^{2}}{16} edges) \end{array}

Define ${T_{i}}$ to be the collection of all triangles that meet $I$ in at least one edge, and define the event $A_{i} = {T_{i} \subset G}$ .

Note that the event $E_{t}$ , where $t = \frac{p k^{2}}{16}$ , from the lemma holds on the event that $T$ meets $I$ in $\frac{p k^{2}}{16}$ edges. This is where we use the fact that we only choose edge-disjoint triangles! By Lemma 2.6, we have

\begin{array}{l} ℙ (E_{t}) & \leq 2 {(\frac{e k^{2} n p^{3}}{t})}^{t} \\ \leq {(\frac{16 e k^{2} n p^{3}}{p k^{2}})}^{\frac{p k^{2}}{16}} \\ = {(16 e γ^{2})}^{\frac{p k^{2}}{16}} \end{array}

(*) \leq {(16 e γ^{2})}^{\frac{p k^{2}}{16}} {(\frac{e n}{k})}^{k} \to 0,

if $γ$ is chosen to be small and $C$ large. □

2.1 Lovasz-Erdős Local Lemma

Lemma 2.7 (Erdos-Lovasz, 70s). Assuming that:

$F = {A_{i}}$ is a family of events in a probability space
$G$ a dependency graph of $F$
$ℙ (A_{i}) \leq \frac{1}{e (Δ + 1)}$ , where $Δ = Δ (G)$ is the max degree of $G$

Then

ℙ (⋂_{i} A_{i}^{c}) > 0 .

Definition 2.8 (Dependency graph). If $F = {A_{i}}$ is a family of events, a dependency graph $G$ is a graph with vertex set $F$ , with the property that: for all $i$ , the event $A_{i}$ is independent from ${A_{j} : A_{j} ⁄ \sim A_{i}}$ .

Picture:

Reminder: $A_{i}$ is independent from ${A_{j} : A_{j} ⁄ \sim A_{i}}$ if $E$ is formed by taking intersections of $A_{j}, A_{j}^{c} ⁄ \sim A_{i}$ , we have

ℙ (A_{i} \cap E) = ℙ (A_{i}) ℙ (E) .

Theorem (Spencer). $R (k) \geq (1 + o (1)) \frac{\sqrt{2} k}{e} 2^{k ∕ 2}$ .

Proof. Let $δ > 0$ and let $n = (1 - δ) \frac{\sqrt{2} k}{e} 2^{k ∕ 2}$ . Choose a colouring uniformly at random. For every $S \in {[n]}^{(k)}$ , define the event

A_{S} = “ S^{(2)} are monochromatic” .

We clearly have $ℙ (A_{S}) = 2^{- (\binom{k}{2}) + 1}$ .

Let $G$ be the dependency graph on ${A_{S}}_{S}$ where $A_{S} \sim A_{T}$ if $S^{(2)} \cap T^{(2)} \neq \emptyset$ .

Δ = Δ (G) \leq (\binom{k}{2}) \cdot (\binom{n - 2}{k - 2}) \leq k^{4} \cdot (\frac{1}{n^{2}}) (\binom{n}{k})

We now check:

Δ \cdot 2^{- (\binom{k}{2}) + 1} \leq 2 k^{4} (\frac{1}{n^{2}}) {(\frac{e n}{k})}^{k} 2^{- (\binom{k}{2})} = {[(1 + o (1)) \frac{1}{n^{2 ∕ k}} (\frac{e n \sqrt{n}}{k} \cdot 2^{- k ∕ 2})]}^{k} .

This $\to 0$ . So the condition in Local Lemma holds for sufficiently large $k$ . □

Remark. This is the best known lower bound for diagonal Ramsey.

Definition 2.9 ( $k$ -uniform hypergraph). Say $H$ is a $k$ -uniform hypergraph on vertex set $X$ if $H \subset X^{(k)}$ .

Definition 2.10 (Colourable $k$ -uniform hypergraph). Say a $k$ -uniform hypergraph is $2$ -colourable if there exists $χ : X \to {red, blue}$ such that there is no monochromatic $e \in H$ .

Theorem 2.11. Assuming that:

$H$ a $k$ -uniform hypergraph with maximum degree $d$
$d \leq \frac{2^{k - 1}}{e k} - 1$

Then

H

2

-colourable.

Proof. We choose our colouring of the ground set $X$ uniformly at random. For each $e \in H$ , define the event

A_{e} = “ e monochromatic” .

We have $ℙ (E_{e}) = 2^{- k + 1}$ . We want $2^{- k + 1} \leq \frac{1}{e (Δ + 1)}$ . Note if we define our dependency graph $G$ by $A_{e} \sim A_{f}$ if $e \cap f \neq \emptyset$ , then

Δ (G) \leq d \cdot k .

Now just use the bound on $d$ in the hypothesis. □

Remark. Actually, our second application implies the first on $R (k)$ : just let $H$ be the $(\binom{k}{2})$ -uniform hypergraph on $X = {[n]}^{(2)}$ , defined by

H = {S^{(2)} : S \in {[n]}^{(k)}} .

Theorem 2.12 (Lopsided Local Lemma). Assuming that:

$F = {A_{i}}$ a family of events
$G$ a dependency graph
$x_{1}, \dots, x_{n} \in (0, 1)$ be such that $\forall i$ ,

$ℙ (A_{i}) \leq x_{i} \prod_{A_{i} \sim A_{j}} (1 - x_{j})$

(where $A_{i} \sim A_{j}$ denotes adjacency in the dependency graph).

Then

ℙ (⋂_{i = 1}^{n} A_{i}^{c}) \geq \prod_{i = 1}^{n} (1 - x_{i}) .

Proof. We use

ℙ (A \cap B) = ℙ (A | B) ℙ (B) .

Applying this many times, we have

\begin{array}{l} ℙ (⋂_{i = 1}^{n} A_{i}^{c}) & = \prod_{i = 1}^{n} ℙ (A_{i}^{c} | A_{1}^{c} \cap \dots \cap A_{i - 1}^{c}) \\ = \prod_{i = 1}^{n} (1 - \underset{\leq x_{i} ?}{\underset{⏟}{ℙ (A_{i} | A_{1}^{c} \cap \dots \cap A_{i - 1}^{c})}}) \end{array}

We will prove that this term is $\leq x_{i}$ by instead proving the more general statement:

(*) = ℙ (A_{i} | ⋂_{j \in S} A_{j}^{c}) \leq x_{i},

where $S \subset [n] ∖ {j}$ . We prove by induction on $| S |$ .

If $S = \emptyset$ , then done by hypothesis.

If $S \neq \emptyset$ , then define

D = ⋂_{\begin{array}{c} j \in S \\ j \sim i \end{array}} A_{j}^{c}, I = ⋂_{j \in S j ⁄ \sim i} A_{j}^{c} .

Note that

\begin{array}{l} (*) & = ℙ (A_{i} | D \cap I) \\ = \frac{ℙ (A_{i} \cap D \cap I)}{ℙ (D \cap I)} \\ \leq \frac{ℙ (A_{i} \cap I)}{ℙ (D \cap I)} \\ = \frac{ℙ (A_{i}) ℙ (I)}{ℙ (D \cap I)} \\ = \frac{ℙ (A_{i})}{ℙ (D | I)} \end{array}

Let ${A_{i_{1}}, \dots, A_{i_{s}}}$ be the events in the intersection $D$ . Then

\begin{array}{l} ℙ (D | I) & = \prod_{j = 1}^{s} ℙ (A_{i_{j}}^{c} | I \cap A_{i_{1}}^{c} \cap \dots \cap A_{i_{j - 1}}^{c}) \\ = \prod_{j = 1}^{s} (1 - ℙ (A_{i_{j}} | I \cap A_{i_{1}}^{c} \cap \dots \cap A_{i_{j - 1}}^{c})) \end{array}

If no events in the intersection, then we are already done. Otherwise, we may apply the induction hypothesis to each term to get

\frac{ℙ (A_{i})}{ℙ (D | I)} \leq \frac{x_{i} \prod_{j \sim i} (1 - x_{j})}{\prod_{j = 1}^{s} (1 - x_{i_{j}})} \leq x_{i} . □

Proof of Local Lemma. Apply Lopsided Local Lemma with weights $x_{i} = \frac{1}{Δ + 1}$ for all $i$ . We just need to check that the probability upper bounds in Lopsided Local Lemma hold.

By calculus, we have

{(\frac{Δ}{Δ + 1})}^{Δ} \geq \frac{1}{e} .

Hence

\begin{array}{l} ℙ (A_{i}) & \leq \frac{1}{e (Δ + 1)} \\ \leq \frac{1}{Δ + 1} {(\frac{Δ}{Δ + 1})}^{Δ} \\ = \frac{1}{Δ + 1} {(1 - \frac{1}{Δ + 1})}^{Δ} \\ \leq \frac{1}{Δ + 1} \prod_{A_{i} \sim A_{j}} (1 - \frac{1}{Δ + 1}) □ \end{array}

Now we will see another proof of $R (3, k) \geq c \frac{k^{2}}{{(\log k)}^{2}}$ , in order to give some intuition as to what kind of situations are good for Local Lemma.

Proof of $R (3, k) \geq c \frac{k^{2}}{{(\log k)}^{2}}$ using Local Lemma. Recall that it is enough to show that for sufficiently large $n$ , there exists a triangle -free graph on $n$ vertices with $α (G) \leq C \sqrt{n} \log n$ .

Set $k = C \sqrt{n} \log n$ , and sample $G \sim G (n, p)$ where $p = \frac{γ}{\sqrt{n}}$ , with $γ > 0$ is chosen later.

Define the events:

For each $T \in {[n]}^{(3)}$ , define
$A_{T} = “ T^{(2)} \subset G ” .$
For each $I \in {[n]}^{(k)}$ , define
$B_{I} = “ I^{(k)} independent in G ” .$

Define the dependency graph $G$ :

$A_{T} \sim A_{S}$ for $S, T \in {[n]}^{(3)}$ if $S^{(2)} \cap T^{(2)} \neq \emptyset$ .
$A_{T} \sim B_{I}$ for $T \in {[n]}^{(3)}, I \in {[n]}^{(k)}$ if $S^{(2)} \cap I^{(2)} \neq \emptyset$ .
$B_{I} \sim B_{J}$ for $I, J \in {[n]}^{(k)}$ if $I^{(2)} \cap J^{(2)} \neq \emptyset$ .

Now note:

The event $A_{T}$ is $\sim$ to $\leq 3 n$ $A_{S}$ , $S \in {[n]}^{(3)}$ .
The event $A_{T}$ is $\sim$ to $\leq 3 n^{k - 2}$ $B_{I}$ , $I \in {[n]}^{(k)}$ .
The event $B_{I}$ is $\sim$ to $\leq k^{2} n$ $A_{S}$ , $S \in {[n]}^{(3)}$ .
The event $B_{I}$ is $\sim$ to $\leq k^{2} n^{k - 2}$ $B_{J}$ , $J \in {[n]}^{(k)}$ .

We choose $x_{T} = 2 p^{3}$ for all $T \in {[n]}^{(3)}$ (“we want to make it a bit bigger than the probability of it occuring so that we can afford the product stuff”) and $x_{I} = n^{- 10 k}$ for all $I \in {[n]}^{(k)}$ .

Then

\begin{array}{l} x_{T} \prod_{\begin{array}{c} S \in {[n]}^{(3)} \\ T \sim S \end{array}} (1 - x_{S}) \prod_{\begin{array}{c} I \in {[n]}^{(k)} \\ I \sim T \end{array}} (1 - x_{I}) & \geq 2 p^{3} {(1 - 2 p^{3})}^{3 n} {(1 - n^{- 10 k})}^{3 n^{k - 2}} \\ \geq 2 p^{3} \exp (- (1 + o (1)) [2 p^{3} (3 n) + 3 n^{- 10 k} n^{k - 2}]) \\ = 2 p^{3} (1 + o (1)) \\ \geq p^{3} \end{array}

for large enough $n$ . We have $ℙ (B_{I}) = {(1 - p)}^{(\binom{k}{2})} \leq e^{- p (\binom{k}{2})}$ , so

\begin{array}{l} x_{I} {(1 - 2 p^{3})}^{k^{2} n} {(1 - n^{- 10 k})}^{k^{2} n^{k - 2}} & \geq n^{- 10 k} \exp (- (1 + o (1)) [2 p^{3} k^{2} n + n^{- 10 k} k^{2} n^{k - 2}]) \\ = n^{- 10 k} \exp (- (1 + o (1)) (2 γ^{2}) p k^{2}) \end{array}

Note

e^{- p (\binom{k}{2})} = \exp (- \frac{γ}{\sqrt{n}} k C \sqrt{n} (\log n)) = n^{- γ C k} .

First choose $γ$ small so $e^{- 2 γ^{2} p k} ≫ e^{- p (\binom{k}{2}) \frac{1}{2}}$ , and then choose $C ≫ \frac{1}{γ}$ , then done. □

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

Theorem 2.13 (Ajtai-Komlos-Szemeredi, 1980s + Shearer 80s). $R (3, k) \leq (1 + o (1)) \frac{k^{2}}{\log k}$ .

Theorem 2.14 (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 .

2 The Ramsey numbers R(3,k)

2.1 Lovasz-Erdős Local Lemma

2.2 Upper bounds on R(3,k)

2 The Ramsey numbers $R (3, k)$

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