Graph Ramsey Theory · Study tools

Play it yourselfLi–Lin, Ch. 1: Existence

Ramsey's theorem

Colour every edge of $K_6$ red or blue and you cannot avoid a triangle in one colour. Ramsey's theorem says this is not a fluke: for any target, a large enough complete graph forces it. Try to beat the bound yourself before reading the proof.

The idea

Ramsey number.

r(m,n)

is the least

N

such that every red/blue colouring of the edges of

K_N

contains a red

K_m

or a blue

K_n

. Equivalently, every graph on

N

vertices has a clique of size

m

or an independent set of size

n

. More generally

r(G,H)

asks for a red

G

or a blue

H

, and

r_k(G)

uses

k

colours.

Erdős–Szekeres recursion. For

m,n\ge 2

,

r(m,n)\le r(m-1,n)+r(m,n-1), \qquad\text{hence}\qquad r(m,n)\le\binom{m+n-2}{m-1}.

Proof in one line: a vertex $v$ of $K_N$ with $N=r(m-1,n)+r(m,n-1)$ has $N-1$ edges, so by pigeonhole it has at least $r(m-1,n)$ red neighbours or at least $r(m,n-1)$ blue ones. Inside those neighbours, the smaller Ramsey number finds what we need, and $v$ completes it. If both terms on the right are even the inequality is strict, by a parity argument (worked example below).

In particular $r(k,k)\le\binom{2k-2}{k-1}<4^{k-1}$ . The same pigeonhole idea gives multicolour and hypergraph versions.

What is actually known. Exact values are rare:

r(3,3)=6

,

r(3,4)=9

,

r(3,5)=14

,

r(4,4)=18

,

r(4,5)=25

. Already

r(5,5)

is unknown: it lies between 43 and 46 (the upper bound 46 was proved with computer help in 2024; the previous bound, from 2018, was 48).

Explore

Click an edge to colour it: red, then blue, then back to uncoloured. A forbidden pattern lights up as soon as it appears.

Target

Board

Worked example

Prove $r(3,4)\le 9$ . (The board above has a colouring of $K_8$ with no red triangle and no blue $K_4$ , so in fact $r(3,4)=9$ .)

What are $r(2,4)$ and $r(3,3)$ , and what does the recursion give?

$r(2,n)=n$ : a single red edge is a red $K_2$ ; if there is none, all of $K_n$ is blue. With $r(3,3)=6$ the recursion gives $r(3,4)\le r(2,4)+r(3,3)=4+6=10$ .
In a colouring of $K_9$ , suppose some vertex $v$ has at least 4 red edges. Finish the argument.

Look at 4 red neighbours of $v$ . A red edge among them makes a red triangle with $v$ . If there is none, the 4 neighbours span a blue $K_4$ .
Now suppose some vertex has at least 6 blue edges.

Among 6 blue neighbours, $r(3,3)=6$ gives a red triangle (done) or a blue triangle, which together with $v$ is a blue $K_4$ .
If neither case happens, every vertex has at most 3 red and at most 5 blue edges. Why is that impossible in $K_9$ ?

Each vertex has 8 edges, so it has exactly 3 red and 5 blue. Then the red graph is 3-regular on 9 vertices, and its degree sum $9\cdot 3=27$ would be odd. That is impossible, since the degree sum is twice the number of edges. So $r(3,4)\le 9$ .

Check your understanding

A colouring of $K_5$ has no monochromatic triangle. What must its red graph be?

A 5-cycle.
The complete bipartite graph $K_{2,3}$ . $K_{2,3}$ has no triangle, but its complement is a triangle plus an edge, so the blue graph has a triangle.
Any graph with 5 edges.Count each vertex's red edges. What happens if a vertex has 3 red neighbours?

If a vertex had 3 neighbours in one colour, a same-colour edge among them makes a triangle with it, and otherwise they form a triangle in the other colour. So every vertex has exactly 2 red and 2 blue edges: the red graph is 2-regular on 5 vertices with no triangle, which leaves only

C_5

.

Using $r(3,4)=9$ and the recursion, what upper bound do you get for $r(4,4)$ ?

18
20That is the binomial bound $\binom{6}{3}$ . Feed in the known value of $r(3,4)$ instead.
17The parity improvement needs both terms on the right to be even, and 9 is odd.

r(4,4)\le r(3,4)+r(4,3)=9+9=18

. This turns out to be the exact value: module 2 shows a colouring of

K_{17}

with no monochromatic

K_4

.

Someone exhibits a red/blue colouring of $K_{42}$ with no monochromatic $K_5$ . What does this prove?

$r(5,5)\ge 43$ .
$r(5,5)=43$ .One good colouring gives only a lower bound. An upper bound needs a statement about every colouring.
$r(5,5)\le 42$ .A colouring that avoids the pattern shows $K_{42}$ is too small, not big enough.

A colouring with no monochromatic

K_5

shows

K_{42}

does not force one, so

r(5,5)>42

. Lower bounds come from constructions; upper bounds come from arguments that cover all

2^{\binom N2}

colourings.

Practice

Three coloursPigeonhole once more

Show that every colouring of the edges of $K_{17}$ with three colours contains a monochromatic triangle, that is, $r_3(3)\le 17$ .

Hint

A vertex has 16 edges. At least how many share a colour?

Solution

Some colour, say colour 1, appears on at least $\lceil 16/3\rceil=6$ edges at a vertex $v$ . If two of those 6 neighbours are joined in colour 1, we have a triangle with $v$ . Otherwise the 6 neighbours span a $K_6$ coloured with colours 2 and 3 only, and $r(3,3)=6$ gives a monochromatic triangle there. (Module 2 shows 17 is exact.)

The binomial boundInduction

Deduce $r(m,n)\le\binom{m+n-2}{m-1}$ from the recursion.

Hint

Induct on $m+n$ . The base cases are $r(2,n)=n$ and $r(m,2)=m$ . Which identity for binomial coefficients matches the recursion?

Solution

Base: $\binom{n}{1}=n=r(2,n)$ , and similarly for $r(m,2)$ . Step: $r(m,n)\le r(m-1,n)+r(m,n-1)\le\binom{m+n-3}{m-2}+\binom{m+n-3}{m-1}=\binom{m+n-2}{m-1}$ by Pascal's rule.

More practice: Li–Lin, Exercises 1.2, 1.6 and 1.9.

InteractiveLi–Lin, Ch. 2: Small Ramsey Numbers

Paley graphs and small values

Upper bounds come from counting. Lower bounds need an explicit colouring, and the best small ones come from finite fields. The Paley graph on 17 vertices proves $r(4,4)>17$ , and with the bound from module 1 that settles $r(4,4)=18$ .

The idea

Paley graph. Let

q

be a prime power with

q\equiv1\pmod 4

. The Paley graph

P_q

has vertex set the field

\mathbb F_q

, with

x\sim y

when

x-y

is a nonzero square. Since

-1

is a square when

q\equiv1\pmod4

, this relation is symmetric. Every vertex has

(q-1)/2

neighbours.

Self-complementary. If

a

is a non-square, the map

x\mapsto ax

sends squares to non-squares, so it maps

P_q

onto its complement. Hence

\omega(P_q)=\alpha(P_q)

, and colouring edges of

P_q

red and non-edges blue gives

r(\omega+1,\omega+1)>q

.

For $q=17$ the squares mod 17 are $\{1,2,4,8,9,13,15,16\}$ , and $\omega(P_{17})=3$ . So $r(4,4)>17$ ; together with $r(4,4)\le18$ this gives $r(4,4)=18$ .

Schur numbers. A set of integers is sum-free if

x+y

is never in it when

x,y

are (

x=y

allowed). The Schur number

s_k

is the largest

N

such that

\{1,\dots,N\}

splits into

k

sum-free sets. Known:

s_1=1,\ s_2=4,\ s_3=13,\ s_4=44

, and

s_5=160

(by computer, 2017).

Schur meets Ramsey.

r_k(3)\ge s_k+2

. Also

r_3(3)=17

: Greenwood and Gleason coloured

K_{16}

on

\mathbb F_{16}

by sending the edge

xy

to the coset of the cubes that contains

x-y

; each coset is sum-free.

Explore

Vertex

x

sits at position

x

around the circle. Click vertices to build a set; it is checked as you go.

Field size q

Draw

Worked example

Show that $s_2=4$ , and turn that into the lower bound $r(3,3)\ge 6$ .

Split $\{1,2,3,4\}$ into two sum-free sets.

$\{1,4\}$ and $\{2,3\}$ . Sums within the first: $2,5,8$ ; within the second: $4,5,6$ . None lands back in the same set.
Why can $\{1,\dots,5\}$ not be split this way?

Put 1 in $A$ . Then $2=1+1\notin A$ , so $2\in B$ , and $4=2+2\notin B$ , so $4\in A$ . Now $3\notin A$ (since $1+3=4$ ), so $3\in B$ . Finally $5=1+4$ rules out $A$ and $5=2+3$ rules out $B$ .
Given a sum-free split of $\{1,\dots,N\}$ into $k$ classes, colour $K_{N+1}$ on vertices $0,\dots,N$ by giving edge $ij$ the class of $|i-j|$ . Why is there no monochromatic triangle?

For a triangle $i<j<l$ the three differences are $a=j-i$ , $b=l-j$ and $a+b=l-i$ . If all three had the same class, that class would contain $a$ , $b$ and $a+b$ , so it would not be sum-free.
What do you get for $k=2$ and $k=3$ ?

So $r_k(3)>s_k+1$ . With $s_2=4$ : a good colouring of $K_5$ (it is the pentagon), so $r(3,3)\ge6$ . With $s_3=13$ : $r_3(3)\ge15$ , which is weaker than the true value 17, found with $\mathbb F_{16}$ instead.

Check your understanding

Why does the Paley construction need $q\equiv 1\pmod 4$ ?

So that $-1$ is a square, which makes " $x-y$ is a square" symmetric in $x$ and $y$ .
So that $q$ is prime. $q$ may be any prime power, such as 9 or 25. The condition is about $-1$ .
So that the graph has an even number of vertices. $q\equiv1\pmod4$ makes $q$ odd.

y-x=(-1)(x-y)

, so if

-1

is a square,

x-y

and

y-x

are squares together. In

\mathbb F_q

with

q

odd,

-1

is a square exactly when

q\equiv1\pmod4

.

