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.
Ramsey's theorem
Colour every edge of
The idea
Proof in one line: a vertex
In particular
Explore
Worked example
Prove
What are
and , and what does the recursion give? : a single red edge is a red ; if there is none, all of is blue. With the recursion gives .In a colouring of
, suppose some vertex has at least 4 red edges. Finish the argument.Look at 4 red neighbours of
. A red edge among them makes a red triangle with . If there is none, the 4 neighbours span a blue .Now suppose some vertex has at least 6 blue edges.
Among 6 blue neighbours,
gives a red triangle (done) or a blue triangle, which together with is a blue .If neither case happens, every vertex has at most 3 red and at most 5 blue edges. Why is that impossible in
?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
would be odd. That is impossible, since the degree sum is twice the number of edges. So .
Check your understanding
A colouring of
- A 5-cycle.
- The complete bipartite graph
. 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?
Using
- 18
- 20That is the binomial bound
. Feed in the known value of instead. - 17The parity improvement needs both terms on the right to be even, and 9 is odd.
Someone exhibits a red/blue colouring of
. .One good colouring gives only a lower bound. An upper bound needs a statement about every colouring. .A colouring that avoids the pattern shows is too small, not big enough.
Practice
Three coloursPigeonhole once more
Show that every colouring of the edges of
Hint
A vertex has 16 edges. At least how many share a colour?
Solution
Some colour, say colour 1, appears on at least
The binomial boundInduction
Deduce
Hint
Induct on
Solution
Base:
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
Hint
Label
Solution
Suppose not, so
Exercise 1.6Goodman's count of monochromatic triangles
For a graph
Hint
Colour
Solution
At
Exercise 1.9
Prove
Hint
With
Solution
Partial solution. Let
Counting triples
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:
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
The idea
For
Explore
Worked example
Show that
Split
into two sum-free sets. and . Sums within the first: ; within the second: . None lands back in the same set.Why can
not be split this way?Put 1 in
. Then , so , and , so . Now (since ), so . Finally rules out and rules out .Given a sum-free split of
into classes, colour on vertices by giving edge the class of . Why is there no monochromatic triangle?For a triangle
the three differences are , and . If all three had the same class, that class would contain , and , so it would not be sum-free.What do you get for
and ?So
. With : a good colouring of (it is the pentagon), so . With : , which is weaker than the true value 17, found with instead.
Check your understanding
Why does the Paley construction need
- So that
is a square, which makes " is a square" symmetric in and . - So that
is prime. may be any prime power, such as 9 or 25. The condition is about . - So that the graph has an even number of vertices.
makes odd.
, weaker than what gives. .A single graph only ever gives a lower bound.- Nothing, because 13 is prime and 17 is needed.Any graph with no
and no independent 4-set gives a lower bound. Check what this one gives.
In the explorer, select a triangle in
- An independent set of size 3, because
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.
Practice
Symmetry of Paley graphsAutomorphisms
Show that any two edges of
Hint
Which maps
Solution
If
A triangle-free graph on 13 verticesSum-free connection sets
On
Hint
A triangle
Solution
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.1
Prove
Hint
Lower bound: split
Solution
Lower bound.
Upper bound. Colour
If two of
Exercise 2.3The Schur number
Prove that
Hint
For the construction, try
Solution
Lower bound.
Upper bound. The general argument gives
Exercise 2.6Neighbourhoods in Paley graphs
In the Paley graph
Hint
With the quadratic character
Solution
Expand:
The last character sum: for
Random colourings
Nobody knows how to write down a colouring of
The idea
Colour each edge of
The reason:
The same chapter bounds independence numbers: every graph has
Explore
Worked example
Prove that every graph
Order the vertices uniformly at random. Let
be the set of vertices that come before all of their neighbours. Why is independent?If
were adjacent, would come before and before .What is
?Only the relative order of
and its neighbours matters, and each of these vertices is equally likely to come first. So .Finish the bound.
by linearity, so some ordering gives an independent set at least this large.Deduce: a graph on
vertices with no has at most edges. is convex, so by Jensen for any with average degree . Apply this to the complement : a clique in is an independent set in , so . Hence and . So . Module 7 returns to this.
Check your understanding
For
- Some colouring of
has no monochromatic , so . - Every colouring of
has no monochromatic .An average below 1 guarantees some colouring with , not that all have it. - A random colouring has a monochromatic
with probability exactly .Markov gives . Equality would need always.
Two 4-sets that share an edge are not independent events. Why is
- 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
, not an approximation. - It isn't; the formula is an upper bound.Write
as a sum of indicator variables and take expectations term by term.
For some
. .That needs . Here typical colourings do have monochromatic -sets.- Nothing, because
.Some colouring has at most 6 bad sets. What can you remove?
Practice
The boundChecking the inequality
Show that
Hint
Use
Solution
Half the edges are bipartiteA one-line expectation
Show that every graph with
Hint
Put each vertex on the left or right at random. When does an edge cross?
Solution
Each edge crosses with probability
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
Hint
Removing
Solution
Let
Repeat until no edges remain. The final graph is edgeless on
Exercise 3.7Sparse graphs have large independent sets
If
Hint
CaroβWei plus convexity, or count components.
Solution
By CaroβWei and convexity of
The random graph process
Start with
The idea
- Triangles: threshold
. At the number of triangles is approximately Poisson with mean . - Giant component: at
, if every component has vertices; if there is a unique component with a constant fraction of the vertices. - Connectivity: at
, . The last obstacle is an isolated vertex.
Random graphs are also where Ramsey lower bounds come from: taking
Watch
- 50 isolated vertices. Edges will arrive in a uniformly random order.
- Up to
edges ( ): a scattering of small trees. Cycles are unlikely this early. - Up to
( ): the critical point. Cycles start to appear, and components merge quickly. - Up to
( ): one component swallows most of the others. This is the giant component. - Up to
( ): 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
.
Worked example
Let
Compute
.Each of the
triples is a triangle with probability , so .Suppose
. Why is there a.a.s. no triangle?Markov:
.Suppose
. Then , but that alone is not enough. Bound .Write
. 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 of them, each with . So .Finish with Chebyshev.
Between the two regimes, at
, is approximately Poisson with mean , so .
Check your understanding
About how many triangles do you expect in
- About
. - About
.Compute with : the powers of cancel. - About 1.You are close. Remember
.
At
- About 1.
- About 0.Compute
. - About
.The exponential cancels the factor exactly.
If
- No.
could be huge on a rare event and 0 otherwise, so a second-moment bound is needed. - Yes, by Markov's inequality.Markov bounds
from above. It says nothing about being positive. - Yes, because
is a sum of many indicators.Indicators can be strongly correlated, for example all equal to one event of small probability.
Practice
When does appear?Same method, new numbers
Find the threshold for
Hint
Solution
No isolated verticesFirst moment
Show that at
Solution
The expected number of isolated vertices is
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
Hint
Expected number of cycles, then Markov.
Solution
The number of possible
Exercise 4.12The threshold for containing
Let
Hint
Below the threshold, the densest subgraph
Solution
Below:
Above:
Each term is
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
then
For
each up to a factor
Explore
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
Set up the random experiment and the bad events.
Colour each vertex red or blue independently with probability
. For each edge , let be the event that is monochromatic.What is
?All red or all blue:
.Find a dependency graph with maximum degree
. is determined by the colours on . The events with are determined by colours off , so is mutually independent of all of them together. Joining to the edges it meets gives degree at most .Conclude, and compare with the union bound for
.The local lemma applies, so with positive probability no edge is monochromatic. For
the condition is , that is , with no limit at all on the total number of edges. The union bound would need fewer than edges in total.
Check your understanding
Why is the event "
- Such a
shares no edge with , so those events depend only on edges outside . - Because such a
shares no vertex with . may share one vertex. What do the events actually depend on? - Because each event has small probability.Small probability says nothing about independence.
Asymptotically, Spencer's local lemma bound for
- 2
That is the gain over the deletion method, not over the union bound. Divide the two constants: .
If the events are fully independent (
- No. Independent events, each with probability below 1, can all be avoided, since
. - Yes, the local lemma is exact when
.Try with two independent events. - No, they need
.That is the union bound, which is only a sufficient condition.
Practice
Regular uniform hypergraphsCount the dependencies
Show that every
Hint
Each edge has
Solution
An edge meets at most
Satisfiable formulasThe same lemma, in logic
A
Solution
Set each variable true or false at random. A clause fails with probability
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
Hint
Colour
Solution
Cliques. First moment: if
Local Lemma: two
a factor
Bicliques. A fixed
Exercise 5.5Two-colouring hypergraphs with few intersections
Let
Hint
Colour randomly and split "edge
Solution
Colour each vertex red or blue independently.
Lopsidependency. Let
Local Lemma. With all
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
A clique is a family of triples meeting pairwise in exactly one point: at most
That is only polynomial in
Explore
Worked example
Prove the Oddtown theorem.
Turn each set into a vector. Over which field?
Over
: let be the indicator vector of . Then .What are
and for ? since sizes are odd, and since intersections are even.Show the vectors are linearly independent.
If
, take the dot product with : every term vanishes except . So every .Conclude.
Linearly independent vectors in
number at most , so . For triples, an independent set of is such a family, so .
Check your understanding
Which family is a clique in
- The seven lines of the Fano plane, such as
- All triples containing the element 1.
and share two elements, so they are not adjacent. - The four triples inside
.These meet pairwise in two elements. That makes them independent, not a clique.
Oddtown needs odd set sizes. What goes wrong with even sizes and even intersections?
becomes 0 and the independence argument fails; indeed there can be such sets.- Nothing; the same bound
holds.Try all unions of the pairs - The vectors no longer live in
.They still do. Look at which dot product changes.
- ErdΕs's bound wins for every
: it is exponential, is cubic. stays ahead, because explicit graphs are better than random ones.Compare growth rates: against .- They stay within a constant factor of each other.The ratio
tends to infinity.
Practice
The clique boundA positive definite Gram matrix
Show directly that a family of triples in
Hint
Use real indicator vectors this time. What is their Gram matrix?
Solution
With real vectors,
TetrahedraAn independent set of size t
When
Solution
Split
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
Hint
With
Solution
Each
Exercise 6.4Mod- town and mod- town
Generalise the Oddtown theorem to "mod
Hint
For mod
Solution
Mod
Mod
TurΓ‘n numbers
How many edges can a graph on
The idea
For bipartite
Why Ramsey cares. In a
Explore
Worked example
Show that a graph on
Count "cherries": pairs of edges
at a common vertex . How many are there in terms of degrees? : choose the centre , then two of its neighbours.Why is this at most
when there is no ?Each cherry has a pair of endpoints
. If two cherries had the same endpoints and different centres , then would be a 4-cycle. So each pair is used at most once.Use convexity to bring in the average degree
. is convex, so , that is .Solve for
. , so . The polarity graph shows the constant cannot be improved.
Check your understanding
To first order, what is
That holds for bipartite graphs. Is bipartite? , so the formula gives , not .
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.
A graph on
- About
. - About
. has average degree but is full of 4-cycles. - Bounded by a constant.The polarity graph has degrees about
and no .
Practice
Mantel's theoremTurΓ‘n for triangles, by CauchyβSchwarz
Show that a triangle-free graph on
Hint
For an edge
Solution
Disjoint neighbourhoods give
Many colours, one 4-cycleTurΓ‘n meets Ramsey
Use the worked example to show that every
Hint
Some colour class has at least
Solution
It suffices that
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
Hint
A star-free graph has bounded maximum degree. For paths, disjoint copies of
Solution
Stars.
Paths. The ErdΕsβGallai theorem gives
Exercise 7.5Odd cycles have bipartite extremal graphs
Prove that
Hint
The lower bound is
Solution
Lower bound. The balanced complete bipartite graph has no odd cycles and
Upper bound (outline). Let
- By deleting low-degree vertices one at a time (each deletion of a vertex of degree
keeps the edge count above relative to the new order) one may assume minimum degree . - The ErdΕsβSimonovits stability theorem (since
) says can be made bipartite by deleting edges. Take a max-cut . - If some edge
lies inside , the high minimum degree gives and many neighbours in , and between and of those there are paths of every even length up to , closing an odd cycle of length . So is bipartite, and .
Each step needs
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
The idea
For
Explore
Worked example
Show that
Show that the five words
form a code.Take two of them, with first letters differing by
. If the first letters are confusable, but the second letters differ by , which is not confusable. If 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
or . 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
, so there are at most 2.Add up over the five windows
.Each codeword's first letter lies in exactly two windows. So
, giving .What does this give for
? , better than . LovΓ‘sz's theta function gives the matching upper bound, so : 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?
That is per word. Each word costs two channel uses.- 1That is the single-letter rate
. The two-letter code does better.
Why is
- Concatenate
codewords of length : two such long words differ in some block, and that block tells them apart. - Because
is multiplicative under .It is only super-multiplicative: . - Because
has more vertices.More vertices alone does not give large independent sets. Build the code explicitly.
- 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
or . So at most codewords. - Because
.The pentagon gives 5, so the product formula fails. - Because
has at most 25 vertices. and can be as large as you like.
Practice
The square channelClique covers
Show that
Hint
Solution
Long words for the pentagonConcatenation
Show that
Solution
Concatenate
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
Determine
Hint
Solution
For odd powers,
Exercise 8.4Shannon capacity of even cycles
Prove
Hint
An independent set of size
Solution
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
Then
Why. Choose
- A vertex
is in when all picks land in : probability . By convexity . - An
-set with fewer than common neighbours ("bad") lies in only if all picks land in its common neighbourhood: probability below . So the expected number of bad sets inside is below . - Some choice has
. Delete one vertex from each bad set in .
Explore
Worked example
Let
What set
would make embedding easy?A set of 4 vertices in which every pair has at least 10 common neighbours. Put the branch vertices on
. Then give each of the 6 subdivision vertices a common neighbour of its two branch vertices, avoiding the at most vertices already used. With 10 common neighbours there is always one left.Apply the lemma with
, , . What is the second term? .How large must
be?We need
, i.e. , i.e. .Translate into edges.
, so suffices. Hence , matching the shape with .
Check your understanding
In a graph on 40 vertices, a pair
That is for one pick. All three picks must land among the 3 common neighbours. The picks must be adjacent to both and , so they must land in the intersection of the two neighbourhoods.
Why is
, and is convex, so the sum is at least times the value at the average.- Because every vertex has degree
. is only the average degree. The argument must handle uneven degrees. - Because
always contains . is usually not inside its own common neighbourhood.
Suppose
- It tends to 0, because it equals
and . - It grows, because
is huge. is fixed while grows. Which factor depends on ? - It stays constant.Write the ratio out and see where
appears.
Practice
Subdivided Same recipe, new numbers
Repeat the worked example for
Hint
Now
Solution
When placing a subdivision vertex, at most
The size of Indicators
Prove
Solution
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
Hint
Solution
Every subgraph of a forest is a forest, which has a vertex of degree
Exercise 9.7Embedding degenerate bipartite graphs greedily
Let
Hint
Order
Solution
Since
Embed
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
- Cycle count.
and the number of closed 4-walks, , is at most . - Discrepancy. For every vertex set
, . - Eigenvalues.
and every other eigenvalue has .
The striking part is the first: one number, the 4-cycle count, controls the edge count of every subset.
The Paley graph
Explore
Worked example
For a prime
is a circulant graph: depends only on . What are the eigenvectors?For
and each , the vector is an eigenvector with eigenvalue , where is the set of nonzero squares. For this is .Relate
( ) to the Gauss sum .As
runs over , takes the value 0 once and each nonzero square twice. So .Use the classical fact
for ( is real). What are the eigenvalues? , so for every . Half of them take each sign.Apply Hoffman's bound
for -regular graphs.With
and : . For this gives ; the truth is 3. The spectrum alone gets close.
Check your understanding
Two disjoint cliques of size
- No. If
is one of the cliques, , twice what density 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.
"Shuffle the labels" changes the picture of the matrix but not the numbers. Why?
- Relabelling replaces
by for a permutation matrix , which has the same eigenvalues and the same . - 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.
A 500-regular graph on 1000 vertices has
- Between 2000 and 8000.
- Between 4970 and 5030.The error term is
, not . - Exactly 5000.5000 is the centre,
. The lemma allows an error.
Practice
Every graph has many 4-cyclesThe easy half of the cycle count
Let
Hint
Solution
By the Rayleigh quotient with
Random tests miss structureWhy "every set" matters
In two disjoint cliques of size
Solution
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
Hint
Try
Solution
For
The useful version restricts the condition (for example to the sum over
Exercise 10.5Eigenvalues of Cayley graphs
Let
Hint
The neighbours of
Solution
For abelian
Van der Waerden and regularity
Colour
The idea
Known exactly:
Explore
Worked example
Prove
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
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
exists. The colouring RRBBRRBB of shows , so .
Check your understanding
Extend the good colouring RRBBRRBB of
- 1, 5, 9
- 3, 6, 93 is blue and 6 is red.
- 2, 5, 88 is blue.
- No: those two halves have density 1, far from
. - Yes: regularity only asks about the overall density.It asks about every pair of subsets of at least
times the size. - Yes: halves are too small to count.The threshold is
vertices, and 50 is well above it.
- About
, as for random edges. - Possibly none.That can happen for dense pairs that are not regular. Regularity is what rules it out.
- About
.A triangle needs all three edges, so the densities multiply.
Practice
Counting 4-term progressionsWhy good colourings are rare
How many 4-term progressions does
Hint
For common difference
Solution
For
Progressions inside progressionsScaling
Show that if
Solution
Colour
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.1
Show the van der Waerden number
Hint
Colour
Solution
[8]. RRBBRRBB: the red set
[9]. Suppose there's no monochromatic progression; say
both red: . both blue: then is red (else ) and is red (else ), and is red. red, blue (the other mixed case is the mirror image ): blue ( ); red ( ); blue ( ); red ( ); blue ( ); red ( ); and is red.
Every case fails, so
Exercise 11.8Regularity is monotone in
If
Hint
Write out the definition and compare the two conditions.
Solution
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
Construction: take
Other exact results:
Explore
Worked example
Prove ChvΓ‘tal's upper bound: if
Show that a graph with minimum degree at least
contains every tree on vertices.Embed
one vertex at a time, always adding a leaf next to an already embedded vertex . Fewer than other vertices have been used, and has at least neighbours, so one is free.Suppose the red graph
has no copy of . What can you say about every subgraph of ?Every subgraph has a vertex of degree at most
, by step 1. So is -degenerate: repeatedly removing a vertex of degree at most empties it.Why does that give
?Colour the vertices greedily in the reverse of the removal order. Each vertex has at most
neighbours coloured before it, so one of colours is free.Finish.
Some colour class of
has at least vertices, so at least . It is independent in , so all edges inside it are blue: a blue . With Burr's construction, .
Check your understanding
What lower bound does Burr's construction give for
- 13
- 16The red cliques have
vertices, not . - 9There are
red cliques, not 2.
In the construction for a tree
- Every red component has only
vertices, and is connected with 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.
Burr's bound with
is not -good: the bound can be strict.- Burr's bound is wrong for stars.A lower bound below the truth is still correct.
must be 4.The pentagon colouring of (try it in the lab) has no monochromatic .
Practice
A star against a triangleChvΓ‘tal, and a direct proof
Show that
Hint
Directly: if no vertex has
Solution
Two 4-cyclesA pentagon again
Show that
Solution
Colour a 5-cycle in
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
Hint
Lower bound:
Solution
Lower bound. On
Upper bound (partial). Colour
These degree constraints alone don't give a contradiction: averaging arguments come out exactly tight up to a term
Exercise 12.3Multicolour Ramsey numbers of stars
Prove
Hint
Avoiding a colour-
Solution
Let
Let
Otherwise (
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
Explore
Worked example
Prove that every red/blue colouring of
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
has a red row pair if cells and 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 combinations.A column has
red and blue cells. How many monochromatic row pairs does it have, at least? , which is 4 when or , 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
columns have 3 red cells and have 2, the red row pairs number . This must equal 10, so , which is impossible. Hence ; the 4Γ4 board has a good colouring, so .
Check your understanding
Why is
- Split
into two halves of size : the edges between them form a , and its colouring already contains what we need. - Because
has twice as many edges as .It has about twice as many, but the argument needs a copy of inside , not an edge count. - Because bipartite graphs have chromatic number 2.True, but the inequality comes from finding
inside .
- No:
. - Yes: the Folkman graphs.Folkman graphs avoid
, but they are large and have many more edges. - Yes:
with one extra vertex of degree 3.Colour as two pentagons. Can the new vertex's three edges always be coloured safely?
Can a triangle-free graph
- No:
has no triangles at all, monochromatic or not. - Yes, by Folkman's theorem.Folkman's graphs avoid
, not . - Yes, if
is large enough.A colouring cannot create a triangle that is not there.
Practice
Size Ramsey for starsUpper and lower bounds
Show that
Solution
In any 2-colouring of the
The 4Γ4 boardA good colouring
Find a colouring of
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 and
Find the size Ramsey numbers
Hint
For
Solution
Exercise 13.5Bipartite Folkman numbers
For bipartite
Hint
Upper bound:
Solution
Upper bound. With
Lower bound (partial). A triangle-free