Introduction - Probabilistic Combinatorics

1 Introduction

The course is Probabilistic Combinatorics, being lectured by

Julian \underset{}{\underset{⏟}{Sa}} \underset{}{\underset{⏟}{has}} \underset{}{\underset{⏟}{ra}} \underset{}{\underset{⏟}{bu}} \underset{“ d a y^{″}}{\underset{⏟}{dhe}}

We will be studying in particular the Ramsey numbers. Starting with the simplest to define:

R (k) = \min {n : every red/blue colouring of E (K_{n}) contains a monochromatic K_{n}} .

Example. $R (3) \leq 6$ : pick a vertex. Without loss of generality say it has at least 3 red neighbours. If any of these are connected by a red edge, then we get a red triangle by using the original vertex. If none of them are connected by a red edge, then we get a blue triangle between them.

$R (3) > 5$ : by considering the following picture.

Thus $R (3) = 6$ .

Main question: how fast does $R (k) \to \infty$ as $k \to \infty$ ?

We will also study:

R (l, k) = \min {n : every red/blue colouring of E (K_{n}) contains either a blue K_{l} or a red K_{k}} .

For a fixed graph $H$ , we define

R (H) = \min {n : every red/blue colouring of E (K_{n}) contains a monochromatic H} .

Example. $R (k) = R (K_{k})$ .

For $H$ a fixed graph, we define

ex (n, H) = \max {e (G) : G is a graph on n vertices and G ⁄ \supset H} .

Example. Mantel’s Theorem says that

ex (n, K_{3}) = ⌊ \frac{n^{2}}{4} ⌋ .

1.1 Binomial Random Graph

Definition 1.1 (Binomial random graph). Given $n \in ℕ$ , $p \in (0, 1)$ , the binomial random graph $G (n, p)$ is the probability space defined on all graphs on $n$ vertices, where each edge is included independently with probability $p$ .

1.2 Topics in this course

First examples: “first moment method”.
$R (3, k)$ :
- deletion method
- Lovász local lemma
- Semi-random method
- Hard core model
- The triangle free process
Dependent random choice:
- Ramsey numbers $R (H)$ with $H$ sparse
- Sidorenko conjecture
- Extremal numbers of bipartite graphs
Pseudo-randomness
- $R (H)$ of bounded-degree graphs
- size-ramsey numbers
- $R (3, 3, k)$
Szemeredi-Regularity lemma
- Roth’s Theorem on 3-term arithmetic progressions in dense sets
- Ramsey-Turán
Method of graph containers:
- Counting graphs with no $C_{4}$
- $R (3, 3, k)$
- $R (4, k)$

1.3 Brief introduction to $R (k)$

Theorem (Erdos-Szekeres, ’35). $R (k) \leq 4^{k}$ .

Proof sketch. Let $n \geq 4^{k}$ and let $χ$ be a colouring of $K_{n}$ . Pick a vertex $v$ . It must have $\geq \frac{1}{2} n$ neighbours connected to it by the same colour.

Now ignore everything that was connected using the other colour. Pick a new vertex from what remains, and apply the process again:

We continue until either $A$ or $B$ gets to size $k$ . We basically just want

n {(\frac{1}{2})}^{k} {(\frac{1}{2})}^{k} \geq 1,

i.e. $n \geq 4^{k}$ . □

How about a lower bound?

Example.

This gives $R (k) \geq {(k - 1)}^{2} + 1$ . Quite a long way from $4^{k}$ !

Theorem (Erdos, ’47). $R (k) \geq (1 - o (1)) \frac{k}{\sqrt{2} e} 2^{k ∕ 2}$ .

Notation. $o (1)$ denotes a quantity that $\to 0$ as $k \to \infty$ .

Proof. Let $n = (1 - o (1)) \frac{k}{\sqrt{2} e} e^{k ∕ 2}$ we choose $χ$ to be a random colouring of $E (K_{n})$ where the colour of each edge is chosen red / blue uniformly and independently. We have

\begin{array}{l} ℙ (χ has a monochromatic K_{k}) & = ℙ (⋃_{K \in {[n]}^{(k)}} {K is a monochromatic clique}) \\ \leq 2 (\binom{n}{k}) 2^{- (\binom{k}{2})} \\ \leq 2 {(\frac{e n}{k})}^{k} 2^{- (\binom{k}{2})} \\ = (\frac{e n}{k} 2^{(\frac{k - 1}{2})}) \\ < 1 \end{array}

by the choice of $n$ . □

Big question: Is there an “explicit” construction that gives $R (k) \geq {(1 + 𝜀)}^{k}$ , for some fixed $𝜀 > 0$ ?

1 Introduction

1.1 Binomial Random Graph

1.2 Topics in this course

1.3 Brief introduction to R(k)

1.3 Brief introduction to $R (k)$