$P_{13}$ has $\omega=\alpha=3$ . What does it tell you about $r(4,4)$ ?

$r(4,4)>13$ , weaker than what $P_{17}$ gives.
$r(4,4)=14$ .A single graph only ever gives a lower bound.
Nothing, because 13 is prime and 17 is needed.Any graph with no $K_4$ and no independent 4-set gives a lower bound. Check what this one gives.

Colour edges of

P_{13}

red and non-edges blue: there is no monochromatic

K_4

, so

K_{13}

does not force one.

P_{17}

does the same on more vertices, which is why it is the one that matches the upper bound.

In the explorer, select a triangle in $P_{17}$ and press "Multiply by a non-square". What do you get, and why?

An independent set of size 3, because $x\mapsto ax$ turns every square difference into a non-square one.
Another triangle, because multiplication is an automorphism.Multiplying by a square is an automorphism. A non-square swaps edges and non-edges.
A set of size 6.The map is a bijection on vertices, so the size is preserved.

ax-ay=a(x-y)

, and a non-square times a nonzero square is a non-square. So cliques become independent sets of the same size and vice versa, which is why

\omega(P_q)=\alpha(P_q)

.

Practice

Symmetry of Paley graphsAutomorphisms

Show that any two edges of $P_q$ have the same number of common neighbours.

Hint

Which maps $x\mapsto ax+b$ are automorphisms? Can one of them send the edge $\{0,1\}$ to any given edge?

Solution

If $a$ is a nonzero square, $\phi(x)=ax+b$ is an automorphism, since $\phi(x)-\phi(y)=a(x-y)$ is a square exactly when $x-y$ is. For an edge $\{u,v\}$ , take $a=v-u$ (a square) and $b=u$ : then $\phi(0)=u$ and $\phi(1)=v$ . Automorphisms preserve common neighbourhoods, so every edge has as many common neighbours as $\{0,1\}$ .

A triangle-free graph on 13 verticesSum-free connection sets

On $\mathbb Z_{13}$ , join $x$ and $y$ when $x-y\in S=\{1,5,8,12\}$ . Show this graph has no triangle. (A computer check shows its independence number is 4, so it proves $r(3,5)\ge14$ ; in fact $r(3,5)=14$ .)

Hint

A triangle $\{x,x+a,x+a+b\}$ needs $a$ , $b$ and $a+b$ all in $S$ .

Solution

$S$ is closed under negation, so the graph is well defined, and a triangle needs $a,b\in S$ with $a+b\in S$ . The sums mod 13 of pairs from $S$ are $2,6,9,0,10,0,4,3,7,11$ , none of which lies in $S$ . So there is no triangle.

More practice: Li–Lin, Exercises 2.1, 2.3 and 2.6.

SimulationLi–Lin, Ch. 3: Basic Probabilistic Method

Random colourings

Nobody knows how to write down a colouring of $K_n$ with no monochromatic $K_k$ when $n$ is close to $2^{k/2}$ . Erdős showed in 1947 that a random colouring does the job with positive probability. The proof never says which colouring works.

The idea

Colour each edge of $K_n$ red or blue independently, with probability $\tfrac12$ each. A fixed $k$ -set of vertices is monochromatic with probability $2\cdot 2^{-\binom k2}$ . If $X$ counts the monochromatic $k$ -sets, linearity of expectation gives

\mathbb E X=\binom nk\,2^{1-\binom k2}.

Erdős's bound. If

\binom nk 2^{1-\binom k2}<1

, then

r(k,k)>n

. Taking

n=\lfloor 2^{k/2}\rfloor

shows

r(k,k)>2^{k/2}

for all

k\ge3

.

The reason: $X$ is a whole number and its average is below 1, so some colouring has $X=0$ .

Deletion. For every

n

,

r(k,k)>n-\binom nk 2^{1-\binom k2}

. Some colouring has at most

\mathbb E X

monochromatic

k

-sets; delete one vertex from each.

Two tools used all the time. Markov's inequality:

\Pr(X\ge a)\le \mathbb E X/a

for

X\ge0

. Linearity:

\mathbb E(X+Y)=\mathbb EX+\mathbb EY

, with no independence needed.

The same chapter bounds independence numbers: every graph has $\alpha(G)\ge\sum_v \frac{1}{d(v)+1}$ (the worked example).

Explore

red blue · vertices with a ring are deleted to kill every monochromatic

K_k

; the rest are shown in teal.

Clique size k 4 Vertices n 12

Worked example

Prove that every graph $G$ has $\alpha(G)\ge\sum_{v}\frac1{d(v)+1}$ (Caro–Wei), and deduce Turán's theorem from it.

Order the vertices uniformly at random. Let $I$ be the set of vertices that come before all of their neighbours. Why is $I$ independent?

If $u,v\in I$ were adjacent, $u$ would come before $v$ and $v$ before $u$ .
What is $\Pr(v\in I)$ ?

Only the relative order of $v$ and its $d(v)$ neighbours matters, and each of these $d(v)+1$ vertices is equally likely to come first. So $\Pr(v\in I)=\frac{1}{d(v)+1}$ .
Finish the bound.

$\mathbb E|I|=\sum_v\frac1{d(v)+1}$ by linearity, so some ordering gives an independent set at least this large.
Deduce: a graph on $n$ vertices with no $K_{r+1}$ has at most $(1-\frac1r)\frac{n^2}{2}$ edges.

$x\mapsto\frac1{x+1}$ is convex, so by Jensen $\alpha(H)\ge\frac{n}{\bar d+1}$ for any $H$ with average degree $\bar d$ . Apply this to the complement $\bar G$ : a clique in $G$ is an independent set in $\bar G$ , so $r\ge\alpha(\bar G)\ge\frac{n}{\bar d_{\bar G}+1}$ . Hence $\bar d_{\bar G}\ge\frac nr-1$ and $\bar d_G=n-1-\bar d_{\bar G}\le n-\frac nr$ . So $e(G)=\frac{n\bar d_G}{2}\le(1-\frac1r)\frac{n^2}2$ . Module 7 returns to this.

Check your understanding

For $k=4$ and $n=6$ , $\mathbb E X=\binom64 2^{-5}=15/32$ . What follows?

Some colouring of $K_6$ has no monochromatic $K_4$ , so $r(4,4)>6$ .
Every colouring of $K_6$ has no monochromatic $K_4$ .An average below 1 guarantees some colouring with $X=0$ , not that all have it.
A random colouring has a monochromatic $K_4$ with probability exactly $15/32$ .Markov gives $\Pr(X\ge1)\le 15/32$ . Equality would need $X\le1$ always.

X

takes whole-number values with mean below 1, so

\Pr(X=0)>0

. Here Markov even gives

\Pr(X=0)\ge 17/32

.

Two 4-sets that share an edge are not independent events. Why is $\mathbb EX=\binom nk 2^{1-\binom k2}$ still right?

Linearity of expectation holds for any random variables, dependent or not.
Because the overlaps are rare enough to ignore.The formula is exact for every $n$ , not an approximation.
It isn't; the formula is an upper bound.Write $X$ as a sum of indicator variables and take expectations term by term.

X=\sum_S \mathbf 1[S\text{ mono}]

and

\mathbb E

of a sum is the sum of the

\mathbb E

's, always. Dependence matters for the variance, not the mean.

For some $k$ and $n=40$ , $\mathbb E X=6.2$ . What does deletion give?

$r(k,k)>34$ .
$r(k,k)>40$ .That needs $\mathbb EX<1$ . Here typical colourings do have monochromatic $k$ -sets.
Nothing, because $\mathbb E X>1$ .Some colouring has at most 6 bad sets. What can you remove?

Some colouring has

X\le 6.2

, and

X

is a whole number, so

X\le6

. Remove one vertex from each bad set: at least 34 vertices remain with no monochromatic

K_k

.

Practice

The

2^{k/2}

boundChecking the inequality

Show that $n=\lfloor2^{k/2}\rfloor$ satisfies $\binom nk2^{1-\binom k2}<1$ for $k\ge3$ .

Hint

Use $\binom nk\le n^k/k!$ and $n^k\le 2^{k^2/2}$ .

Solution

$\binom nk2^{1-\binom k2}\le\frac{2^{k^2/2}}{k!}\,2^{1-k^2/2+k/2}=\frac{2^{1+k/2}}{k!}$ . For $k=3$ this is $2^{2.5}/6\approx0.94<1$ , and going from $k$ to $k+1$ multiplies it by $\sqrt2/(k+1)<1$ .

Half the edges are bipartiteA one-line expectation

Show that every graph with $m$ edges has a bipartite subgraph with at least $m/2$ edges.

Hint

Put each vertex on the left or right at random. When does an edge cross?

Solution

Each edge crosses with probability $\tfrac12$ , so the expected number of crossing edges is $m/2$ , and some split achieves at least that. The crossing edges form a bipartite subgraph.

More practice: Li–Lin, Exercises 3.6 and 3.7.

Animated lessonLi–Lin, Ch. 4: Random Graph

The random graph process

Start with $n$ isolated vertices and add random edges one at a time. Properties do not appear gradually: each one shows up suddenly, near an edge count you can predict with a short expectation calculation.

The idea

The model.

G(n,p)

has vertex set

\{1,\dots,n\}

, and each of the

\binom n2

edges is present independently with probability

p

. A property holds asymptotically almost surely (a.a.s.) if its probability tends to 1 as

n\to\infty

. The process that adds edges in random order behaves at

m

edges like

G(n,p)

with

p=m/\binom n2

.

Threshold.

p^*(n)

is a threshold for an increasing property

Q

if

\Pr(G(n,p)\in Q)\to0

when

p/p^*\to0

and

\to1

when

p/p^*\to\infty

.

Three thresholds.

Triangles: threshold $1/n$ . At $p=c/n$ the number of triangles is approximately Poisson with mean $c^3/6$ .
Giant component: at $p=c/n$ , if $c<1$ every component has $O(\log n)$ vertices; if $c>1$ there is a unique component with a constant fraction of the vertices.
Connectivity: at $p=(\ln n+c)/n$ , $\Pr(\text{connected})\to e^{-e^{-c}}$ . The last obstacle is an isolated vertex.

Random graphs are also where Ramsey lower bounds come from: taking $G(N,p)$ with a well-chosen $p$ and deleting a vertex from each triangle shows $r(3,n)\ge c\,(n/\log n)^{3/2}$ . The true order, $n^2/\log n$ , is due to Kim and to Ajtai, Komlós and Szemerédi.

