Graph Ramsey Theory

Thirteen modules, one for each chapter of a first course on graph Ramsey theory, from Ramsey's theorem to bipartite and size Ramsey numbers. Colour the edges yourself, run the random experiments, watch a random graph grow, work through an example one step at a time, then check yourself with concept questions and practice problems.

Follows the chapter order of Y. Li and Q. Lin, Elementary Methods of Graph Ramsey Theory, Applied Mathematical Sciences 211 (Springer, 2022). All thirteen chapters are covered, one module each. Chapter and exercise numbers refer to that book; the questions and examples here are written for this page. Exercises from the book appear at the end of each module, with their numbers from the book and their statements restated in our own words.

Play it yourselfLi–Lin, Ch. 1: Existence

Ramsey's theorem

Colour every edge of K6 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 KN contains a red Km or a blue Kn. 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 rk(G) uses k colours.
ErdΕ‘s–Szekeres recursion. For m,nβ‰₯2,
r(m,n)≀r(mβˆ’1,n)+r(m,nβˆ’1),hencer(m,n)≀(m+nβˆ’2mβˆ’1).

Proof in one line: a vertex v of KN 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)≀(2kβˆ’2kβˆ’1)<4kβˆ’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)≀9. (The board above has a colouring of K8 with no red triangle and no blue K4, so in fact r(3,4)=9.)

  1. 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 K2; if there is none, all of Kn is blue. With r(3,3)=6 the recursion gives r(3,4)≀r(2,4)+r(3,3)=4+6=10.

  2. In a colouring of K9, 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 K4.

  3. 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 K4.

  4. If neither case happens, every vertex has at most 3 red and at most 5 blue edges. Why is that impossible in K9?

    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β‹…3=27 would be odd. That is impossible, since the degree sum is twice the number of edges. So r(3,4)≀9.

Check your understanding

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

  1. A 5-cycle.
  2. The complete bipartite graph K2,3.K2,3 has no triangle, but its complement is a triangle plus an edge, so the blue graph has a triangle.
  3. 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 C5.

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

  1. 18
  2. 20That is the binomial bound (63). Feed in the known value of r(3,4) instead.
  3. 17The parity improvement needs both terms on the right to be even, and 9 is odd.
r(4,4)≀r(3,4)+r(4,3)=9+9=18. This turns out to be the exact value: module 2 shows a colouring of K17 with no monochromatic K4.

Someone exhibits a red/blue colouring of K42 with no monochromatic K5. What does this prove?

  1. r(5,5)β‰₯43.
  2. r(5,5)=43.One good colouring gives only a lower bound. An upper bound needs a statement about every colouring.
  3. r(5,5)≀42.A colouring that avoids the pattern shows K42 is too small, not big enough.
A colouring with no monochromatic K5 shows K42 does not force one, so r(5,5)>42. Lower bounds come from constructions; upper bounds come from arguments that cover all 2(N2) colourings.

Practice

Three coloursPigeonhole once more

Show that every colouring of the edges of K17 with three colours contains a monochromatic triangle, that is, r3(3)≀17.

Hint

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

Solution

