An edge deletion method - Probabilistic Combinatorics

3 An edge deletion method

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 3.1 (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 3.2. 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 3.3. 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 3.4. 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 3.3, 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. □