Watch

largest component other components with a cycle isolated vertices

50 isolated vertices. Edges will arrive in a uniformly random order.
Up to $m=n/4$ edges ( $p\approx\tfrac{1}{2n}$ ): a scattering of small trees. Cycles are unlikely this early.
Up to $m=n/2$ ( $p\approx 1/n$ ): the critical point. Cycles start to appear, and components merge quickly.
Up to $m=n$ ( $p\approx2/n$ ): one component swallows most of the others. This is the giant component.
Up to $m\approx\tfrac n2\ln n$ ( $p\approx\ln n/n$ ): the last isolated vertices get their first edge, and the graph becomes connected around here.
Beyond the threshold: connected, with plenty of triangles. Press "New random graph" and replay to see how much these moments vary for $n=50$ .

Worked example

Let $X$ be the number of triangles in $G(n,p)$ . Show that $1/n$ is a threshold for $X\ge1$ .

Compute $\mathbb EX$ .

Each of the $\binom n3$ triples is a triangle with probability $p^3$ , so $\mathbb EX=\binom n3p^3\sim (np)^3/6$ .
Suppose $np\to0$ . Why is there a.a.s. no triangle?

Markov: $\Pr(X\ge1)\le\mathbb EX\sim(np)^3/6\to0$ .
Suppose $np\to\infty$ . Then $\mathbb EX\to\infty$ , but that alone is not enough. Bound $\operatorname{Var}X$ .

Write $X=\sum_T X_T$ . Triples sharing at most one vertex share no edge, so they are independent and contribute nothing to the covariance. Pairs sharing an edge span 4 vertices and 5 edges: there are $O(n^4)$ of them, each with $\operatorname{Cov}\le p^5$ . So $\operatorname{Var}X\le \mathbb EX+O(n^4p^5)$ .
Finish with Chebyshev.

$\Pr(X=0)\le\frac{\operatorname{Var}X}{(\mathbb EX)^2}\le\frac{1}{\mathbb EX}+O\!\left(\frac{n^4p^5}{n^6p^6}\right)=O\!\left(\frac{1}{(np)^3}\right)+O\!\left(\frac{1}{n^2p}\right)\to0.$

Between the two regimes, at $p=c/n$ , $X$ is approximately Poisson with mean $c^3/6$ , so $\Pr(X=0)\to e^{-c^3/6}$ .

Check your understanding

About how many triangles do you expect in $G(n,1/n)$ for large $n$ ?

About $1/6$ .
About $n/6$ .Compute $\binom n3p^3$ with $p=1/n$ : the powers of $n$ cancel.
About 1.You are close. Remember $\binom n3\approx n^3/6$ .

\binom n3 n^{-3}\to 1/6

. So at

p=1/n

a triangle is present with probability about

1-e^{-1/6}\approx 0.15

: right at the threshold, neither likely nor negligible.

At $p=\ln n/n$ , how many isolated vertices do you expect?

About 1.
About 0.Compute $n(1-p)^{n-1}\approx n e^{-pn}$ .
About $\ln n$ .The exponential $e^{-pn}=1/n$ cancels the factor $n$ exactly.

n(1-p)^{n-1}\approx ne^{-\ln n}=1

. Shifting

p

to

(\ln n+c)/n

makes the mean

e^{-c}

, and the count is approximately Poisson, which is where

e^{-e^{-c}}

comes from.

If $\mathbb EX\to\infty$ , must $\Pr(X\ge1)\to1$ ?

No. $X$ could be huge on a rare event and 0 otherwise, so a second-moment bound is needed.
Yes, by Markov's inequality.Markov bounds $\Pr(X\ge a)$ from above. It says nothing about $X$ being positive.
Yes, because $X$ is a sum of many indicators.Indicators can be strongly correlated, for example all equal to one event of small probability.

Take

X=n^2

with probability

1/n

and

X=0

otherwise:

\mathbb EX=n\to\infty

but

\Pr(X\ge1)\to0

. Chebyshev with

\operatorname{Var}X=o((\mathbb EX)^2)

rules this out.

Practice

When does

K_4

appear?Same method, new numbers

Find the threshold for $G(n,p)$ to contain a $K_4$ .

Hint