Some colour, say colour 1, appears on at least ⌈16/3βŒ‰=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 K6 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)≀(m+nβˆ’2mβˆ’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: (n1)=n=r(2,n), and similarly for r(m,2). Step: r(m,n)≀r(mβˆ’1,n)+r(m,nβˆ’1)≀(m+nβˆ’3mβˆ’2)+(m+nβˆ’3mβˆ’1)=(m+nβˆ’2mβˆ’1) by Pascal's rule.

From Li and Lin, Elementary Methods of Graph Ramsey Theory (Springer, 2022)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 1.2ErdΕ‘s–Szekeres

Let a1,…,an be distinct reals with nβ‰₯st+1. Prove there is an increasing subsequence of s+1 terms or a decreasing one of t+1 terms.

Hint

Label ai by (xi,yi): the length of the longest increasing subsequence ending at ai, and the longest decreasing one starting at ai.

Solution

Suppose not, so 1≀xi≀s and 1≀yi≀t: at most st possible labels. Since n>st, two indices i<j share a label. If ai<aj, appending aj to the longest increasing subsequence ending at ai gives xjβ‰₯xi+1. If ai>aj, putting ai in front of the longest decreasing subsequence starting at aj gives yiβ‰₯yj+1. Either way the labels differ, a contradiction.

Exercise 1.6Goodman's count of monochromatic triangles

For a graph G on N vertices, show the number of triangles in G plus the number in GΒ― is (N3)βˆ’12βˆ‘vd(v)(Nβˆ’1βˆ’d(v)).

Hint

Colour G red and GΒ― blue. Count pairs (vertex, two edges at it of different colours).

Solution

At v there are d(v)(Nβˆ’1βˆ’d(v)) pairs consisting of one red and one blue edge, each spanning a triangle with v. A non-monochromatic triangle has exactly two vertices where its two edges differ in colour (two edges of one colour and one of the other), so it is counted exactly twice; a monochromatic triangle is never counted. Hence the number of non-monochromatic triangles is 12βˆ‘vd(v)(Nβˆ’1βˆ’d(v)), and the rest of the (N3) triangles are monochromatic.

Exercise 1.9r(n,n)≀4r(nβˆ’1,nβˆ’1)βˆ’2

Prove r(n,n)≀4r(nβˆ’1,nβˆ’1)βˆ’2.

Hint

With m=r(nβˆ’1,nβˆ’1), in a colouring with no monochromatic Kn, |NR(x)∩NB(y)|≀mβˆ’1 and |NB(x)∩NR(y)|≀mβˆ’1 for all xβ‰ y. Double count the pairs (ordered pair x,y; vertex z red to x, blue to y).

Solution

Partial solution. Let m=r(nβˆ’1,nβˆ’1), N=4mβˆ’2, and suppose KN is coloured with no monochromatic Kn. If |NR(x)∩NB(y)|β‰₯m, that set contains a red Knβˆ’1 (add x) or a blue Knβˆ’1 (add y), so the bound in the hint holds.

Counting triples (x,y,z) with xz red and yz blue in two ways gives βˆ‘zdR(z)dB(z)=βˆ‘xβ‰ y|NR(x)∩NB(y)|≀N(Nβˆ’1)(mβˆ’1). Since dR(z)+dB(z)=4mβˆ’3, some vertex z has dR(z)dB(z)≀(4mβˆ’3)(mβˆ’1), forcing one of its degrees to be at least 3mβˆ’2; say dR(z)β‰₯3mβˆ’2. Then every y∈NR(z) has at least 2mβˆ’2 red neighbours inside NR(z), and any red Knβˆ’2 among them would complete a red Kn with y,z.

Finishing the argument from here needs a further case analysis that I haven't written out, so treat this as a guide to the proof's structure rather than a complete proof. (Sanity checks: n=3 gives r(3,3)≀4β‹…2βˆ’2=6, tight; n=4 gives 18≀22.)

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≑1(mod4). The Paley graph Pq has vertex set the field Fq, with x∼y when xβˆ’y is a nonzero square. Since βˆ’1 is a square when q≑1(mod4), this relation is symmetric. Every vertex has (qβˆ’1)/2 neighbours.
Self-complementary. If a is a non-square, the map x↦ax sends squares to non-squares, so it maps Pq onto its complement. Hence Ο‰(Pq)=Ξ±(Pq), and colouring edges of Pq red and non-edges blue gives r(Ο‰+1,Ο‰+1)>q.

For q=17 the squares mod 17 are {1,2,4,8,9,13,15,16}, and Ο‰(P17)=3. So r(4,4)>17; together with r(4,4)≀18 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 sk is the largest N such that {1,…,N} splits into k sum-free sets. Known: s1=1,Β s2=4,Β s3=13,Β s4=44, and s5=160 (by computer, 2017).
Schur meets Ramsey. rk(3)β‰₯sk+2. Also r3(3)=17: Greenwood and Gleason coloured K16 on F16 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 s2=4, and turn that into the lower bound r(3,3)β‰₯6.

  1. 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.

  2. Why can {1,…,5} not be split this way?

    Put 1 in A. Then 2=1+1βˆ‰A, so 2∈B, and 4=2+2βˆ‰B, so 4∈A. Now 3βˆ‰A (since 1+3=4), so 3∈B. Finally 5=1+4 rules out A and 5=2+3 rules out B.

  3. Given a sum-free split of {1,…,N} into k classes, colour KN+1 on vertices 0,…,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.

  4. What do you get for k=2 and k=3?

    So rk(3)>sk+1. With s2=4: a good colouring of K5 (it is the pentagon), so r(3,3)β‰₯6. With s3=13: r3(3)β‰₯15, which is weaker than the true value 17, found with F16 instead.

Check your understanding

Why does the Paley construction need q≑1(mod4)?

  1. So that βˆ’1 is a square, which makes "xβˆ’y is a square" symmetric in x and y.
  2. So that q is prime.q may be any prime power, such as 9 or 25. The condition is about βˆ’1.
  3. So that the graph has an even number of vertices.q≑1(mod4) makes q odd.
yβˆ’x=(βˆ’1)(xβˆ’y), so if βˆ’1 is a square, xβˆ’y and yβˆ’x are squares together. In Fq with q odd, βˆ’1 is a square exactly when q≑1(mod4).

P13 has Ο‰=Ξ±=3. What does it tell you about r(4,4)?

  1. r(4,4)>13, weaker than what P17 gives.
  2. r(4,4)=14.A single graph only ever gives a lower bound.
  3. Nothing, because 13 is prime and 17 is needed.Any graph with no K4 and no independent 4-set gives a lower bound. Check what this one gives.
Colour edges of P13 red and non-edges blue: there is no monochromatic K4, so K13 does not force one. P17 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 P17 and press "Multiply by a non-square". What do you get, and why?

  1. An independent set of size 3, because x↦ax turns every square difference into a non-square one.
  2. Another triangle, because multiplication is an automorphism.Multiplying by a square is an automorphism. A non-square swaps edges and non-edges.
  3. 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 Ο‰(Pq)=Ξ±(Pq).

Practice

Symmetry of Paley graphsAutomorphisms

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

Hint

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

Solution

If a is a nonzero square, Ο•(x)=ax+b is an automorphism, since Ο•(x)βˆ’Ο•(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 Ο•(0)=u and Ο•(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 Z13, join x and y when xβˆ’y∈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)β‰₯14; 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∈S with a+b∈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.

From Li and Lin, Elementary Methods of Graph Ramsey Theory (Springer, 2022)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 2.1r(C4,C4)=6

Prove r(C4,C4)=6.

Hint

Lower bound: split K5 into two 5-cycles. Upper bound: start from a monochromatic triangle in K6.

Solution

Lower bound. K5 is the union of two edge-disjoint 5-cycles; colour one red, one blue. C5 has no 4-cycle.

Upper bound. Colour K6. Since r(3,3)=6 there is a monochromatic triangle, say red xyz; let a,b,c be the other vertices. If a were red to two of x,y,z, say x,y, then axzy is a red C4. So each of a,b,c is blue to at least two of x,y,z.

If two of a,b,c are blue to the same two vertices u,w, then aubw is a blue C4. Otherwise their blue pairs are {x,y},{y,z},{x,z}, say a red to z, b red to x, c red to y. If ab is red, azxb is a red C4; similarly for bc and ca. So ab,bc,ca are blue, and abzc is a blue C4 (bz and zc are blue).

Exercise 2.3The Schur number s3=13

Prove that s3=13: [13] can be split into three sum-free classes, and [14] cannot.

Hint

For the construction, try {1,4,10,13}, {2,3,11,12}, {5,…,9}. For the upper bound, s3≀r3(3)βˆ’2=15 comes for free; ruling out 14 is a finite case analysis.

Solution

Lower bound. {5,6,7,8,9} is sum-free since the smallest sum is 10. In {1,4,10,13} the pairwise sums (with repetition) are 2,5,8,11,14,17,20,23,26, none in the set. In {2,3,11,12} they are 4,5,6,13,14,15,22,23,24, none in the set.

Upper bound. The general argument gives s3≀r3(3)βˆ’2=15. To get down to 13 one checks that no partition of [14] into three sum-free classes exists. This is a finite case analysis: fix 1 in class A, then branch on the classes of 2,3,…, and each branch dies within a few steps. I haven't written the full hand case analysis here. A short backtracking search over all 314 colourings confirms that none works.

Exercise 2.6Neighbourhoods in Paley graphs

In the Paley graph Pp (p≑1mod4, x∼y iff xβˆ’y is a nonzero square), show that for distinct x,y exactly (pβˆ’1)/4 vertices zβˆ‰{x,y} are adjacent to x and not to y.

Hint

With the quadratic character Ο‡, the count is 14βˆ‘zβ‰ x,y(1+Ο‡(zβˆ’x))(1βˆ’Ο‡(zβˆ’y)). Use βˆ‘zΟ‡(zβˆ’a)=0, Ο‡(βˆ’1)=1, and βˆ‘zΟ‡(zβˆ’x)Ο‡(zβˆ’y)=βˆ’1.

Solution

Expand: βˆ‘zβ‰ x,y1=pβˆ’2; βˆ‘zβ‰ x,yΟ‡(zβˆ’x)=βˆ’Ο‡(yβˆ’x); βˆ‘zβ‰ x,yΟ‡(zβˆ’y)=βˆ’Ο‡(xβˆ’y)=βˆ’Ο‡(yβˆ’x); and βˆ‘zΟ‡(zβˆ’x)Ο‡(zβˆ’y)=βˆ’1 (the terms z=x,y are 0). So the count is

14[(pβˆ’2)βˆ’Ο‡(yβˆ’x)+Ο‡(yβˆ’x)+1]=pβˆ’14.

The last character sum: for zβ‰ x, Ο‡(zβˆ’x)Ο‡(zβˆ’y)=Ο‡(1+xβˆ’yzβˆ’x), and as z runs over zβ‰ x, 1+xβˆ’yzβˆ’x runs over all field elements except 1, so the sum is 0βˆ’Ο‡(1)=βˆ’1.

SimulationLi–Lin, Ch. 3: Basic Probabilistic Method

Random colourings

Nobody knows how to write down a colouring of Kn with no monochromatic Kk when n is close to 2k/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 Kn red or blue independently, with probability 12 each. A fixed k-set of vertices is monochromatic with probability 2β‹…2βˆ’(k2). If X counts the monochromatic k-sets, linearity of expectation gives

EX=(nk)21βˆ’(k2).
ErdΕ‘s's bound. If (nk)21βˆ’(k2)<1, then r(k,k)>n. Taking n=⌊2k/2βŒ‹ shows r(k,k)>2k/2 for all kβ‰₯3.

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βˆ’(nk)21βˆ’(k2). Some colouring has at most EX monochromatic k-sets; delete one vertex from each.
Two tools used all the time. Markov's inequality: Pr(Xβ‰₯a)≀EX/a for Xβ‰₯0. Linearity: E(X+Y)=EX+EY, with no independence needed.

The same chapter bounds independence numbers: every graph has Ξ±(G)β‰₯βˆ‘v1d(v)+1 (the worked example).

Explore

red blue Β· vertices with a ring are deleted to kill every monochromatic Kk; the rest are shown in teal.

Worked example

Prove that every graph G has Ξ±(G)β‰₯βˆ‘v1d(v)+1 (Caro–Wei), and deduce TurΓ‘n's theorem from it.

  1. 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∈I were adjacent, u would come before v and v before u.

  2. What is Pr(v∈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∈I)=1d(v)+1.

  3. Finish the bound.

    E|I|=βˆ‘v1d(v)+1 by linearity, so some ordering gives an independent set at least this large.

  4. Deduce: a graph on n vertices with no Kr+1 has at most (1βˆ’1r)n22 edges.

    x↦1x+1 is convex, so by Jensen Ξ±(H)β‰₯ndΒ―+1 for any H with average degree dΒ―. Apply this to the complement GΒ―: a clique in G is an independent set in GΒ―, so rβ‰₯Ξ±(GΒ―)β‰₯ndΒ―GΒ―+1. Hence dΒ―GΒ―β‰₯nrβˆ’1 and dΒ―G=nβˆ’1βˆ’dΒ―G¯≀nβˆ’nr. So e(G)=ndΒ―G2≀(1βˆ’1r)n22. Module 7 returns to this.

Check your understanding

For k=4 and n=6, EX=(64)2βˆ’5=15/32. What follows?

  1. Some colouring of K6 has no monochromatic K4, so r(4,4)>6.
  2. Every colouring of K6 has no monochromatic K4.An average below 1 guarantees some colouring with X=0, not that all have it.
  3. A random colouring has a monochromatic K4 with probability exactly 15/32.Markov gives Pr(Xβ‰₯1)≀15/32. Equality would need X≀1 always.
X takes whole-number values with mean below 1, so Pr(X=0)>0. Here Markov even gives Pr(X=0)β‰₯17/32.

Two 4-sets that share an edge are not independent events. Why is EX=(nk)21βˆ’(k2) still right?

  1. Linearity of expectation holds for any random variables, dependent or not.
  2. Because the overlaps are rare enough to ignore.The formula is exact for every n, not an approximation.
  3. It isn't; the formula is an upper bound.Write X as a sum of indicator variables and take expectations term by term.
X=βˆ‘S1[SΒ mono] and E of a sum is the sum of the E's, always. Dependence matters for the variance, not the mean.

For some k and n=40, EX=6.2. What does deletion give?

  1. r(k,k)>34.
  2. r(k,k)>40.That needs EX<1. Here typical colourings do have monochromatic k-sets.
  3. Nothing, because EX>1.Some colouring has at most 6 bad sets. What can you remove?
Some colouring has X≀6.2, and X is a whole number, so X≀6. Remove one vertex from each bad set: at least 34 vertices remain with no monochromatic Kk.

Practice

The 2k/2 boundChecking the inequality

Show that n=⌊2k/2βŒ‹ satisfies (nk)21βˆ’(k2)<1 for kβ‰₯3.

Hint

Use (nk)≀nk/k! and nk≀2k2/2.

Solution

(nk)21βˆ’(k2)≀2k2/2k!21βˆ’k2/2+k/2=21+k/2k!. For k=3 this is 22.5/6β‰ˆ0.94<1, and going from k to k+1 multiplies it by 2/(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 12, so the expected number of crossing edges is m/2, and some split achieves at least that. The crossing edges form a bipartite subgraph.

From Li and Lin, Elementary Methods of Graph Ramsey Theory (Springer, 2022)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 3.6Caro–Wei by greedy deletion

Let f(G)=βˆ‘v11+d(v). Show that deleting a vertex of maximum degree gives G1 with f(G1)β‰₯f(G), and deduce Ξ±(G)β‰₯f(G).

Hint

Removing v loses its term but every neighbour's term grows.

Solution

Let v have maximum degree Ξ”β‰₯1. Deleting it removes 11+Ξ”. Each of its Ξ” neighbours u loses one degree, so its term rises by 1d(u)βˆ’11+d(u)=1d(u)(1+d(u))β‰₯1Ξ”(Ξ”+1). The total gain is at least ΔΔ(Ξ”+1)=1Ξ”+1, so f(G1)β‰₯f(G).

Repeat until no edges remain. The final graph is edgeless on k vertices, so f=k, and its vertex set is independent in G. Hence Ξ±(G)β‰₯kβ‰₯f(G).

Exercise 3.7Sparse graphs have large independent sets

If G has N vertices and average degree 0<d<1, show Ξ±(G)β‰₯N/2.

Hint

Caro–Wei plus convexity, or count components.

Solution

By Caro–Wei and convexity of x↦11+x, Ξ±(G)β‰₯βˆ‘11+d(v)β‰₯N1+d>N2.

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,…,n}, and each of the (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β†’βˆž. The process that adds edges in random order behaves at m edges like G(n,p) with p=m/(n2).
Threshold. pβˆ—(n) is a threshold for an increasing property Q if Pr(G(n,p)∈Q)β†’0 when p/pβˆ—β†’0 and β†’1 when p/pβˆ—β†’βˆž.
Three thresholds.
  • Triangles: threshold 1/n. At p=c/n the number of triangles is approximately Poisson with mean c3/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(connected)β†’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)β‰₯c(n/log⁑n)3/2. The true order, n2/log⁑n, is due to Kim and to Ajtai, KomlΓ³s and SzemerΓ©di.

Watch

largest component other components with a cycle isolated vertices
  1. 50 isolated vertices. Edges will arrive in a uniformly random order.
  2. Up to m=n/4 edges (pβ‰ˆ12n): a scattering of small trees. Cycles are unlikely this early.
  3. Up to m=n/2 (pβ‰ˆ1/n): the critical point. Cycles start to appear, and components merge quickly.
  4. Up to m=n (pβ‰ˆ2/n): one component swallows most of the others. This is the giant component.
  5. Up to mβ‰ˆn2ln⁑n (pβ‰ˆln⁑n/n): the last isolated vertices get their first edge, and the graph becomes connected around here.
  6. 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β‰₯1.

  1. Compute EX.

    Each of the (n3) triples is a triangle with probability p3, so EX=(n3)p3∼(np)3/6.

  2. Suppose np→0. Why is there a.a.s. no triangle?

    Markov: Pr(Xβ‰₯1)≀EX∼(np)3/6β†’0.

  3. Suppose npβ†’βˆž. Then EXβ†’βˆž, but that alone is not enough. Bound Var⁑X.

    Write X=βˆ‘TXT. 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(n4) of them, each with Cov≀p5. So Var⁑X≀EX+O(n4p5).

  4. Finish with Chebyshev.

    Pr(X=0)≀Var⁑X(EX)2≀1EX+O(n4p5n6p6)=O(1(np)3)+O(1n2p)β†’0.

    Between the two regimes, at p=c/n, X is approximately Poisson with mean c3/6, so Pr(X=0)β†’eβˆ’c3/6.

Check your understanding

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

  1. About 1/6.
  2. About n/6.Compute (n3)p3 with p=1/n: the powers of n cancel.
  3. About 1.You are close. Remember (n3)β‰ˆn3/6.
(n3)nβˆ’3β†’1/6. So at p=1/n a triangle is present with probability about 1βˆ’eβˆ’1/6β‰ˆ0.15: right at the threshold, neither likely nor negligible.

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

  1. About 1.
  2. About 0.Compute n(1βˆ’p)nβˆ’1β‰ˆneβˆ’pn.
  3. About ln⁑n.The exponential eβˆ’pn=1/n cancels the factor n exactly.
n(1βˆ’p)nβˆ’1β‰ˆ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 EXβ†’βˆž, must Pr(Xβ‰₯1)β†’1?

  1. No. X could be huge on a rare event and 0 otherwise, so a second-moment bound is needed.
  2. Yes, by Markov's inequality.Markov bounds Pr(Xβ‰₯a) from above. It says nothing about X being positive.
  3. 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=n2 with probability 1/n and X=0 otherwise: EX=nβ†’βˆž but Pr(Xβ‰₯1)β†’0. Chebyshev with Var⁑X=o((EX)2) rules this out.

Practice

When does K4 appear?Same method, new numbers

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

Hint

E(#K4)=(n4)p6. Where is it of constant order? Check that no subgraph of K4 is denser than K4 itself.

Solution

(n4)p6≍n4p6, which is of constant order at p=nβˆ’2/3. Below it Markov gives no K4. Above it, the second moment works because every subgraph F of K4 has e(F)/v(F)≀6/4, so no smaller piece appears later than K4 itself. The threshold is nβˆ’2/3.

No isolated verticesFirst moment

Show that at p=2ln⁑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≀neβˆ’p(nβˆ’1)=nβ‹…nβˆ’2(nβˆ’1)/n=nβˆ’1+2/nβ†’0. By Markov, a.a.s. there are none.

From Li and Lin, Elementary Methods of Graph Ramsey Theory (Springer, 2022)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 4.10Very sparse random graphs are forests

Show that if np→0, almost every graph in G(n,p) is a forest.

Hint

Expected number of cycles, then Markov.

Solution

The number of possible k-cycles is (n)k2k≀nk2k. So the expected number of cycles is at most βˆ‘kβ‰₯3(np)k2k≀(np)36(1βˆ’np)β†’0. By Markov, Pr(some cycle)≀E[#cycles]β†’0.

Exercise 4.12The threshold for containing H

Let ρ(H)=max{e(F)/v(F):FβŠ†H}. Prove p=nβˆ’1/ρ(H) is a threshold for G(n,p) to contain H.

Hint

Below the threshold, the densest subgraph F is already unlikely to appear. Above it, use the second moment method, with the variance controlled by overlapping copies.

Solution

Below: pβ‰ͺnβˆ’1/ρ. Let FβŠ†H attain ρ. E[#F]≀nv(F)pe(F)=(npρ)v(F)β†’0. No copy of F means no copy of H.

Above: p≫nβˆ’1/ρ. Let X count copies of H; EX≍nv(H)pe(H). Grouping pairs of copies by their intersection F (with e(F)β‰₯1) gives

VarX(EX)2≀Cβˆ‘FβŠ†H,Β e(F)β‰₯11nv(F)pe(F).

Each term is (npe(F)/v(F))βˆ’v(F)≀(npρ)βˆ’v(F)β†’0, because e(F)/v(F)≀ρ and p<1. Chebyshev gives Pr(X=0)≀VarX/(EX)2β†’0.

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 A1,…,AN have a dependency graph D if each Ai is mutually independent of the family {Aj:jβ‰ i,Β ijβˆ‰D}. Typical case: each event is determined by a set of independent coin flips, and i∼j when the two sets overlap.
Symmetric local lemma. If Pr(Ai)≀p for all i, every vertex of D has degree at most d, and
ep(d+1)≀1,

then Pr(β‹‚iAi―)>0: with positive probability no bad event happens.

For r(k,k): colour Kn at random and let AS be the event that the k-set S is monochromatic, so p=21βˆ’(k2). AS depends only on the edges inside S, so it is independent of all AT with |S∩T|≀1. The number of other T with |S∩T|β‰₯2 is

d=βˆ‘i=2kβˆ’1(ki)(nβˆ’kkβˆ’i).
Three lower bounds, compared. As kβ†’βˆž,
union:Β 1e2k2k/2,deletion:Β 1ek2k/2,local lemma (Spencer):Β 2ek2k/2,

each up to a factor 1+o(1). Nothing better than 2k in the exponent is known. The same chapter uses the local lemma for r(3,n)β‰₯c(n/log⁑n)2, and the triangle-free process improves this to (14βˆ’o(1))n2/log⁑n.

Explore

Each bound divided by k2k/2. Dashed lines: the limits 1/(e2), 1/e and 2/e. union deletion local lemma

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)21βˆ’k≀1, then the hypergraph is 2-colourable.

  1. Set up the random experiment and the bad events.

    Colour each vertex red or blue independently with probability 12. For each edge f, let Af be the event that f is monochromatic.

  2. What is Pr(Af)?

    All red or all blue: 2β‹…2βˆ’k=21βˆ’k.

  3. Find a dependency graph with maximum degree d.

    Af is determined by the colours on f. The events Ag with g∩f=βˆ… are determined by colours off f, so Af is mutually independent of all of them together. Joining f to the edges it meets gives degree at most d.

  4. 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)≀512, that is d≀187, with no limit at all on the total number of edges. The union bound would need fewer than 29=512 edges in total.

Check your understanding

Why is the event "S is monochromatic" independent of all the events "T is monochromatic" with |S∩T|≀1?

  1. Such a T shares no edge with S, so those events depend only on edges outside S.
  2. Because such a T shares no vertex with S.T may share one vertex. What do the events actually depend on?
  3. 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?

  1. 2
  2. 2That is the gain over the deletion method, not over the union bound.
  3. eDivide the two constants: 2e/1e2.
2/e1/(e2)=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≀16.

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

  1. No. Independent events, each with probability below 1, can all be avoided, since ∏(1βˆ’pi)>0.
  2. Yes, the local lemma is exact when d=0.Try p=12 with two independent events.
  3. No, they need βˆ‘pi<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β‰₯9.

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)21βˆ’k=eβ‹…73/256β‰ˆ0.78≀1, so the worked example applies. For larger k the left side only shrinks, since k(kβˆ’1)+1 grows polynomially while 2kβˆ’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 2k/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≀2k/eβˆ’1 we get ep(d+1)≀e2βˆ’kβ‹…2k/e=1, so with positive probability no clause fails.

From Li and Lin, Elementary Methods of Graph Ramsey Theory (Springer, 2022)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 5.2Local Lemma bounds for multicolour Ramsey numbers

Use the LovΓ‘sz Local Lemma to bound rk(Kn) and rk(Kn,n) from below, and compare with the basic first-moment method.

Hint

Colour KN uniformly with k colours. The bad event for an n-set has probability k1βˆ’(n2) and depends on at most (n2)(Nnβˆ’2) others. Use ep(d+1)≀1.

Solution

Cliques. First moment: if (Nn)k1βˆ’(n2)<1, a good colouring exists, giving rk(Kn)>(1+o(1))nek(nβˆ’1)/2.

Local Lemma: two n-sets interact only if they share at least two vertices, so d+1≀(n2)(Nnβˆ’2). The condition ek1βˆ’(n2)(n2)(Nnβˆ’2)≀1 holds when Nnβˆ’2≲(nβˆ’2)!k(n2)βˆ’1/n2. Since ((n2)βˆ’1)/(nβˆ’2)=(n+1)/2 exactly, this gives

rk(Kn)>(1+o(1))nek(n+1)/2,

a factor k better than the first moment (for k=2: 2en2n/2 versus 1e2n2n/2, the familiar factor 2).

Bicliques. A fixed Kn,n is monochromatic with probability k1βˆ’n2. First moment: roughly N2nk1βˆ’n2/(n!)2<1, giving Nβ‰ˆnekn/2. Local Lemma: copies sharing an edge number at most n2N2nβˆ’2/((nβˆ’1)!)2, giving N2nβˆ’2≲kn2βˆ’1((nβˆ’1)!)2/n2, so rk(Kn,n)>cnk(n+1)/2 since (n2βˆ’1)/(2nβˆ’2)=(n+1)/2. Again the Local Lemma gains about a factor k or more over the first moment.

Exercise 5.5Two-colouring hypergraphs with few intersections

Let rβ‰₯2. If every edge of a hypergraph has at least r vertices and meets at most 2rβˆ’2βˆ’1 other edges, show the vertices can be 2-coloured so that no edge is monochromatic.

Hint

Colour randomly and split "edge e is monochromatic" into two events, Re (all red) and Be (all blue). In the lopsided Local Lemma, Re only needs to be joined to the events Bf with f∩eβ‰ βˆ….

Solution

Colour each vertex red or blue independently. Pr(Re)=Pr(Be)≀2βˆ’r.

Lopsidependency. Let S be any set of events among the Rf (any fβ‰ e) and the Bf with f∩e=βˆ…. Conditioning on none of them happening makes Re no more likely: "not Rf" is a decreasing event in the set of red vertices, Re is increasing, and events on disjoint vertex sets are independent, so Harris's inequality gives Pr(Reβˆ£β‹‚SAΒ―)≀Pr(Re). Hence Re needs neighbours only Bf with f∩eβ‰ βˆ… (including Be): at most 2rβˆ’2 of them. Symmetrically for Be.

Local Lemma. With all xi=x=2βˆ’(rβˆ’1), condition (5.5) asks 2βˆ’r≀x(1βˆ’x)2rβˆ’2. Since (1βˆ’x)2rβˆ’2β‰₯1βˆ’2rβˆ’2x=12, the right side is at least 2βˆ’r. So with positive probability no Re or Be occurs: a proper 2-colouring exists.

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 F is a family of subsets of {1,…,t}, each of odd size, and any two distinct members meet in an even number of elements, then |F|≀t.
Fisher-type inequality. If distinct subsets of {1,…,t} pairwise meet in exactly Ξ»β‰₯1 elements, there are at most t of them.
The graph. Let Nt have the (t3) three-element subsets of {1,…,t} as vertices, with A∼B when |A∩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)>(t3).

That is only polynomial in t, against ErdΕ‘s's exponential 2t/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 eclog⁑nlog⁑log⁑n on n vertices. The same intersection theorems disproved Borsuk's conjecture: Kahn and Kalai found bounded sets in Rd that cannot be split into fewer than 1.2d pieces of smaller diameter.

Explore

Each chip is a vertex of Nt. 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.

  1. Turn each set into a vector. Over which field?

    Over F2: let vA∈F2t be the indicator vector of A. Then vAβ‹…vB=|A∩B|mod2.

  2. What are vA⋅vA and vA⋅vB for A≠B?

    vAβ‹…vA=|A|≑1 since sizes are odd, and vAβ‹…vB=|A∩B|≑0 since intersections are even.

  3. Show the vectors are linearly independent.

    If βˆ‘AcAvA=0, take the dot product with vB: every term vanishes except cBvBβ‹…vB=cB. So every cB=0.

  4. Conclude.

    Linearly independent vectors in F2t number at most t, so |F|≀t. For triples, an independent set of Nt is such a family, so Ξ±(Nt)≀t.

Check your understanding

Which family is a clique in Nt?

  1. The seven lines of the Fano plane, such as {1,2,3},{1,4,5},{2,4,6},…
  2. All triples containing the element 1.{1,2,3} and {1,2,4} share two elements, so they are not adjacent.
  3. 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 N7, 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?

  1. vAβ‹…vA becomes 0 and the independence argument fails; indeed there can be 2⌊t/2βŒ‹ such sets.
  2. Nothing; the same bound t holds.Try all unions of the pairs {1,2},{3,4},…
  3. The vectors no longer live in F2t.They still do. Look at which dot product changes.
Unions of the disjoint pairs {1,2},{3,4},… all have even size and even intersections: 2⌊t/2βŒ‹ sets ("Eventown"). The diagonal entries of the Gram matrix are what make the odd case linear in t.

Nt gives r(t+1,t+1)>(t3), and ErdΕ‘s gives r(t+1,t+1)>2(t+1)/2. For t=10, (103)=120 beats 25.5β‰ˆ45. What happens as t grows?

  1. ErdΕ‘s's bound wins for every tβ‰₯19: it is exponential, (t3) is cubic.
  2. Nt stays ahead, because explicit graphs are better than random ones.Compare growth rates: t3/6 against 2t/2.
  3. They stay within a constant factor of each other.The ratio 2t/2/t3 tends to infinity.
At t=18: 816 against 29.5β‰ˆ724; 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+Ο΅)t; none is known.