$\mathbb E(\#K_4)=\binom n4p^6$ . Where is it of constant order? Check that no subgraph of $K_4$ is denser than $K_4$ itself.

Solution

$\binom n4p^6\asymp n^4p^6$ , which is of constant order at $p=n^{-2/3}$ . Below it Markov gives no $K_4$ . Above it, the second moment works because every subgraph $F$ of $K_4$ has $e(F)/v(F)\le 6/4$ , so no smaller piece appears later than $K_4$ itself. The threshold is $n^{-2/3}$ .

No isolated verticesFirst moment

Show that at $p=2\ln n/n$ , $G(n,p)$ a.a.s. has no isolated vertex.

Solution

The expected number of isolated vertices is $n(1-p)^{n-1}\le n e^{-p(n-1)}=n\cdot n^{-2(n-1)/n}=n^{-1+2/n}\to0$ . By Markov, a.a.s. there are none.

More practice: Li–Lin, Exercises 4.10 and 4.12.

CalculatorLi–Lin, Ch. 5: Lovász Local Lemma

The local lemma

The union bound needs the bad events' probabilities to add up to less than 1. The Lovász Local Lemma needs much less: if each bad event depends on only a few others, all of them can be avoided at once, however many there are. For Ramsey numbers this gains a constant factor over Erdős's bound.

The idea

Dependency graph. Events

A_1,\dots,A_N

have a dependency graph

D

if each

A_i

is mutually independent of the family

\{A_j: j\ne i,\ ij\notin D\}

. Typical case: each event is determined by a set of independent coin flips, and

i\sim j

when the two sets overlap.

Symmetric local lemma. If

\Pr(A_i)\le p

for all

i

, every vertex of

D

has degree at most

d

, and

e\,p\,(d+1)\le1,

then $\Pr\big(\bigcap_i\overline{A_i}\big)>0$ : with positive probability no bad event happens.

For $r(k,k)$ : colour $K_n$ at random and let $A_S$ be the event that the $k$ -set $S$ is monochromatic, so $p=2^{1-\binom k2}$ . $A_S$ depends only on the edges inside $S$ , so it is independent of all $A_T$ with $|S\cap T|\le1$ . The number of other $T$ with $|S\cap T|\ge2$ is

d=\sum_{i=2}^{k-1}\binom ki\binom{n-k}{k-i}.

Three lower bounds, compared. As

k\to\infty

,

\text{union: } \tfrac{1}{e\sqrt2}\,k2^{k/2},\qquad \text{deletion: } \tfrac1e\,k2^{k/2},\qquad \text{local lemma (Spencer): } \tfrac{\sqrt2}{e}\,k2^{k/2},

each up to a factor $1+o(1)$ . Nothing better than $\sqrt2^{\,k}$ in the exponent is known. The same chapter uses the local lemma for $r(3,n)\ge c(n/\log n)^2$ , and the triangle-free process improves this to $(\tfrac14-o(1))\,n^2/\log n$ .

Explore

Each bound divided by

k2^{k/2}

. Dashed lines: the limits

1/(e\sqrt2)

,

1/e

and

\sqrt2/e

. union deletion local lemma

Clique size k 10

Worked example

A hypergraph is 2-colourable if its vertices can be coloured red and blue with no edge monochromatic. Show: if every edge has exactly $k$ vertices and meets at most $d$ other edges, and $e(d+1)2^{1-k}\le1$ , then the hypergraph is 2-colourable.

Set up the random experiment and the bad events.

Colour each vertex red or blue independently with probability $\tfrac12$ . For each edge $f$ , let $A_f$ be the event that $f$ is monochromatic.
What is $\Pr(A_f)$ ?

All red or all blue: $2\cdot2^{-k}=2^{1-k}$ .
Find a dependency graph with maximum degree $d$ .

$A_f$ is determined by the colours on $f$ . The events $A_g$ with $g\cap f=\varnothing$ are determined by colours off $f$ , so $A_f$ is mutually independent of all of them together. Joining $f$ to the edges it meets gives degree at most $d$ .
Conclude, and compare with the union bound for $k=10$ .

The local lemma applies, so with positive probability no edge is monochromatic. For $k=10$ the condition is $e(d+1)\le512$ , that is $d\le187$ , with no limit at all on the total number of edges. The union bound would need fewer than $2^{9}=512$ edges in total.

Check your understanding

Why is the event " $S$ is monochromatic" independent of all the events " $T$ is monochromatic" with $|S\cap T|\le1$ ?

Such a $T$ shares no edge with $S$ , so those events depend only on edges outside $S$ .
Because such a $T$ shares no vertex with $S$ . $T$ may share one vertex. What do the events actually depend on?
Because each event has small probability.Small probability says nothing about independence.

Two vertices are needed to share an edge. The colours of edges are independent, so events determined by disjoint sets of edges are independent, even as a whole family.

Asymptotically, Spencer's local lemma bound for $r(k,k)$ is how many times Erdős's union bound?

2
$\sqrt2$ That is the gain over the deletion method, not over the union bound.
$e$ Divide the two constants: $\frac{\sqrt2}{e}\big/\frac1{e\sqrt2}$ .

\frac{\sqrt2/e}{1/(e\sqrt2)}=2

. The improvement is only a constant factor. For moderate

k

the convergence is slow: the calculator shows deletion doing at least as well as the local lemma for every

k\le16

.

If the events are fully independent ( $d=0$ ), the condition reads $ep\le1$ . Is that what independent events actually need?

No. Independent events, each with probability below 1, can all be avoided, since $\prod(1-p_i)>0$ .
Yes, the local lemma is exact when $d=0$ .Try $p=\tfrac12$ with two independent events.
No, they need $\sum p_i<1$ .That is the union bound, which is only a sufficient condition.

The factor

e

is the price of handling arbitrary dependencies with one clean condition. With

d=0

the product formula is exact and much weaker conditions suffice.

Practice

Regular uniform hypergraphsCount the dependencies

Show that every $k$ -uniform hypergraph in which each vertex lies in exactly $k$ edges is 2-colourable once $k\ge9$ .

Hint

Each edge has $k$ vertices, each in $k-1$ other edges.

Solution

An edge meets at most $d=k(k-1)$ others. For $k=9$ : $e(d+1)2^{1-k}=e\cdot73/256\approx0.78\le1$ , so the worked example applies. For larger $k$ the left side only shrinks, since $k(k-1)+1$ grows polynomially while $2^{k-1}$ doubles.

Satisfiable formulasThe same lemma, in logic

A $k$ -CNF formula has clauses of exactly $k$ distinct literals. Show that if each clause shares a variable with at most $2^k/e-1$ other clauses, the formula is satisfiable.

Solution

Set each variable true or false at random. A clause fails with probability $2^{-k}$ (all $k$ literals false), and its failure depends only on its own variables. With $d\le 2^k/e-1$ we get $ep(d+1)\le e2^{-k}\cdot2^k/e=1$ , so with positive probability no clause fails.

More practice: Li–Lin, Exercises 5.2 and 5.5.

Build it yourselfLi–Lin, Ch. 6: Constructive Lower Bounds

Explicit Ramsey graphs

Random colourings beat every explicit construction anyone knows. Still, explicit graphs exist whose cliques and independent sets can be bounded by linear algebra. Here is the simplest one: its vertices are triples, and you can try to build a large clique or independent set by hand.

The idea

Oddtown theorem. If

\mathcal F

is a family of subsets of

\{1,\dots,t\}

, each of odd size, and any two distinct members meet in an even number of elements, then

|\mathcal F|\le t

.

Fisher-type inequality. If distinct subsets of

\{1,\dots,t\}

pairwise meet in exactly

\lambda\ge1

elements, there are at most

t

of them.

The graph. Let

N_t

have the

\binom t3

three-element subsets of

\{1,\dots,t\}

as vertices, with

A\sim B

when

|A\cap B|=1

.

A clique is a family of triples meeting pairwise in exactly one point: at most $t$ by Fisher. An independent set is a family of triples meeting pairwise in 0 or 2 points, an even number: at most $t$ by Oddtown. So

r(t+1,t+1)>\binom t3.

That is only polynomial in $t$ , against Erdős's exponential $2^{t/2}$ . Frankl and Wilson replaced "intersection 1" by conditions on intersections modulo a prime and got explicit graphs with cliques and independent sets of size $e^{c\sqrt{\log n\log\log n}}$ on $n$ vertices. The same intersection theorems disproved Borsuk's conjecture: Kahn and Kalai found bounded sets in $\R^d$ that cannot be split into fewer than $1.2^{\sqrt d}$ pieces of smaller diameter.

Explore

Each chip is a vertex of

N_t

. Click chips to choose a family of triples. A pair that breaks the pattern is outlined in red.

Ground set size t

Worked example

Prove the Oddtown theorem.

Turn each set into a vector. Over which field?

Over $\mathbb F_2$ : let $v_A\in\mathbb F_2^t$ be the indicator vector of $A$ . Then $v_A\cdot v_B=|A\cap B|\bmod 2$ .
What are $v_A\cdot v_A$ and $v_A\cdot v_B$ for $A\ne B$ ?

$v_A\cdot v_A=|A|\equiv1$ since sizes are odd, and $v_A\cdot v_B=|A\cap B|\equiv0$ since intersections are even.
Show the vectors are linearly independent.

If $\sum_A c_Av_A=0$ , take the dot product with $v_B$ : every term vanishes except $c_B\,v_B\cdot v_B=c_B$ . So every $c_B=0$ .
Conclude.

Linearly independent vectors in $\mathbb F_2^t$ number at most $t$ , so $|\mathcal F|\le t$ . For triples, an independent set of $N_t$ is such a family, so $\alpha(N_t)\le t$ .

Check your understanding

Which family is a clique in $N_t$ ?

The seven lines of the Fano plane, such as $\{1,2,3\},\{1,4,5\},\{2,4,6\},\dots$
All triples containing the element 1. $\{1,2,3\}$ and $\{1,2,4\}$ share two elements, so they are not adjacent.
The four triples inside $\{1,2,3,4\}$ .These meet pairwise in two elements. That makes them independent, not a clique.

Any two lines of the Fano plane meet in exactly one point. That gives a clique of size 7 in

N_7

, so Fisher's bound

t

is attained there. Try the button in the explorer.

Oddtown needs odd set sizes. What goes wrong with even sizes and even intersections?

$v_A\cdot v_A$ becomes 0 and the independence argument fails; indeed there can be $2^{\lfloor t/2\rfloor}$ such sets.
Nothing; the same bound $t$ holds.Try all unions of the pairs $\{1,2\},\{3,4\},\dots$
The vectors no longer live in $\mathbb F_2^t$ .They still do. Look at which dot product changes.

Unions of the disjoint pairs

\{1,2\},\{3,4\},\dots

all have even size and even intersections:

2^{\lfloor t/2\rfloor}

sets ("Eventown"). The diagonal entries of the Gram matrix are what make the odd case linear in

t

.

$N_t$ gives $r(t+1,t+1)>\binom t3$ , and Erdős gives $r(t+1,t+1)>2^{(t+1)/2}$ . For $t=10$ , $\binom{10}{3}=120$ beats $2^{5.5}\approx45$ . What happens as $t$ grows?

Erdős's bound wins for every $t\ge19$ : it is exponential, $\binom t3$ is cubic.
$N_t$ stays ahead, because explicit graphs are better than random ones.Compare growth rates: $t^3/6$ against $2^{t/2}$ .
They stay within a constant factor of each other.The ratio $2^{t/2}/t^3$ tends to infinity.

At

t=18

:

816

against

2^{9.5}\approx724

; at

t=19

:

969

against

1024

. From then on the exponential wins by more and more. Erdős asked for an explicit construction giving

(1+\epsilon)^t

; none is known.

Practice

The clique boundA positive definite Gram matrix

Show directly that a family of triples in $\{1,\dots,t\}$ meeting pairwise in exactly one element has at most $t$ members.

Hint

Use real indicator vectors this time. What is their Gram matrix?

Solution

With real vectors, $v_A\cdot v_A=3$ and $v_A\cdot v_B=1$ , so the Gram matrix is $2I+J$ , which is positive definite (its eigenvalues are 2 and $2+m$ ). A positive definite Gram matrix means the vectors are linearly independent in $\R^t$ , so there are at most $t$ .

TetrahedraAn independent set of size t

When $4\mid t$ , find an independent set of size exactly $t$ in $N_t$ , so the Oddtown bound is attained.

Solution

Split $\{1,\dots,t\}$ into blocks of 4 and take all four triples inside each block. Triples in the same block meet in 2 elements and triples in different blocks are disjoint, so every intersection is even. There are $4\cdot t/4=t$ triples. The "Tetrahedra" button in the explorer shows this for $t=8$ .

More practice: Li–Lin, Exercises 6.3 and 6.4.

InteractiveLi–Lin, Ch. 7: Turán Number and Related Ramsey Number

Turán numbers

How many edges can a graph on $n$ vertices have without containing a $K_{r+1}$ ? Split the vertices into $r$ parts as equally as possible and join every pair in different parts. Drag vertices between parts to see why equal parts are best.

The idea

Turán number.

\mathrm{ex}(n,H)

is the largest number of edges in an

n

-vertex graph with no copy of

H

. The Turán graph

T(n,r)

is the complete

r

-partite graph with part sizes

\lfloor n/r\rfloor

or

\lceil n/r\rceil

.

Turán's theorem.

\mathrm{ex}(n,K_{r+1})=e(T(n,r))\le\left(1-\frac1r\right)\frac{n^2}2

, and

T(n,r)

is the only extremal graph.

Erdős–Stone–Simonovits.

\mathrm{ex}(n,H)=\left(1-\frac1{\chi(H)-1}+o(1)\right)\frac{n^2}2

. The chromatic number decides the answer to first order.

For bipartite $H$ that first-order answer is $o(n^2)$ , and the real question is the exponent. Kővári, Sós and Turán: $\mathrm{ex}(n,K_{s,t})=O(n^{2-1/s})$ for $s\le t$ . For $C_4=K_{2,2}$ the order $n^{3/2}$ is right: the Erdős–Rényi polarity graph, built from the projective plane over $\mathbb F_q$ , has $q^2+q+1$ vertices, no $C_4$ , and about $\tfrac12q^3$ edges.

Why Ramsey cares. In a $k$ -colouring of $K_N$ some colour has at least $\binom N2/k$ edges. If that exceeds $\mathrm{ex}(N,H)$ , that colour contains $H$ . Bipartite Turán numbers therefore bound multicolour Ramsey numbers, such as $r_k(C_4)=O(k^2)$ .

Explore

All edges between different parts are drawn. Drag a vertex into another part. A complete

r

-partite graph never contains

K_{r+1}

: two of any

r+1

vertices share a part.

Vertices n 12 Parts r 3

Worked example

Show that a graph on $n$ vertices with no 4-cycle has at most $\frac n4\big(1+\sqrt{4n-3}\big)$ edges.

Count "cherries": pairs of edges $vx, vy$ at a common vertex $v$ . How many are there in terms of degrees?

$\sum_v\binom{d(v)}{2}$ : choose the centre $v$ , then two of its neighbours.
Why is this at most $\binom n2$ when there is no $C_4$ ?

Each cherry has a pair of endpoints $\{x,y\}$ . If two cherries had the same endpoints and different centres $v\ne w$ , then $x,v,y,w$ would be a 4-cycle. So each pair $\{x,y\}$ is used at most once.
Use convexity to bring in the average degree $\bar d=2e/n$ .

$x\mapsto\binom x2$ is convex, so $n\binom{\bar d}{2}\le\sum_v\binom{d(v)}2\le\binom n2$ , that is $\bar d(\bar d-1)\le n-1$ .
Solve for $e$ .

$\bar d\le\frac{1+\sqrt{4n-3}}2$ , so $e=\frac{n\bar d}{2}\le\frac n4\big(1+\sqrt{4n-3}\big)\approx\tfrac12n^{3/2}$ . The polarity graph shows the constant $\tfrac12$ cannot be improved.

Check your understanding

To first order, what is $\mathrm{ex}(n,C_5)$ ?

$n^2/4$
$o(n^2)$ That holds for bipartite graphs. Is $C_5$ bipartite?
$n^2/3$ $\chi(C_5)=3$ , so the formula gives $1-\frac12$ , not $1-\frac13$ .

\chi(C_5)=3

gives

\big(1-\tfrac12\big)\tfrac{n^2}2=\tfrac{n^2}4

. The complete bipartite graph

K_{n/2,n/2}

has no odd cycle at all, and Erdős–Stone says you cannot do much better.

In a complete multipartite graph, you move one vertex from a part of size 7 to a part of size 4. How does the number of edges change?

It goes up by 2.
It goes up by 3.The moved vertex belongs to its new part too, so that part then has 5 vertices, not 4.
It stays the same.Only its own edges change. Count its neighbours before and after.

Before, the vertex is adjacent to everything outside its part:

n-7

vertices. After, to

n-5

(its new part has

4+1

vertices). The gain is

2=7-4-1

. In general moving from size

a

to size

b

changes the count by

a-b-1

, which is positive whenever

a\ge b+2

. That is why balanced parts are optimal.

A graph on $n$ vertices has no 4-cycle. Roughly how large can its average degree be?

About $\sqrt n$ .
About $n/2$ . $K_{n/2,n/2}$ has average degree $n/2$ but is full of 4-cycles.
Bounded by a constant.The polarity graph has degrees about $\sqrt n$ and no $C_4$ .

The worked example gives

\bar d(\bar d-1)\le n-1

, so

\bar d\lesssim\sqrt n

, and the polarity graph attains this order.

Practice

Mantel's theoremTurán for triangles, by Cauchy–Schwarz

Show that a triangle-free graph on $n$ vertices has at most $n^2/4$ edges.

Hint

For an edge $xy$ , the neighbourhoods of $x$ and $y$ are disjoint. Sum $d(x)+d(y)$ over all edges.

Solution

Disjoint neighbourhoods give $d(x)+d(y)\le n$ for each edge. Summing over edges, each vertex $v$ appears $d(v)$ times, so $\sum_v d(v)^2\le ne$ . By Cauchy–Schwarz, $\sum_vd(v)^2\ge(2e)^2/n$ . Hence $4e^2/n\le ne$ , so $e\le n^2/4$ .

Many colours, one 4-cycleTurán meets Ramsey

Use the worked example to show that every $k$ -colouring of the edges of $K_N$ with $N=k^2+k+2$ contains a monochromatic $C_4$ .

Hint

Some colour class has at least $\binom N2/k$ edges. Compare with $\frac N4(1+\sqrt{4N-3})$ .

Solution

It suffices that $\binom N2/k>\frac N4(1+\sqrt{4N-3})$ , that is $\frac{2(N-1)}{k}>1+\sqrt{4N-3}$ . With $N-1=k^2+k+1$ the left side is $2k+2+\frac2k$ . On the right, $4N-3=(2k+1)^2+4$ , so $\sqrt{4N-3}<2k+1+\frac{2}{2k+1}$ , and the right side is less than $2k+2+\frac{2}{2k+1}<2k+2+\frac2k$ . So $r_k(C_4)\le k^2+k+2$ .

More practice: Li–Lin, Exercises 7.4 and 7.5.

Build it yourselfLi–Lin, Ch. 8: Communication Channels

Shannon capacity

A channel sends one of five letters, and each letter can be received as itself or as a neighbour around a pentagon. With single letters you can send only 2 messages with no risk of confusion. With two-letter words you can send 5, not 4. That 5 is $r(3,3)-1$ , and the coincidence is a theorem.

The idea

Confusability graph. Letters are vertices, joined when they can be confused. A zero-error code of single letters is an independent set, so it has at most

\alpha(G)

words.

Strong product. In

G\boxtimes H

(written

\wedge

in the book), distinct pairs

(a,b)

and

(a',b')

are adjacent when, in each coordinate, the entries are equal or adjacent. Words of length

n

are confusable exactly when they are adjacent in

G^{\boxtimes n}

.

Shannon capacity.

\Theta(G)=\lim_n\alpha(G^{\boxtimes n})^{1/n}=\sup_n\alpha(G^{\boxtimes n})^{1/n}

. Always

\Theta(G)\ge\alpha(G)

. Lovász proved

\Theta(C_5)=\sqrt5

, attained by the two-letter code below; even cycles have

\Theta(C_{2m})=m

.

\Theta(C_7)

is unknown.

Erdős–McEliece–Taylor. The largest possible

\alpha(G_1\boxtimes\cdots\boxtimes G_n)

over graphs with

\alpha(G_i)<k_i

is exactly

r(k_1,\dots,k_n)-1

.

For $n=2$ , $k_1=k_2=3$ : $\alpha(C_5)=2<3$ , and $\alpha(C_5\boxtimes C_5)=5=r(3,3)-1$ . The pentagon reaches the maximum.

Explore

Cell

(i,j)

is the word "

i\,j

". Letters

i

and

i\pm1\pmod 5

can be confused. Click cells to choose codewords; confusable pairs are joined in red. Shaded cells could be confused with a chosen word.

Worked example

Show that $\alpha(C_5\boxtimes C_5)=5$ , with letters $0,\dots,4$ and $i$ confusable with $i\pm1\bmod 5$ .

Show that the five words $(i,2i\bmod5)$ form a code.

Take two of them, with first letters differing by $\delta=j-i\ne0$ . If $\delta=\pm1$ the first letters are confusable, but the second letters differ by $2\delta=\pm2$ , which is not confusable. If $\delta=\pm2$ the first letters already differ by 2. Either way, some coordinate tells the words apart.
For the upper bound, look at the codewords whose first letter is $i$ or $i+1$ . At most how many are there?

Any two of them have confusable first letters (equal or adjacent), so their second letters must be distinct and non-adjacent. That is an independent set in $C_5$ , so there are at most 2.
Add up over the five windows $\{i,i+1\}$ .

Each codeword's first letter lies in exactly two windows. So $2|\mathcal C|\le5\cdot2$ , giving $|\mathcal C|\le5$ .
What does this give for $\Theta(C_5)$ ?

$\Theta(C_5)\ge\alpha(C_5^{\boxtimes2})^{1/2}=\sqrt5\approx2.236$ , better than $\alpha(C_5)=2$ . Lovász's theta function gives the matching upper bound, so $\Theta(C_5)=\sqrt5$ : longer words never do better per letter.

Check your understanding

The five-word code uses two letters per word. What is its zero-error rate, in bits per letter?

$\tfrac12\log_25\approx1.16$
$\log_25\approx2.32$ That is per word. Each word costs two channel uses.
1That is the single-letter rate $\log_2\alpha(C_5)$ . The two-letter code does better.

Five messages in two channel uses:

\log_25

bits per two letters. Shannon capacity in bits is

\log_2\Theta

, and for

C_5

this code already achieves it.

Why is $\alpha(G^{\boxtimes mn})\ge\alpha(G^{\boxtimes n})^m$ ?

Concatenate $m$ codewords of length $n$ : two such long words differ in some block, and that block tells them apart.
Because $\alpha$ is multiplicative under $\boxtimes$ .It is only super-multiplicative: $\alpha(C_5^{\boxtimes2})=5>2\cdot2$ .
Because $G^{\boxtimes mn}$ has more vertices.More vertices alone does not give large independent sets. Build the code explicitly.

Distinct concatenations differ in some block, where the two length-

n

codewords are non-confusable, so the long words are non-confusable. This super-multiplicativity is why the limit defining

\Theta

exists and equals the supremum.

$G$ and $H$ both have independence number at most 2. Why must $\alpha(G\boxtimes H)\le5$ ?

For two codewords, some coordinate has distinct non-adjacent letters; colour the pair by such a coordinate. A monochromatic triangle would be an independent 3-set in $G$ or $H$ . So at most $r(3,3)-1=5$ codewords.
Because $\alpha(G\boxtimes H)=\alpha(G)\alpha(H)\le4$ .The pentagon gives 5, so the product formula fails.
Because $G\boxtimes H$ has at most 25 vertices. $G$ and $H$ can be as large as you like.

This is the easy half of Erdős–McEliece–Taylor. The code gives a 2-colouring of the complete graph on the codewords with no monochromatic triangle, so it has at most 5 vertices.

Practice

The square channelClique covers

Show that $\Theta(C_4)=2$ .

Hint

$C_4$ is covered by two cliques (edges). What covers $C_4^{\boxtimes n}$ ?

Solution

$\alpha(C_4)=2$ gives $\Theta\ge2$ . Cover $C_4$ by the cliques $\{0,1\}$ and $\{2,3\}$ . Products of cliques are cliques in the strong product, so $C_4^{\boxtimes n}$ is covered by $2^n$ cliques. An independent set has at most one vertex per clique, so $\alpha(C_4^{\boxtimes n})\le2^n$ and $\Theta(C_4)=2$ .

Long words for the pentagonConcatenation

Show that $\alpha(C_5^{\boxtimes 2n})\ge5^n$ , and that $\alpha(C_5^{\boxtimes(2n+1)})\ge2\cdot5^n$ .

Solution

Concatenate $n$ words from the five-word code: $5^n$ codewords of length $2n$ . For odd length, append one more letter from the independent set $\{0,2\}$ of $C_5$ , doubling the count.

More practice: Li–Lin, Exercises 8.1 and 8.4.

SimulationLi–Lin, Ch. 9: Dependent Random Choice

Dependent random choice

Pick a few random vertices and keep their common neighbourhood. The set you get is small, but it is special: pairs with few common neighbours rarely survive the choice. That is exactly what you need to embed sparse bipartite graphs into dense graphs.

The idea

The lemma. Let

G

have

n

vertices and average degree

d

. Suppose positive integers

t,r,m,a

satisfy

n\left(\frac dn\right)^{t}-\binom nr\left(\frac mn\right)^{t}\ge a.

Then $G$ has a set $U$ of at least $a$ vertices in which every $r$ vertices have at least $m$ common neighbours.

Why. Choose $t$ vertices $T$ uniformly at random, with repetition, and let $A$ be their common neighbourhood.

A vertex $v$ is in $A$ when all $t$ picks land in $N(v)$ : probability $(d(v)/n)^t$ . By convexity $\mathbb E|A|=\sum_v(d(v)/n)^t\ge n(d/n)^t$ .
An $r$ -set $S$ with fewer than $m$ common neighbours ("bad") lies in $A$ only if all picks land in its common neighbourhood: probability below $(m/n)^t$ . So the expected number $Y$ of bad sets inside $A$ is below $\binom nr(m/n)^t$ .
Some choice has $|A|-Y\ge a$ . Delete one vertex from each bad set in $A$ .

Application. If

H

is bipartite and every vertex on one side has degree at most

r

, then

\mathrm{ex}(n,H)\le c_H\,n^{2-1/r}

. The worked example does a case by hand.

Explore

the picks

T

common neighbourhood

A

bad pairs in

A

(fewer than

m

common neighbours) and the vertices deleted for them the final set

U

Edge probability of G 0.50 Number of picks t 2 Threshold m 8

Worked example

Let $H$ be $K_4$ with every edge subdivided once: 4 branch vertices and 6 subdivision vertices, each subdivision vertex adjacent to two branch vertices. Show that every graph with at least $3.7\,n^{3/2}$ edges contains $H$ .

What set $U$ would make embedding $H$ easy?

A set of 4 vertices in which every pair has at least 10 common neighbours. Put the branch vertices on $U$ . Then give each of the 6 subdivision vertices a common neighbour of its two branch vertices, avoiding the at most $4+5=9$ vertices already used. With 10 common neighbours there is always one left.
Apply the lemma with $r=2$ , $m=10$ , $t=2$ . What is the second term?

$\binom n2(10/n)^2<\frac{n^2}{2}\cdot\frac{100}{n^2}=50$ .
How large must $d$ be?

We need $n(d/n)^2-50\ge4$ , i.e. $d^2/n\ge54$ , i.e. $d\ge\sqrt{54n}$ .
Translate into edges.

$e=nd/2$ , so $e\ge\frac{\sqrt{54}}{2}n^{3/2}\approx3.67\,n^{3/2}$ suffices. Hence $\mathrm{ex}(n,H)<3.7\,n^{3/2}$ , matching the $n^{2-1/r}$ shape with $r=2$ .

Check your understanding

In a graph on 40 vertices, a pair $\{u,v\}$ has only 3 common neighbours. With $t=3$ picks, what is the probability that both $u$ and $v$ end up in $A$ ?

$(3/40)^3\approx0.0004$
$3/40$ That is for one pick. All three picks must land among the 3 common neighbours.
$(6/40)^3$ The picks must be adjacent to both $u$ and $v$ , so they must land in the intersection of the two neighbourhoods.

u,v\in A

means every pick is a common neighbour of

u

and

v

. The picks are independent, each succeeding with probability

3/40

.

Why is $\mathbb E|A|\ge n(d/n)^t$ , even if $G$ is far from regular?

$\mathbb E|A|=\sum_v(d(v)/n)^t$ , and $x\mapsto x^t$ is convex, so the sum is at least $n$ times the value at the average.
Because every vertex has degree $d$ . $d$ is only the average degree. The argument must handle uneven degrees.
Because $A$ always contains $T$ . $T$ is usually not inside its own common neighbourhood.

By Jensen,

\frac1n\sum_v (d(v)/n)^t\ge\big(\frac1n\sum_v d(v)/n\big)^t=(d/n)^t

. Uneven degrees only help.

Suppose $m<d$ . As $t$ grows, what happens to the ratio of the two terms, $\binom nr(m/n)^t\big/\,n(d/n)^t$ ?

It tends to 0, because it equals $\frac{\binom nr}{n}(m/d)^t$ and $m/d<1$ .
It grows, because $\binom nr$ is huge. $\binom nr$ is fixed while $t$ grows. Which factor depends on $t$ ?
It stays constant.Write the ratio out and see where $t$ appears.

More picks make bad sets die off faster than the good set shrinks. The price is that

|A|

itself shrinks like

(d/n)^t

, so

t

is chosen just large enough.

Practice

Subdivided

K_5

Same recipe, new numbers

Repeat the worked example for $K_5$ with each edge subdivided. What constant $c$ do you get in $\mathrm{ex}(n,H)\le c\,n^{3/2}$ ?

Hint

Now $|U|\ge5$ , and you embed 10 subdivision vertices. How many common neighbours does each pair need?

Solution

When placing a subdivision vertex, at most $5+9=14$ vertices are already used, so $m=15$ works. With $t=2$ the bad term is below $15^2/2=112.5$ , so we need $d^2/n\ge117.5$ . Then $e=nd/2\ge\frac{\sqrt{117.5}}2n^{3/2}\approx5.42\,n^{3/2}$ suffices.

The size of

A

Indicators

Prove $\mathbb E|A|=\sum_v(d(v)/n)^t$ when the $t$ vertices are chosen independently and uniformly, with repetition allowed. Why does the lemma allow repetition?

Solution

$|A|=\sum_v\mathbf 1[v\in A]$ , and $v\in A$ exactly when each of the $t$ independent picks lies in $N(v)$ , which has probability $(d(v)/n)^t$ . Repetition makes the picks independent, so probabilities multiply exactly. Without repetition the formula would be a ratio of falling factorials, which is messier to estimate.

More practice: Li–Lin, Exercises 9.2 and 9.7.

CompareLi–Lin, Ch. 10: Quasi-Random Graphs

Quasi-random graphs

The Paley graph is completely determined by arithmetic, yet every statistic you compute says it looks random. Chung, Graham and Wilson showed that several very different-looking "random-like" properties are in fact equivalent. Compare four graphs of the same density and see which tests catch the fakes.

The idea

Fix $0<p<1$ and a sequence of graphs $G$ on $n\to\infty$ vertices. The following are equivalent; graphs satisfying them are called quasi-random with density $p$ .

Cycle count. $e(G)\ge(1+o(1))\,p\frac{n^2}{2}$ and the number of closed 4-walks, $\operatorname{tr}A^4$ , is at most $(1+o(1))\,p^4n^4$ .
Discrepancy. For every vertex set $S$ , $e(S)=p\frac{|S|^2}{2}+o(n^2)$ .
Eigenvalues. $\lambda_1=(1+o(1))\,pn$ and every other eigenvalue has $|\lambda_i|=o(n)$ .

The striking part is the first: one number, the 4-cycle count, controls the edge count of every subset.

Expander mixing lemma. If

G

is

d

-regular and

\lambda=\max_{i\ge2}|\lambda_i|

, then for all vertex sets

S,T

,

\left|e(S,T)-\frac{d\,|S|\,|T|}{n}\right|\le\lambda\sqrt{|S|\,|T|}.

The Paley graph $P_q$ is $\frac{q-1}2$ -regular with other eigenvalues $\frac{-1\pm\sqrt q}{2}$ , so it is quasi-random with $p=\tfrac12$ . Graphs with a small second eigenvalue are the source of many explicit Ramsey lower bounds, for multicolour numbers and for off-diagonal $r(s,t)$ .

Explore

Graph on 37 vertices, density about ½

Adjacency matrix: a filled cell at row

i

, column

j

means

ij

is an edge. Rows of the tested set

S

are marked in gold.

All 37 eigenvalues, largest first. The band shows

\pm\sqrt n

, roughly where a random graph's non-top eigenvalues sit.

Worked example

For a prime $q\equiv1\pmod4$ , find the eigenvalues of $P_q$ and use them to show $\alpha(P_q)\le\sqrt q$ .

$P_q$ is a circulant graph: $x\sim y$ depends only on $x-y$ . What are the eigenvectors?

For $\omega=e^{2\pi i/q}$ and each $j\in\mathbb Z_q$ , the vector $u_j=(\omega^{jx})_{x}$ is an eigenvector with eigenvalue $\lambda_j=\sum_{s\in Q}\omega^{js}$ , where $Q$ is the set of nonzero squares. For $j=0$ this is $|Q|=\frac{q-1}2$ .
Relate $\lambda_j$ ( $j\ne0$ ) to the Gauss sum $g_j=\sum_{x\in\mathbb Z_q}\omega^{jx^2}$ .

As $x$ runs over $\mathbb Z_q$ , $x^2$ takes the value 0 once and each nonzero square twice. So $g_j=1+2\lambda_j$ .
Use the classical fact $g_j^2=q$ for $q\equiv1\pmod4$ ( $g_j$ is real). What are the eigenvalues?

$g_j=\pm\sqrt q$ , so $\lambda_j=\frac{-1\pm\sqrt q}{2}$ for every $j\ne0$ . Half of them take each sign.
Apply Hoffman's bound $\alpha\le n\frac{-\lambda_{\min}}{d-\lambda_{\min}}$ for $d$ -regular graphs.

With $-\lambda_{\min}=\frac{1+\sqrt q}{2}$ and $d-\lambda_{\min}=\frac{q+\sqrt q}{2}$ : $\alpha(P_q)\le q\cdot\frac{1+\sqrt q}{q+\sqrt q}=\sqrt q$ . For $q=17$ this gives $\alpha\le4$ ; the truth is 3. The spectrum alone gets close.

Check your understanding

Two disjoint cliques of size $n/2$ have edge density close to $\tfrac12$ . Are they quasi-random?

No. If $S$ is one of the cliques, $e(S)\approx|S|^2/2$ , twice what density $\tfrac12$ predicts.
Yes, the density is right.Density is a single number. Quasi-randomness asks every large subset to have the right density.
Yes, because random halves have the right number of edges.They do, which is why the test must range over all sets, not random ones.

The discrepancy condition fails for one well-chosen set. The spectrum sees it too: the second eigenvalue is about

n/2

, not

o(n)

. Try it in the explorer.

"Shuffle the labels" changes the picture of the matrix but not the numbers. Why?

Relabelling replaces $A$ by $PAP^{-1}$ for a permutation matrix $P$ , which has the same eigenvalues and the same $\operatorname{tr}A^4$ .
Because the shuffle is undone before computing.It isn't. The stats are computed from the shuffled matrix.
Because the graphs are all symmetric.Every adjacency matrix is symmetric. The point is what relabelling does to it.

Quasi-randomness is a property of the graph, not of a drawing. Structure that is obvious in one labelling can be invisible in another, but similar matrices have identical spectra.

A 500-regular graph on 1000 vertices has $\lambda=\max_{i\ge2}|\lambda_i|=30$ . For sets $S,T$ of size 100, what range does the mixing lemma give for $e(S,T)$ ?

Between 2000 and 8000.
Between 4970 and 5030.The error term is $\lambda\sqrt{|S||T|}$ , not $\lambda$ .
Exactly 5000.5000 is the centre, $d|S||T|/n$ . The lemma allows an error.

Centre

500\cdot100\cdot100/1000=5000

, error at most

30\cdot100=3000

. For larger sets the relative error shrinks: it is

\lambda n/(d\sqrt{|S||T|})

.

Practice

Every graph has many 4-cyclesThe easy half of the cycle count

Let $G$ have $n$ vertices and $e=pn^2/2$ edges. Show $\operatorname{tr}A^4\ge p^4n^4$ .

Hint

$\operatorname{tr}A^4=\sum\lambda_i^4$ . Bound $\lambda_1$ below using the all-ones vector.

Solution

By the Rayleigh quotient with $\mathbf 1$ , $\lambda_1\ge\frac{\mathbf 1^TA\mathbf 1}{n}=\frac{2e}{n}=pn$ . So $\operatorname{tr}A^4=\sum_i\lambda_i^4\ge\lambda_1^4\ge p^4n^4$ . Quasi-random graphs are exactly those where this is nearly tight.

Random tests miss structureWhy "every set" matters

In two disjoint cliques of size $n/2$ , let $S$ be a uniformly random set of size $s$ . Estimate $e(S)$ , and explain why random sets cannot detect this structure.

Solution

$S$ has about $s/2$ vertices in each clique, so $e(S)\approx2\binom{s/2}{2}\approx s^2/4=\tfrac12\cdot\frac{s^2}{2}$ : exactly what density $\tfrac12$ predicts. Only special sets, like one whole clique, reveal the structure. That is why the discrepancy property quantifies over every set, and why spectral and cycle-count tests, which see all sets at once, are so useful.

More practice: Li–Lin, Exercises 10.1 and 10.5.

Play it yourselfLi–Lin, Ch. 11: Regularity Lemma and van der Waerden Number

Van der Waerden and regularity

Colour $1,2,\dots,N$ in two colours: once $N$ is large, some arithmetic progression is monochromatic. Szemerédi's work on the density version of this produced the regularity lemma, which says every large graph is a bounded number of random-looking pieces.

The idea

Van der Waerden's theorem. For all

k

and

t

there is

N

such that every

k

-colouring of

\{1,\dots,N\}

contains a monochromatic arithmetic progression of length

t

. The least such

N

is

w_k(t)

; write

w(t)

for two colours.

Known exactly: $w(3)=9$ , $w(4)=35$ , $w(5)=178$ , $w(6)=1132$ . Szemerédi's theorem is the density version: any set of integers with positive upper density contains arbitrarily long progressions.

Regular pairs. For disjoint vertex sets

X,Y

, the density is

d(X,Y)=\frac{e(X,Y)}{|X||Y|}

. The pair is $\varepsilon$ -regular if

|d(X',Y')-d(X,Y)|\le\varepsilon

for all

X'\subseteq X

,

Y'\subseteq Y

with

|X'|\ge\varepsilon|X|

,

|Y'|\ge\varepsilon|Y|

. Edges between a regular pair are spread like random edges.

Szemerédi's regularity lemma. For every

\varepsilon>0

and

m

there is

M

such that every graph with at least

m

vertices has a partition

V_0\cup V_1\cup\dots\cup V_k

, with

m\le k\le M

,

|V_0|\le\varepsilon n

,

|V_1|=\dots=|V_k|

, in which all but at most

\varepsilon k^2

of the pairs

(V_i,V_j)

are

\varepsilon

-regular.

$M$ does not depend on the graph, but it grows like a tower of 2s of height polynomial in $1/\varepsilon$ , and Gowers showed this is unavoidable. Uses in Ramsey theory: graphs of bounded maximum degree have Ramsey numbers linear in their order (Chvátal, Rödl, Szemerédi and Trotter), and Ramsey–Turán problems such as $\mathrm{RT}(n,K_4,o(n))=(\tfrac18+o(1))n^2$ .

Explore

Click a number to colour it red, again for blue, again to clear. A monochromatic progression is outlined, with its first term and common difference listed below.

Board

Worked example

Prove $w(3)\le9$ : every red/blue colouring of $\{1,\dots,9\}$ has a monochromatic 3-term progression. Suppose one doesn't, and look at 4, 5 and 6.

Suppose 4 and 6 have the same colour, say red. What goes wrong?

2 (from 2, 4, 6), 5 (from 4, 5, 6) and 8 (from 4, 6, 8) must all be blue. But 2, 5, 8 is a progression. The same happens if 4 and 6 are both blue.
So 4 and 6 differ, say 4 red and 6 blue. Reflecting $x\mapsto10-x$ and swapping the colours preserves this situation and sends a red 5 to a blue 5. Why may we assume 5 is red?

The reflection maps progressions to progressions, and swapping colours keeps "monochromatic". Under the combined map, 4 (red) goes to 6 and becomes blue, 6 (blue) goes to 4 and becomes red, and 5's colour flips. So the case "5 blue" turns into the case "5 red".
With 4, 5 red and 6 blue, force as many colours as you can.

3 is blue (3, 4, 5). Then 9 is red (3, 6, 9). Then 7 is blue (5, 7, 9), and 8 is red (6, 7, 8). Also 1 is blue (1, 5, 9), so 2 is red (1, 2, 3).
Find the contradiction.

2, 5 and 8 are all red. So no good colouring of $\{1,\dots,9\}$ exists. The colouring RRBBRRBB of $\{1,\dots,8\}$ shows $w(3)>8$ , so $w(3)=9$ .

Check your understanding

Extend the good colouring RRBBRRBB of $\{1,\dots,8\}$ by colouring 9 red. Which progression is now monochromatic?

1, 5, 9
3, 6, 93 is blue and 6 is red.
2, 5, 88 is blue.

1, 5 and 9 are all red. Colouring 9 blue fails too (7, 8, 9 are then all blue), which is a quick way to see that this particular colouring cannot be extended.

$|X|=|Y|=100$ . The only edges join the first 50 vertices of $X$ to the first 50 of $Y$ , all of them. The density is $\tfrac14$ . Is $(X,Y)$ $0.1$ -regular?

No: those two halves have density 1, far from $\tfrac14$ .
Yes: regularity only asks about the overall density.It asks about every pair of subsets of at least $\varepsilon$ times the size.
Yes: halves are too small to count.The threshold is $\varepsilon|X|=10$ vertices, and 50 is well above it.

With

X'

and

Y'

the two halves,

|d(X',Y')-d(X,Y)|=\tfrac34>0.1

. A regular pair cannot hide a dense block on a large piece.

$V_1,V_2,V_3$ are pairwise $\varepsilon$ -regular with densities $d_{12},d_{13},d_{23}$ , all well above $\varepsilon$ . Roughly how many triangles have one vertex in each?

About $d_{12}d_{13}d_{23}\,|V_1||V_2||V_3|$ , as for random edges.
Possibly none.That can happen for dense pairs that are not regular. Regularity is what rules it out.
About $(d_{12}+d_{13}+d_{23})\,|V_1||V_2||V_3|/3$ .A triangle needs all three edges, so the densities multiply.

This is the triangle counting lemma, the step that makes the regularity lemma useful: a triangle in the "reduced graph" of dense regular pairs gives many real triangles.

Practice

Counting 4-term progressionsWhy good colourings are rare

How many 4-term progressions does $\{1,\dots,34\}$ contain? How many monochromatic ones does a random 2-colouring have on average?

Hint

For common difference $\delta$ , the first term $a$ needs $a+3\delta\le34$ .

Solution

For $\delta=1,\dots,11$ there are $34-3\delta$ choices of $a$ , giving $\sum_{\delta=1}^{11}(34-3\delta)=374-198=176$ . Each is monochromatic with probability $2\cdot2^{-4}=\tfrac18$ , so the average is 22. A good colouring exists (try "Show a good colouring" on the 34-board), but a random one is far from it.

Progressions inside progressionsScaling

Show that if $a,a+\delta,\dots,a+(N-1)\delta$ is 2-coloured with $N\ge w(t)$ , it contains a monochromatic $t$ -term progression.

Solution

Colour $i\in\{1,\dots,N\}$ with the colour of $a+(i-1)\delta$ . A monochromatic progression $i,i+c,\dots$ gives the monochromatic progression $a+(i-1)\delta,\ a+(i-1+c)\delta,\dots$ , with difference $c\delta$ . This is the kind of step used in the proofs of the recursive bounds for $w_k(t)$ .

More practice: Li–Lin, Exercises 11.1 and 11.8.

Construction labLi–Lin, Ch. 12: More Ramsey Linear Functions

Linear Ramsey numbers

For complete graphs Ramsey numbers grow exponentially. For sparse graphs they can be linear in the number of vertices, sometimes with an exact formula. Trees against cliques is the cleanest case: one construction gives the lower bound, and it is the truth.

The idea

Burr's lower bound. Let

G

be connected and let

\sigma(H)

be the smallest possible colour class in a proper

\chi(H)

-colouring of

H

. If

|G|\ge\sigma(H)

, then

r(G,H)\ge(\chi(H)-1)(|G|-1)+\sigma(H).

Construction: take $\chi(H)-1$ red cliques of size $|G|-1$ and one red clique of size $\sigma(H)-1$ , and colour every edge between different cliques blue. Red components are too small to hold $G$ , and a blue $H$ would need a proper colouring with too few or too small classes.

Goodness.

G

is $H$ -good if equality holds. For

H=K_p

the bound reads

(p-1)(|G|-1)+1

, and

G

is called

p

-good.

Chvátal's theorem. Every tree

T

on

m

vertices is

p

-good for every

p

:

r(T,K_p)=(m-1)(p-1)+1

.

Other exact results: $r(P_m,P_n)=n+\lfloor m/2\rfloor-1$ for $n\ge m\ge2$ (Gerencsér–Gyárfás); $r(K_{1,m},K_{1,n})=m+n-\epsilon$ , with $\epsilon=1$ if $m,n$ are both even and 0 otherwise (Harary); $r(C_4,C_4)=6$ . Large book graphs are $p$ -good, subdivided graphs have linear Ramsey numbers, and Lee proved the Burr–Erdős conjecture: $d$ -degenerate graphs have Ramsey numbers linear in their order.

Explore

Click an edge: red, then blue, then uncoloured. Avoid a red copy of the first graph and a blue copy of the second; any copy found is highlighted.

Pair (red, blue)

Board

Worked example

Prove Chvátal's upper bound: if $T$ is a tree on $m$ vertices and $N=(m-1)(p-1)+1$ , every red/blue colouring of $K_N$ has a red $T$ or a blue $K_p$ .

Show that a graph with minimum degree at least $m-1$ contains every tree on $m$ vertices.

Embed $T$ one vertex at a time, always adding a leaf next to an already embedded vertex $u$ . Fewer than $m-1$ other vertices have been used, and $u$ has at least $m-1$ neighbours, so one is free.
Suppose the red graph $R$ has no copy of $T$ . What can you say about every subgraph of $R$ ?

Every subgraph has a vertex of degree at most $m-2$ , by step 1. So $R$ is $(m-2)$ -degenerate: repeatedly removing a vertex of degree at most $m-2$ empties it.
Why does that give $\chi(R)\le m-1$ ?

Colour the vertices greedily in the reverse of the removal order. Each vertex has at most $m-2$ neighbours coloured before it, so one of $m-1$ colours is free.
Finish.

Some colour class of $R$ has at least $N/(m-1)>p-1$ vertices, so at least $p$ . It is independent in $R$ , so all edges inside it are blue: a blue $K_p$ . With Burr's construction, $r(T,K_p)=(m-1)(p-1)+1$ .

Check your understanding

What lower bound does Burr's construction give for $r(P_5,K_4)$ , where $P_5$ is the path on 5 vertices?

13
16The red cliques have $|G|-1=4$ vertices, not $|G|$ .
9There are $\chi(K_4)-1=3$ red cliques, not 2.

(4-1)(5-1)+1=13

: three red

K_4

's with blue between them is a colouring of

K_{12}

with no red

P_5

and no blue

K_4

. By Chvátal's theorem 13 is exact.

In the construction for a tree $T$ on $m$ vertices against $K_p$ , why is there no red $T$ ?

Every red component has only $m-1$ vertices, and $T$ is connected with $m$ vertices.
Because the red graph is bipartite.The red graph is a union of cliques, far from bipartite.
Because trees need a vertex of high degree.Paths are trees with maximum degree 2. The reason is size, not degree.

A connected red subgraph lies inside one red component. Connectedness of

G

is exactly why Burr's bound assumes it.

Burr's bound with $G=H=K_{1,3}$ gives $(2-1)(4-1)+1=4$ . The true value is $r(K_{1,3},K_{1,3})=6$ . What does this show?

$K_{1,3}$ is not $K_{1,3}$ -good: the bound can be strict.
Burr's bound is wrong for stars.A lower bound below the truth is still correct.
$r(K_{1,3},K_{1,3})$ must be 4.The pentagon colouring of $K_5$ (try it in the lab) has no monochromatic $K_{1,3}$ .

Goodness is a special property, not a general rule. For two stars the extremal colourings are regular-looking (each colour 2-regular on

K_5

), not block-structured.

Practice

A star against a triangleChvátal, and a direct proof

Show that $r(K_{1,n},K_3)=2n+1$ , first from Chvátal's theorem and then directly.

Hint

Directly: if no vertex has $n$ red edges, every vertex has many blue edges. Two blue neighbours of each other then share a blue neighbour.

Solution

$K_{1,n}$ is a tree on $n+1$ vertices, so Chvátal gives $n\cdot2+1$ . Directly, in $K_{2n+1}$ with no red $K_{1,n}$ , each vertex has at most $n-1$ red and so at least $n+1$ blue edges. Take a blue edge $uv$ : $u$ and $v$ each have at least $n$ further blue neighbours among the other $2n-1$ vertices, so they share one, giving a blue triangle. Two red $K_n$ 's with blue between them show $2n$ is not enough.

Two 4-cyclesA pentagon again

Show that $r(C_4,C_4)\ge6$ .

Solution

Colour a 5-cycle in $K_5$ red and its complement, another 5-cycle, blue. A 5-cycle has no 4-cycle (it has no cycle other than itself), so neither colour contains $C_4$ . The lab confirms that every colouring of $K_6$ fails.

More practice: Li–Lin, Exercises 12.2 and 12.3.

Play it yourselfLi–Lin, Ch. 13: Various Ramsey Problems

Bipartite, size and other variants

Change what is coloured, or what is counted, and you get a new Ramsey problem. Colour the edges of a complete bipartite graph, ask for the fewest edges rather than the fewest vertices, demand induced copies, or forbid large cliques in the host. The grid game below is the smallest bipartite case.

The idea

Bipartite Ramsey number.

br(B_1,B_2)

is the least

N

such that every red/blue colouring of

K_{N,N}

contains a red

B_1

or a blue

B_2

. Since

K_{2N}\supseteq K_{N,N}

,

r(B_1,B_2)\le2\,br(B_1,B_2)

.

Known.

br(K_{2,2})=5

. Thomason:

br(K_{m,n})\le2^m(n-1)+1

for

n\ge m

. Conlon:

br(K_{n,n})\le(1+o(1))\,2^{n+1}\log_2 n

.

Size Ramsey number.

\hat r(G,H)

is the fewest edges of a graph

F

such that every red/blue colouring of

F

has a red

G

or a blue

H

. For example

\hat r(K_{1,n},K_{1,n})=2n-1

, and

\hat r(K_n,K_n)=\binom{r(n,n)}2

: for cliques nothing beats the complete graph. Beck showed paths have linear size Ramsey numbers.

Induced and Folkman. For every graph

H

there is a graph

G

such that every 2-colouring of

E(G)

contains a monochromatic induced copy of

H

. And there are graphs with no

K_4

in which every 2-colouring of the edges has a monochromatic triangle (Folkman): forcing a triangle does not require large cliques.

Explore

Row

i

is

x_i

, column

j

is

y_j

, and cell

(i,j)

is the edge

x_iy_j

. A monochromatic

K_{2,2}

is four cells of one colour at the corners of a rectangle. Click to cycle red, blue, uncoloured.

Board

Worked example

Prove that every red/blue colouring of $K_{5,5}$ contains a monochromatic $K_{2,2}$ . Think of the 5×5 grid above.

A monochromatic rectangle is two rows and two columns with all four cells one colour. Rephrase in terms of "monochromatic row pairs" in each column.

Say column $j$ has a red row pair $\{a,b\}$ if cells $(a,j)$ and $(b,j)$ are both red. A red rectangle is a red row pair shared by two columns, and similarly for blue. So with no monochromatic rectangle, each (row pair, colour) combination occurs in at most one column. There are $\binom52\cdot2=20$ combinations.
A column has $a$ red and $5-a$ blue cells. How many monochromatic row pairs does it have, at least?

$\binom a2+\binom{5-a}2$ , which is 4 when $a=2$ or $3$ , and at least 6 otherwise. So the five columns give at least 20 monochromatic row pairs.
Combine steps 1 and 2. What must every column look like?

At least 20 pairs into at most 20 slots, so equality everywhere: every column has 2 or 3 red cells, and all 10 red row pairs are used exactly once.
Count red row pairs and reach a contradiction.

If $x$ columns have 3 red cells and $5-x$ have 2, the red row pairs number $3x+(5-x)=2x+5$ . This must equal 10, so $x=2.5$ , which is impossible. Hence $br(K_{2,2})\le5$ ; the 4×4 board has a good colouring, so $br(K_{2,2})=5$ .

Check your understanding

Why is $r(B_1,B_2)\le2\,br(B_1,B_2)$ for bipartite $B_1,B_2$ ?

Split $K_{2N}$ into two halves of size $N$ : the edges between them form a $K_{N,N}$ , and its colouring already contains what we need.
Because $K_{2N}$ has twice as many edges as $K_{N,N}$ .It has about twice as many, but the argument needs a copy of $K_{N,N}$ inside $K_{2N}$ , not an edge count.
Because bipartite graphs have chromatic number 2.True, but the inequality comes from finding $K_{N,N}$ inside $K_{2N}$ .

Any colouring of

K_{2N}

restricts to a colouring of the

K_{N,N}

between the halves, and with

N=br(B_1,B_2)

that contains a red

B_1

or a blue

B_2

.

$K_6$ has 15 edges and every 2-colouring of it has a monochromatic triangle. Is there a graph with fewer edges with the same property?

No: $\hat r(K_3,K_3)=\binom{6}{2}=15$ .
Yes: the Folkman graphs.Folkman graphs avoid $K_4$ , but they are large and have many more edges.
Yes: $K_5$ with one extra vertex of degree 3.Colour $K_5$ as two pentagons. Can the new vertex's three edges always be coloured safely?

For complete graphs the size Ramsey number is

\binom{r(n,n)}{2}

: you cannot save edges by using a sparser host. (For the extra vertex of degree 3: colour

K_5

as two pentagons; whichever three neighbours it has, its three edges can be coloured without closing a monochromatic triangle.)

Can a triangle-free graph $G$ have the property that every 2-colouring of its edges contains a monochromatic triangle?

No: $G$ has no triangles at all, monochromatic or not.
Yes, by Folkman's theorem.Folkman's graphs avoid $K_4$ , not $K_3$ .
Yes, if $G$ is large enough.A colouring cannot create a triangle that is not there.

To force a monochromatic

K_3

the host must contain

K_3

. Folkman's surprise is that it need not contain

K_4

, even though the obvious host

K_6

does.

Practice

Size Ramsey for starsUpper and lower bounds

Show that $\hat r(K_{1,n},K_{1,n})\le2n-1$ , and that the star $K_{1,2n-2}$ is not enough.

Solution

In any 2-colouring of the $2n-1$ edges of $K_{1,2n-1}$ , one colour has at least $n$ edges, all at the centre: a monochromatic $K_{1,n}$ . In $K_{1,2n-2}$ , colour $n-1$ edges red and $n-1$ blue; no vertex has $n$ edges of one colour. (The matching lower bound, that no graph with $2n-2$ edges works, takes more care.)

The 4×4 boardA good colouring

Find a colouring of $K_{4,4}$ with no monochromatic $K_{2,2}$ , and check it.

Hint

A monochromatic rectangle means two rows that share two red columns, or two blue columns. Start from the row RRRB and choose the other rows so that every pair of rows shares at most one red and at most one blue column.

Solution

Rows (R = red, B = blue): RRRB, RBBR, BRBR, BBRR. Check the six pairs of rows: each pair shares at most one red column and at most one blue column (rows 2 and 3, for example, share column 3 in blue and column 4 in red). So no rectangle is monochromatic. "Show a good colouring" on the 4×4 board loads it.

More practice: Li–Lin, Exercises 13.1 and 13.5.