Practice

The clique boundA positive definite Gram matrix

Show directly that a family of triples in {1,…,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, vAβ‹…vA=3 and vAβ‹…vB=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 Rt, so there are at most t.

TetrahedraAn independent set of size t

When 4∣t, find an independent set of size exactly t in Nt, so the Oddtown bound is attained.

Solution

Split {1,…,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β‹…t/4=t triples. The "Tetrahedra" button in the explorer shows this for t=8.

From Li and Lin, Elementary Methods of Graph Ramsey Theory (Springer, 2022)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 6.3The dual Fisher inequality

Let H=(V,E) be a simple hypergraph in which every pair of vertices lies in exactly Ξ»β‰₯1 edges, with |V|β‰₯2 and no edge equal to V. Show |E|β‰₯|V|.

Hint

With M the VΓ—E incidence matrix, MMT=Ξ»J+D with D=diag(rvβˆ’Ξ»), where rv is the degree.

Solution

(MMT)uv counts edges containing both u and v: Ξ» off the diagonal, rv on it. So MMT=Ξ»J+D.

Each rv>Ξ». Pick uβ‰ v. The rv edges through v include the Ξ» through both u and v; if rv=Ξ», every edge through v would contain every other vertex, i.e. equal V, which is excluded. So D is positive definite, Ξ»J is positive semidefinite, and MMT is positive definite of size |V|. Hence |V|=rank(MMT)≀rankM≀|E|.

Exercise 6.4Mod-p town and mod-pk town

Generalise the Oddtown theorem to "mod p town", and to "mod pk town".

Hint

For mod p, the incidence vectors are linearly independent over Fp. For pk, use Lucas' theorem: (apj)modp is the j-th base-p digit of a.

Solution

Mod p. Let A1,…,AmβŠ†[n] with |Ai|β‰’0 and |Ai∩Aj|≑0(modp) for iβ‰ j. The incidence vectors vi∈Fpn have viβ‹…vj=0 for iβ‰ j and viβ‹…viβ‰ 0. If βˆ‘civi=0, dotting with vj gives cj=0. So the vi are independent and m≀n.

Mod q=pk. Suppose |Ai|β‰’0(modq) and |Ai∩Aj|≑0(modq) for iβ‰ j. Then mβ‰€βˆ‘j=0kβˆ’1(npj). Proof: for each i choose j(i)<k such that the j(i)-th base-p digit of |Ai| is nonzero. For j<k let wi(j)∈Fp([n]pj) be the indicator of the pj-subsets of Ai. Then wi(j)β‹…wl(j)=(|Ai∩Al|pj), which mod p is the j-th digit of |Ai∩Al|: zero for iβ‰ l (all digits below k vanish), nonzero for i=l and j=j(i). So within each class {i:j(i)=j} the vectors wi(j) are independent, giving at most (npj) sets per class.

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 Kr+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. 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 ⌊n/rβŒ‹ or ⌈n/rβŒ‰.
TurΓ‘n's theorem. ex(n,Kr+1)=e(T(n,r))≀(1βˆ’1r)n22, and T(n,r) is the only extremal graph.
ErdΕ‘s–Stone–Simonovits. ex(n,H)=(1βˆ’1Ο‡(H)βˆ’1+o(1))n22. The chromatic number decides the answer to first order.

For bipartite H that first-order answer is o(n2), and the real question is the exponent. KΕ‘vΓ‘ri, SΓ³s and TurΓ‘n: ex(n,Ks,t)=O(n2βˆ’1/s) for s≀t. For C4=K2,2 the order n3/2 is right: the ErdΕ‘s–RΓ©nyi polarity graph, built from the projective plane over Fq, has q2+q+1 vertices, no C4, and about 12q3 edges.

Why Ramsey cares. In a k-colouring of KN some colour has at least (N2)/k edges. If that exceeds ex(N,H), that colour contains H. Bipartite TurΓ‘n numbers therefore bound multicolour Ramsey numbers, such as rk(C4)=O(k2).

Explore

All edges between different parts are drawn. Drag a vertex into another part. A complete r-partite graph never contains Kr+1: two of any r+1 vertices share a part.

Worked example

Show that a graph on n vertices with no 4-cycle has at most n4(1+4nβˆ’3) edges.

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

    βˆ‘v(d(v)2): choose the centre v, then two of its neighbours.

  2. Why is this at most (n2) when there is no C4?

    Each cherry has a pair of endpoints {x,y}. If two cherries had the same endpoints and different centres v≠w, then x,v,y,w would be a 4-cycle. So each pair {x,y} is used at most once.

  3. Use convexity to bring in the average degree dΒ―=2e/n.

    x↦(x2) is convex, so n(dΒ―2)β‰€βˆ‘v(d(v)2)≀(n2), that is dΒ―(dΒ―βˆ’1)≀nβˆ’1.

  4. Solve for e.

    d¯≀1+4nβˆ’32, so e=ndΒ―2≀n4(1+4nβˆ’3)β‰ˆ12n3/2. The polarity graph shows the constant 12 cannot be improved.

Check your understanding

To first order, what is ex(n,C5)?

  1. n2/4
  2. o(n2)That holds for bipartite graphs. Is C5 bipartite?
  3. n2/3Ο‡(C5)=3, so the formula gives 1βˆ’12, not 1βˆ’13.
Ο‡(C5)=3 gives (1βˆ’12)n22=n24. The complete bipartite graph Kn/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?

  1. It goes up by 2.
  2. It goes up by 3.The moved vertex belongs to its new part too, so that part then has 5 vertices, not 4.
  3. 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β‰₯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?

  1. About n.
  2. About n/2.Kn/2,n/2 has average degree n/2 but is full of 4-cycles.
  3. Bounded by a constant.The polarity graph has degrees about n and no C4.
The worked example gives dΒ―(dΒ―βˆ’1)≀nβˆ’1, so d¯≲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 n2/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)≀n for each edge. Summing over edges, each vertex v appears d(v) times, so βˆ‘vd(v)2≀ne. By Cauchy–Schwarz, βˆ‘vd(v)2β‰₯(2e)2/n. Hence 4e2/n≀ne, so e≀n2/4.

Many colours, one 4-cycleTurΓ‘n meets Ramsey

Use the worked example to show that every k-colouring of the edges of KN with N=k2+k+2 contains a monochromatic C4.

Hint

Some colour class has at least (N2)/k edges. Compare with N4(1+4Nβˆ’3).

Solution

It suffices that (N2)/k>N4(1+4Nβˆ’3), that is 2(Nβˆ’1)k>1+4Nβˆ’3. With Nβˆ’1=k2+k+1 the left side is 2k+2+2k. On the right, 4Nβˆ’3=(2k+1)2+4, so 4Nβˆ’3<2k+1+22k+1, and the right side is less than 2k+2+22k+1<2k+2+2k. So rk(C4)≀k2+k+2.

From Li and Lin, Elementary Methods of Graph Ramsey Theory (Springer, 2022)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 7.4TurΓ‘n numbers of paths and stars

What are ex(n,Pm) (path on m vertices) and ex(n,K1,m)?

Hint

A star-free graph has bounded maximum degree. For paths, disjoint copies of Kmβˆ’1 are extremal, and the ErdΕ‘s–Gallai theorem gives the matching upper bound.

Solution

Stars. K1,m-free means maximum degree at most mβˆ’1, so e≀n(mβˆ’1)/2. For nβ‰₯m there is a graph with all degrees mβˆ’1 (if n(mβˆ’1) is even) or all but one (otherwise), so ex(n,K1,m)=⌊n(mβˆ’1)/2βŒ‹. (For n<m it is (n2).)

Paths. The ErdΕ‘s–Gallai theorem gives e(G)≀(mβˆ’2)n2 for Pm-free G. Proof idea: a longest path in a connected Pm-free graph, together with a PΓ³sa rotation argument, shows some vertex has degree ≀(mβˆ’2)/2; delete it and induct. Disjoint copies of Kmβˆ’1 have exactly (mβˆ’2)n2 edges, so equality holds when (mβˆ’1)∣n. In general, with n=q(mβˆ’1)+r, 0≀r<mβˆ’1, the extremal number is q(mβˆ’12)+(r2) (Faudree–Schelp), attained by qKmβˆ’1βˆͺKr.

Exercise 7.5Odd cycles have bipartite extremal graphs

Prove that ex(n,C2m+1)=⌊n2/4βŒ‹ for large n.

Hint

The lower bound is K⌊n/2βŒ‹,⌈n/2βŒ‰. For the upper bound, combine ErdΕ‘s–Stone with the stability method: a nearly extremal C2m+1-free graph is close to bipartite, and then any edge inside a part creates an odd cycle.

Solution

Lower bound. The balanced complete bipartite graph has no odd cycles and ⌊n2/4βŒ‹ edges.

Upper bound (outline). Let G be C2m+1-free with e(G)β‰₯⌊n2/4βŒ‹.

  1. By deleting low-degree vertices one at a time (each deletion of a vertex of degree <(12βˆ’Ξ΄)n keeps the edge count above n2/4 relative to the new order) one may assume minimum degree β‰₯(12βˆ’Ξ΄)n.
  2. The ErdΕ‘s–Simonovits stability theorem (since Ο‡(C2m+1)=3) says G can be made bipartite by deleting o(n2) edges. Take a max-cut (X,Y).
  3. If some edge xxβ€² lies inside X, the high minimum degree gives x and xβ€² many neighbours in Y, and between NY(x) and NX of those there are paths of every even length up to 2m, closing an odd cycle of length 2m+1. So G is bipartite, and e(G)β‰€βŒŠn2/4βŒ‹.

Each step needs n large compared with m and the stability constants, which is why the statement says "for large n". This is an outline: the stability theorem is quoted, not proved.

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 Ξ±(G) words.
Strong product. In G⊠H (written ∧ 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⊠n.
Shannon capacity. Θ(G)=limnΞ±(G⊠n)1/n=supnΞ±(G⊠n)1/n. Always Θ(G)β‰₯Ξ±(G). LovΓ‘sz proved Θ(C5)=5, attained by the two-letter code below; even cycles have Θ(C2m)=m. Θ(C7) is unknown.
ErdΕ‘s–McEliece–Taylor. The largest possible Ξ±(G1βŠ β‹―βŠ Gn) over graphs with Ξ±(Gi)<ki is exactly r(k1,…,kn)βˆ’1.

For n=2, k1=k2=3: Ξ±(C5)=2<3, and Ξ±(C5⊠C5)=5=r(3,3)βˆ’1. The pentagon reaches the maximum.

Explore

Cell (i,j) is the word "ij". Letters i and iΒ±1(mod5) 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 Ξ±(C5⊠C5)=5, with letters 0,…,4 and i confusable with iΒ±1mod5.

  1. Show that the five words (i,2imod5) form a code.

    Take two of them, with first letters differing by Ξ΄=jβˆ’iβ‰ 0. If Ξ΄=Β±1 the first letters are confusable, but the second letters differ by 2Ξ΄=Β±2, which is not confusable. If Ξ΄=Β±2 the first letters already differ by 2. Either way, some coordinate tells the words apart.

  2. 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 C5, so there are at most 2.

  3. Add up over the five windows {i,i+1}.

    Each codeword's first letter lies in exactly two windows. So 2|C|≀5β‹…2, giving |C|≀5.

  4. What does this give for Θ(C5)?

    Θ(C5)β‰₯Ξ±(C5⊠2)1/2=5β‰ˆ2.236, better than Ξ±(C5)=2. LovΓ‘sz's theta function gives the matching upper bound, so Θ(C5)=5: 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?

  1. 12log2⁑5β‰ˆ1.16
  2. log2⁑5β‰ˆ2.32That is per word. Each word costs two channel uses.
  3. 1That is the single-letter rate log2⁑α(C5). The two-letter code does better.
Five messages in two channel uses: log2⁑5 bits per two letters. Shannon capacity in bits is log2⁑Θ, and for C5 this code already achieves it.

Why is Ξ±(G⊠mn)β‰₯Ξ±(G⊠n)m?

  1. Concatenate m codewords of length n: two such long words differ in some block, and that block tells them apart.
  2. Because Ξ± is multiplicative under ⊠.It is only super-multiplicative: Ξ±(C5⊠2)=5>2β‹…2.
  3. Because G⊠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 Θ exists and equals the supremum.

G and H both have independence number at most 2. Why must Ξ±(G⊠H)≀5?

  1. 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.
  2. Because Ξ±(G⊠H)=Ξ±(G)Ξ±(H)≀4.The pentagon gives 5, so the product formula fails.
  3. Because G⊠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 Θ(C4)=2.

Hint

C4 is covered by two cliques (edges). What covers C4⊠n?

Solution

Ξ±(C4)=2 gives Θβ‰₯2. Cover C4 by the cliques {0,1} and {2,3}. Products of cliques are cliques in the strong product, so C4⊠n is covered by 2n cliques. An independent set has at most one vertex per clique, so Ξ±(C4⊠n)≀2n and Θ(C4)=2.

Long words for the pentagonConcatenation

Show that Ξ±(C5⊠2n)β‰₯5n, and that Ξ±(C5⊠(2n+1))β‰₯2β‹…5n.

Solution

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

From Li and Lin, Elementary Methods of Graph Ramsey Theory (Springer, 2022)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 8.1Independence numbers of powers of C5

Determine α(C5∧2n) (strong powers). What can be said about α(C5∧(2n+1))?

Hint

Ξ±(C5∧2)=5 by an explicit independent set, and LovΓ‘sz's Ο‘(C5)=5 is multiplicative and bounds Ξ±.

Solution

{(i,2imod5):i∈Z5} is independent in C5∧2, so Ξ±(C5∧2)β‰₯5, and by supermultiplicativity Ξ±(C5∧2n)β‰₯5n. LovΓ‘sz's bound gives Ξ±(G∧k)≀ϑ(G)k, with Ο‘(C5)=5. So Ξ±(C5∧2n)=5n.

For odd powers, 2β‹…5n≀α(C5∧(2n+1))β‰€βŒŠ5n5βŒ‹ (using Ξ±(C5)=2 for the lower bound). The exact value is not determined by these bounds; for instance Ξ±(C5∧3)=10, while the upper bound gives 11.

Exercise 8.4Shannon capacity of even cycles

Prove Θ(C2m)=m.

Hint

An independent set of size m and a cover by m cliques (edges).

Solution

Ξ±(C2m)=m (alternate vertices), so Ξ±(C2m∧k)β‰₯mk. The vertices of C2m are covered by m disjoint edges, which are cliques; products of these cover C2m∧k by mk cliques, and an independent set meets each clique at most once. So Ξ±(C2m∧k)=mk and Θ=limΞ±(G∧k)1/k=m.

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(dn)tβˆ’(nr)(mn)tβ‰₯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 E|A|=βˆ‘v(d(v)/n)tβ‰₯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 (nr)(m/n)t.
  • Some choice has |A|βˆ’Yβ‰₯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 ex(n,H)≀cHn2βˆ’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

Worked example

Let H be K4 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.7n3/2 edges contains H.

  1. 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.

  2. Apply the lemma with r=2, m=10, t=2. What is the second term?

    (n2)(10/n)2<n22β‹…100n2=50.

  3. How large must d be?

    We need n(d/n)2βˆ’50β‰₯4, i.e. d2/nβ‰₯54, i.e. dβ‰₯54n.

  4. Translate into edges.

    e=nd/2, so eβ‰₯542n3/2β‰ˆ3.67n3/2 suffices. Hence ex(n,H)<3.7n3/2, matching the n2βˆ’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?

  1. (3/40)3β‰ˆ0.0004
  2. 3/40That is for one pick. All three picks must land among the 3 common neighbours.
  3. (6/40)3The picks must be adjacent to both u and v, so they must land in the intersection of the two neighbourhoods.
u,v∈A means every pick is a common neighbour of u and v. The picks are independent, each succeeding with probability 3/40.

Why is E|A|β‰₯n(d/n)t, even if G is far from regular?

  1. E|A|=βˆ‘v(d(v)/n)t, and x↦xt is convex, so the sum is at least n times the value at the average.
  2. Because every vertex has degree d.d is only the average degree. The argument must handle uneven degrees.
  3. Because A always contains T.T is usually not inside its own common neighbourhood.
By Jensen, 1nβˆ‘v(d(v)/n)tβ‰₯(1nβˆ‘vd(v)/n)t=(d/n)t. Uneven degrees only help.

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

  1. It tends to 0, because it equals (nr)n(m/d)t and m/d<1.
  2. It grows, because (nr) is huge.(nr) is fixed while t grows. Which factor depends on t?
  3. 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 K5Same recipe, new numbers

Repeat the worked example for K5 with each edge subdivided. What constant c do you get in ex(n,H)≀cn3/2?

Hint

Now |U|β‰₯5, 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 152/2=112.5, so we need d2/nβ‰₯117.5. Then e=nd/2β‰₯117.52n3/2β‰ˆ5.42n3/2 suffices.

The size of AIndicators

Prove E|A|=βˆ‘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|=βˆ‘v1[v∈A], and v∈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.

From Li and Lin, Elementary Methods of Graph Ramsey Theory (Springer, 2022)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 9.2Degeneracy of some familiar graphs

Show Pn is 1-degenerate. What about K1,n, Cn, trees Tn and Km,n?

Hint

d-degenerate means every subgraph has a vertex of degree at most d.

Solution

Every subgraph of a forest is a forest, which has a vertex of degree ≀1. So Pn, K1,n and every tree are 1-degenerate (and not 0-degenerate once they have an edge).

Cn is 2-degenerate: proper subgraphs are forests, and Cn itself has minimum degree 2. It isn't 1-degenerate.

Km,n with m≀n is m-degenerate: in any subgraph, a vertex on the larger side has degree at most m. It isn't (mβˆ’1)-degenerate since its minimum degree is m.

Exercise 9.7Embedding degenerate bipartite graphs greedily

Let G be bipartite with parts U1,U2, such that every r vertices in U1 have at least n common neighbours, and likewise in U2. Prove G contains every r-degenerate bipartite graph H of order n.

Hint

Order V(H) so each vertex has at most r neighbours earlier. Embed in that order.

Solution

Since H is r-degenerate, repeatedly removing a vertex of degree ≀r and reversing gives an ordering v1,…,vn in which each vi has at most r neighbours among v1,…,viβˆ’1. Map the parts of H to U1,U2.

Embed vi given v1,…,viβˆ’1. Its earlier neighbours lie in the other part; their images are at most r vertices of, say, U2. Enlarge to exactly r vertices if necessary. Their common neighbourhood in U1 has at least n vertices, all adjacent to the images of vi's earlier neighbours. At most iβˆ’1<n of them are used, so pick an unused one. After n steps H is embedded.

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β†’βˆž vertices. The following are equivalent; graphs satisfying them are called quasi-random with density p.

  • Cycle count. e(G)β‰₯(1+o(1))pn22 and the number of closed 4-walks, tr⁑A4, is at most (1+o(1))p4n4.
  • Discrepancy. For every vertex set S, e(S)=p|S|22+o(n2).
  • Eigenvalues. Ξ»1=(1+o(1))pn and every other eigenvalue has |Ξ»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 Ξ»=maxiβ‰₯2|Ξ»i|, then for all vertex sets S,T,
|e(S,T)βˆ’d|S||T|n|≀λ|S||T|.

The Paley graph Pq is qβˆ’12-regular with other eigenvalues βˆ’1Β±q2, so it is quasi-random with p=12. 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 Β±n, roughly where a random graph's non-top eigenvalues sit.

Worked example

For a prime q≑1(mod4), find the eigenvalues of Pq and use them to show Ξ±(Pq)≀q.

  1. Pq is a circulant graph: x∼y depends only on xβˆ’y. What are the eigenvectors?

    For Ο‰=e2Ο€i/q and each j∈Zq, the vector uj=(Ο‰jx)x is an eigenvector with eigenvalue Ξ»j=βˆ‘s∈QΟ‰js, where Q is the set of nonzero squares. For j=0 this is |Q|=qβˆ’12.

  2. Relate Ξ»j (jβ‰ 0) to the Gauss sum gj=βˆ‘x∈ZqΟ‰jx2.

    As x runs over Zq, x2 takes the value 0 once and each nonzero square twice. So gj=1+2Ξ»j.

  3. Use the classical fact gj2=q for q≑1(mod4) (gj is real). What are the eigenvalues?

    gj=Β±q, so Ξ»j=βˆ’1Β±q2 for every jβ‰ 0. Half of them take each sign.

  4. Apply Hoffman's bound α≀nβˆ’Ξ»mindβˆ’Ξ»min for d-regular graphs.

    With βˆ’Ξ»min=1+q2 and dβˆ’Ξ»min=q+q2: Ξ±(Pq)≀qβ‹…1+qq+q=q. For q=17 this gives α≀4; the truth is 3. The spectrum alone gets close.

Check your understanding

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

  1. No. If S is one of the cliques, e(S)β‰ˆ|S|2/2, twice what density 12 predicts.
  2. Yes, the density is right.Density is a single number. Quasi-randomness asks every large subset to have the right density.
  3. 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?

  1. Relabelling replaces A by PAPβˆ’1 for a permutation matrix P, which has the same eigenvalues and the same tr⁑A4.
  2. Because the shuffle is undone before computing.It isn't. The stats are computed from the shuffled matrix.
  3. 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 Ξ»=maxiβ‰₯2|Ξ»i|=30. For sets S,T of size 100, what range does the mixing lemma give for e(S,T)?

  1. Between 2000 and 8000.
  2. Between 4970 and 5030.The error term is Ξ»|S||T|, not Ξ».
  3. Exactly 5000.5000 is the centre, d|S||T|/n. The lemma allows an error.
Centre 500β‹…100β‹…100/1000=5000, error at most 30β‹…100=3000. For larger sets the relative error shrinks: it is Ξ»n/(d|S||T|).

Practice

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

Let G have n vertices and e=pn2/2 edges. Show tr⁑A4β‰₯p4n4.

Hint

tr⁑A4=βˆ‘Ξ»i4. Bound Ξ»1 below using the all-ones vector.

Solution

By the Rayleigh quotient with 1, Ξ»1β‰₯1TA1n=2en=pn. So tr⁑A4=βˆ‘iΞ»i4β‰₯Ξ»14β‰₯p4n4. 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)β‰ˆ2(s/22)β‰ˆs2/4=12β‹…s22: exactly what density 12 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.

From Li and Lin, Elementary Methods of Graph Ramsey Theory (Springer, 2022)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 10.1A "too strong" quasi-randomness condition

Let G have order n with |N(v)∩B|=p|B|+o(n) for every vertex v and every subset B. Is G quasi-random for fixed p?

Hint

Try B=N(v) and B=V.

Solution

For 0<p<1 no such graph exists for large n. Taking B=V gives |N(v)|=pn+o(n); taking B=N(v) gives |N(v)|=p|N(v)|+o(n), so |N(v)|=o(n). These are incompatible. So the statement is vacuously true but says nothing.

The useful version restricts the condition (for example to the sum over v, or to sets B not built from v's neighbourhood). Taking B=N(u) in a sensible version gives codegrees |N(u)∩N(v)|=p2n+o(n) for almost all pairs; with degrees β‰ˆpn, the Chung–Graham–Wilson theorem then shows G is quasi-random.

Exercise 10.5Eigenvalues of Cayley graphs

Let S be an inverse-closed subset of a finite group G not containing the identity. Show that for a character Ο‡ of G, the vector (Ο‡(g))g∈G is an eigenvector of the Cayley graph Ξ“(G,S) with eigenvalue βˆ‘s∈SΟ‡(s).

Hint

The neighbours of g are sg, s∈S, and a (one-dimensional) character is multiplicative.

Solution

(AΟ‡)(g)=βˆ‘s∈SΟ‡(sg)=(βˆ‘s∈SΟ‡(s))Ο‡(g). Since S=Sβˆ’1, A is symmetric, so the eigenvalue is real.

For abelian G there are |G| characters, orthogonal and hence a basis, so these are all the eigenvalues. For non-abelian groups the one-dimensional characters give some eigenvalues; the rest come from higher-dimensional irreducible representations ρ, as eigenvalues of βˆ‘s∈Sρ(s).

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

Van der Waerden and regularity

Colour 1,2,…,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,…,N} contains a monochromatic arithmetic progression of length t. The least such N is wk(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)=e(X,Y)|X||Y|. The pair is Ξ΅-regular if |d(Xβ€²,Yβ€²)βˆ’d(X,Y)|≀Ρ for all Xβ€²βŠ†X, Yβ€²βŠ†Y with |Xβ€²|β‰₯Ξ΅|X|, |Yβ€²|β‰₯Ξ΅|Y|. Edges between a regular pair are spread like random edges.
SzemerΓ©di's regularity lemma. For every Ξ΅>0 and m there is M such that every graph with at least m vertices has a partition V0βˆͺV1βˆͺβ‹―βˆͺVk, with m≀k≀M, |V0|≀Ρn, |V1|=β‹―=|Vk|, in which all but at most Ξ΅k2 of the pairs (Vi,Vj) are Ξ΅-regular.

M does not depend on the graph, but it grows like a tower of 2s of height polynomial in 1/Ξ΅, 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 RT(n,K4,o(n))=(18+o(1))n2.

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)≀9: every red/blue colouring of {1,…,9} has a monochromatic 3-term progression. Suppose one doesn't, and look at 4, 5 and 6.

  1. 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.

  2. So 4 and 6 differ, say 4 red and 6 blue. Reflecting x↦10βˆ’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".

  3. 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).

  4. Find the contradiction.

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

Check your understanding

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

  1. 1, 5, 9
  2. 3, 6, 93 is blue and 6 is red.
  3. 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 14. Is (X,Y) 0.1-regular?

  1. No: those two halves have density 1, far from 14.
  2. Yes: regularity only asks about the overall density.It asks about every pair of subsets of at least Ξ΅ times the size.
  3. Yes: halves are too small to count.The threshold is Ξ΅|X|=10 vertices, and 50 is well above it.
With Xβ€² and Yβ€² the two halves, |d(Xβ€²,Yβ€²)βˆ’d(X,Y)|=34>0.1. A regular pair cannot hide a dense block on a large piece.

V1,V2,V3 are pairwise Ξ΅-regular with densities d12,d13,d23, all well above Ξ΅. Roughly how many triangles have one vertex in each?

  1. About d12d13d23|V1||V2||V3|, as for random edges.
  2. Possibly none.That can happen for dense pairs that are not regular. Regularity is what rules it out.
  3. About (d12+d13+d23)|V1||V2||V3|/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,…,34} contain? How many monochromatic ones does a random 2-colouring have on average?

Hint

For common difference Ξ΄, the first term a needs a+3δ≀34.

Solution

For Ξ΄=1,…,11 there are 34βˆ’3Ξ΄ choices of a, giving βˆ‘Ξ΄=111(34βˆ’3Ξ΄)=374βˆ’198=176. Each is monochromatic with probability 2β‹…2βˆ’4=18, 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+Ξ΄,…,a+(Nβˆ’1)Ξ΄ is 2-coloured with Nβ‰₯w(t), it contains a monochromatic t-term progression.

Solution

Colour i∈{1,…,N} with the colour of a+(iβˆ’1)Ξ΄. A monochromatic progression i,i+c,… gives the monochromatic progression a+(iβˆ’1)Ξ΄,Β a+(iβˆ’1+c)Ξ΄,…, with difference cΞ΄. This is the kind of step used in the proofs of the recursive bounds for wk(t).

From Li and Lin, Elementary Methods of Graph Ramsey Theory (Springer, 2022)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 11.1w(3)=9

Show the van der Waerden number w(3)=9: every 2-colouring of [9] has a monochromatic 3-term progression, and some 2-colouring of [8] doesn't.

Hint

Colour [8] as RRBBRRBB. For [9], fix the colour of 5 and branch on 4 and 6.

Solution

[8]. RRBBRRBB: the red set {1,2,5,6} and the blue set {3,4,7,8} contain no 3-term progressions (check the few candidates).

[9]. Suppose there's no monochromatic progression; say 5 is red.

  • 4,6 both red: 4,5,6.
  • 4,6 both blue: then 2 is red (else 2,4,6) and 8 is red (else 4,6,8), and 2,5,8 is red.
  • 4 red, 6 blue (the other mixed case is the mirror image x↦10βˆ’x): 3 blue (3,4,5); 9 red (3,6,9); 1 blue (1,5,9); 2 red (1,2,3); 8 blue (2,5,8); 7 red (6,7,8); and 5,7,9 is red.

Every case fails, so w(3)=9.

Exercise 11.8Regularity is monotone in Ο΅

If (X,Y) is Ο΅-regular and Ο΅β€²β‰₯Ο΅, show it is Ο΅β€²-regular.

Hint

Write out the definition and compare the two conditions.

Solution

Ο΅β€²-regularity asks that |d(Xβ€²,Yβ€²)βˆ’d(X,Y)|≀ϡ′ whenever |Xβ€²|β‰₯Ο΅β€²|X| and |Yβ€²|β‰₯Ο΅β€²|Y|. Such Xβ€²,Yβ€² also satisfy |Xβ€²|β‰₯Ο΅|X| and |Yβ€²|β‰₯Ο΅|Y|, so Ο΅-regularity gives |d(Xβ€²,Yβ€²)βˆ’d(X,Y)|≀ϡ≀ϡ′.

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 Οƒ(H) be the smallest possible colour class in a proper Ο‡(H)-colouring of H. If |G|β‰₯Οƒ(H), then
r(G,H)β‰₯(Ο‡(H)βˆ’1)(|G|βˆ’1)+Οƒ(H).

Construction: take Ο‡(H)βˆ’1 red cliques of size |G|βˆ’1 and one red clique of size Οƒ(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=Kp 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,Kp)=(mβˆ’1)(pβˆ’1)+1.

Other exact results: r(Pm,Pn)=n+⌊m/2βŒ‹βˆ’1 for nβ‰₯mβ‰₯2 (GerencsΓ©r–GyΓ‘rfΓ‘s); r(K1,m,K1,n)=m+nβˆ’Ο΅, with Ο΅=1 if m,n are both even and 0 otherwise (Harary); r(C4,C4)=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 KN has a red T or a blue Kp.

  1. 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.

  2. 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.

  3. Why does that give Ο‡(R)≀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.

  4. 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 Kp. With Burr's construction, r(T,Kp)=(mβˆ’1)(pβˆ’1)+1.

Check your understanding

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

  1. 13
  2. 16The red cliques have |G|βˆ’1=4 vertices, not |G|.
  3. 9There are Ο‡(K4)βˆ’1=3 red cliques, not 2.
(4βˆ’1)(5βˆ’1)+1=13: three red K4's with blue between them is a colouring of K12 with no red P5 and no blue K4. By ChvΓ‘tal's theorem 13 is exact.

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

  1. Every red component has only mβˆ’1 vertices, and T is connected with m vertices.
  2. Because the red graph is bipartite.The red graph is a union of cliques, far from bipartite.
  3. 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=K1,3 gives (2βˆ’1)(4βˆ’1)+1=4. The true value is r(K1,3,K1,3)=6. What does this show?

  1. K1,3 is not K1,3-good: the bound can be strict.
  2. Burr's bound is wrong for stars.A lower bound below the truth is still correct.
  3. r(K1,3,K1,3) must be 4.The pentagon colouring of K5 (try it in the lab) has no monochromatic K1,3.
Goodness is a special property, not a general rule. For two stars the extremal colourings are regular-looking (each colour 2-regular on K5), not block-structured.

Practice

A star against a triangleChvΓ‘tal, and a direct proof

Show that r(K1,n,K3)=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

K1,n is a tree on n+1 vertices, so ChvΓ‘tal gives nβ‹…2+1. Directly, in K2n+1 with no red K1,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 Kn's with blue between them show 2n is not enough.

Two 4-cyclesA pentagon again

Show that r(C4,C4)β‰₯6.

Solution

Colour a 5-cycle in K5 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 C4. The lab confirms that every colouring of K6 fails.

From Li and Lin, Elementary Methods of Graph Ramsey Theory (Springer, 2022)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 12.2Books are 3-good

Prove that the book Bn=K2+KΒ―n is 3-good for nβ‰₯2: r(K3,Bn)=2n+3.

Hint

Lower bound: 2Kn+1 in blue. Upper bound: in a colouring of K2n+3 with no red triangle and no blue Bn, red neighbourhoods are blue cliques, and a blue edge has at most nβˆ’1 common blue neighbours.

Solution

Lower bound. On 2n+2 vertices take two blue Kn+1's and colour all edges between them red. The red graph is bipartite (no triangle), and each blue component has n+1<n+2=|Bn| vertices.

Upper bound (partial). Colour K2n+3 with no red K3 and no blue Bn. Each red neighbourhood is a blue clique, so red degrees are at most n+1 (a blue Kn+2 contains Bn), and blue degrees are at least n+1. A blue Bn is a blue edge with n common blue neighbours, so inside any blue neighbourhood NB(u) of size m, the induced red graph is triangle-free with minimum degree at least mβˆ’n. Taking a red edge xy there, NR(x) and NR(y) are disjoint inside NB(u), giving m≀2n. So every vertex has red degree at least 2.

These degree constraints alone don't give a contradiction: averaging arguments come out exactly tight up to a term (nβˆ’1)2. The remaining step is a structural case analysis like the one in the book's proof of Theorem 12.3 for fans, and is in Rousseau–Sheehan (1978). I haven't written it out here.

Exercise 12.3Multicolour Ramsey numbers of stars

Prove rk(K1,n1,…,K1,nk)=βˆ‘iniβˆ’k+Ο„, where Ο„=1 if the number of even ni is even and positive, and Ο„=2 otherwise.

Hint

Avoiding a colour-i star K1,ni means colour-i degrees ≀niβˆ’1. With S=βˆ‘(niβˆ’1), at most S+1 vertices are possible, and S+1 needs every colour class to be exactly (niβˆ’1)-regular. Then use 1-factorisations and Hamilton decompositions.

Solution

Let S=βˆ‘i(niβˆ’1). In a good colouring of KN each vertex has colour-i degree ≀niβˆ’1, so Nβˆ’1≀S. If N=S+1, every colour class is (niβˆ’1)-regular, which needs (S+1)(niβˆ’1) even for every i.

Let e be the number of even ni. Then S≑e(mod2).

e even and positive (Ο„=1). S is even, so S+1 is odd, and some niβˆ’1 is odd: no (niβˆ’1)-regular graph on S+1 vertices. So r≀S+1. On S vertices (S even), KS has a 1-factorisation into Sβˆ’1 perfect matchings; give niβˆ’1 of them to colour i, one colour getting one fewer. So r=S+1.

Otherwise (Ο„=2). We need a good colouring of KS+1. If e is odd, S+1 is even and KS+1 has a 1-factorisation into S matchings; give niβˆ’1 to colour i. If e=0, all niβˆ’1 are even and S+1 is odd; KS+1 decomposes into S/2 Hamilton cycles; give (niβˆ’1)/2 to colour i. So r=S+2.

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(B1,B2) is the least N such that every red/blue colouring of KN,N contains a red B1 or a blue B2. Since K2NβŠ‡KN,N, r(B1,B2)≀2br(B1,B2).
Known. br(K2,2)=5. Thomason: br(Km,n)≀2m(nβˆ’1)+1 for nβ‰₯m. Conlon: br(Kn,n)≀(1+o(1))2n+1log2⁑n.
Size Ramsey number. 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 r^(K1,n,K1,n)=2nβˆ’1, and r^(Kn,Kn)=(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 K4 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 xi, column j is yj, and cell (i,j) is the edge xiyj. A monochromatic K2,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 K5,5 contains a monochromatic K2,2. Think of the 5Γ—5 grid above.

  1. 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 (52)β‹…2=20 combinations.

  2. A column has a red and 5βˆ’a blue cells. How many monochromatic row pairs does it have, at least?

    (a2)+(5βˆ’a2), which is 4 when a=2 or 3, and at least 6 otherwise. So the five columns give at least 20 monochromatic row pairs.

  3. 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.

  4. 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(K2,2)≀5; the 4Γ—4 board has a good colouring, so br(K2,2)=5.

Check your understanding

Why is r(B1,B2)≀2br(B1,B2) for bipartite B1,B2?

  1. Split K2N into two halves of size N: the edges between them form a KN,N, and its colouring already contains what we need.
  2. Because K2N has twice as many edges as KN,N.It has about twice as many, but the argument needs a copy of KN,N inside K2N, not an edge count.
  3. Because bipartite graphs have chromatic number 2.True, but the inequality comes from finding KN,N inside K2N.
Any colouring of K2N restricts to a colouring of the KN,N between the halves, and with N=br(B1,B2) that contains a red B1 or a blue B2.

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

  1. No: r^(K3,K3)=(62)=15.
  2. Yes: the Folkman graphs.Folkman graphs avoid K4, but they are large and have many more edges.
  3. Yes: K5 with one extra vertex of degree 3.Colour K5 as two pentagons. Can the new vertex's three edges always be coloured safely?
For complete graphs the size Ramsey number is (r(n,n)2): you cannot save edges by using a sparser host. (For the extra vertex of degree 3: colour K5 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?

  1. No: G has no triangles at all, monochromatic or not.
  2. Yes, by Folkman's theorem.Folkman's graphs avoid K4, not K3.
  3. Yes, if G is large enough.A colouring cannot create a triangle that is not there.
To force a monochromatic K3 the host must contain K3. Folkman's surprise is that it need not contain K4, even though the obvious host K6 does.

Practice

Size Ramsey for starsUpper and lower bounds

Show that r^(K1,n,K1,n)≀2nβˆ’1, and that the star K1,2nβˆ’2 is not enough.

Solution

In any 2-colouring of the 2nβˆ’1 edges of K1,2nβˆ’1, one colour has at least n edges, all at the centre: a monochromatic K1,n. In K1,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 K4,4 with no monochromatic K2,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.

From Li and Lin, Elementary Methods of Graph Ramsey Theory (Springer, 2022)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 13.1Size Ramsey numbers of C4 and P4

Find the size Ramsey numbers r^(C4) and r^(P4) (path with 3 edges), the least number of edges of a graph G with G→(H,H).

Hint

For P4, try the fan K1+P4 (7 edges). For C4, r(C4)=6 gives K6, with 15 edges.

Solution

r^(P4)=7. G=K1+P4 (a vertex joined to a path abcd) has 7 edges and arrows P4. With 6 or fewer edges every graph has a 2-colouring with no monochromatic P4: a disconnected graph arrows P4 only if some component does, so it suffices to check connected graphs on at most 7 vertices. I checked all of them by computer and none works.

r^(C4)≀15. K6β†’(C4,C4) since r(C4,C4)=6, giving 15 edges. I checked by computer that no graph on at most 7 vertices with fewer than 15 edges arrows C4. A complete answer also has to rule out sparser graphs on 8 or more vertices, which I haven't done here.

Exercise 13.5Bipartite Folkman numbers

For bipartite B1,B2, show br(B1,B2)≀f(B1,B2;2)≀2br(B1,B2), where f(β‹…;2) is the least order of a triangle-free graph arrowing (B1,B2).

Hint

Upper bound: KN,N is triangle-free.

Solution

Upper bound. With N=br(B1,B2), KN,N has clique number 2, and by definition every red/blue colouring of it has a red B1 or a blue B2. So f(B1,B2;2)≀2N.

Lower bound (partial). A triangle-free G with Gβ†’(B1,B2) gives K|G|β†’(B1,B2), so |G|β‰₯r(B1,B2). The book's inequality r(B1,B2)≀2br(B1,B2) goes the wrong way to turn this into |G|β‰₯br(B1,B2). I haven't found a short argument for the lower bound, so it is left open here.