Ramsey theory — the series

Six people, and the trio that cannot be avoided. The fifteen pairs among six people, coloured at random. Whatever the colouring, three people are all mutual acquaintances or all mutual strangers — here 1, 2, 5.

Six people at a party

Among any six people, three are mutual acquaintances or three are mutual strangers. Five is not enough, and the arrangement that saves five is a pentagon. Beyond that the numbers become unknowable.

part 1 · discrete

17 points coloured by whether their difference is a square. 17 points on a circle with every pair joined, coloured by whether the difference of their labels is a square modulo 17; the largest set of points all joined by one colour has 3 members.

Eighteen people, and the seventeen that escape

Among any eighteen people, four are mutual acquaintances or four are mutual strangers. Seventeen can be arranged so that neither happens, and the arrangement is not a lucky find — it is a rule about squares.

part 2 · discrete

The expected number of monochromatic sets, and where it drops below one. The logarithm of the expected number of single-coloured 4, 5, 6-point sets in a random two-colouring, plotted against the number of points, with the crossing of one marked for each.

The colouring nobody has ever seen

Count the monochromatic sets a random colouring is expected to contain. If the average is below one, some colouring has none — and the argument is finished, having produced nothing anyone can look at.

part 3 · discrete

Two colours avoid a progression up to 8, and no further. The numbers 1 to 8 in the two colours that avoid three equally spaced numbers in one colour, with the number 9 beside them in both colours and the pattern each choice forces.

Three in a row on the number line

Colour the numbers one to eight in two colours and it can be arranged that no three equally spaced numbers agree. Add the ninth and it cannot. The structure being forced is arithmetic rather than graphical, and the proof is a different proof.

part 4 · discrete

A sequence of 3² with no climb and no fall longer than 3. 10 terms plotted in order, each labelled with the longest climb and the longest fall ending at it; the first 9 keep both counters at 3 or below and the last one cannot.

The sequence that cannot avoid a staircase

Any ten numbers in a row contain four that climb or four that fall. The proof gives every term a pair of counters, notices that no two terms can share a pair, and is finished — with a bound that is exactly right.

part 5 · discrete

12 points, a cup of 5 and a cap of 5. 12 points in general position with the longest convex-upward chain (5 points) and the longest convex-downward chain (5 points) marked.

Every crowd holds a bowl or a dome

Among enough points in the plane, some k of them always bend upward like a bowl or some l bend downward like a dome. The number that forces it is a binomial coefficient, it is exactly right, and it proves that every large enough crowd contains a convex polygon — with a bound nobody could lower to the true answer for eighty years.

part 6 · discrete

400 random points and their longest rising chain, 34 long. 400 uniform random points in a unit square with the longest chain increasing in both coordinates marked: 34 points, against 2√n = 40.0.

The longest climb of a shuffle

Erdős and Szekeres guarantee that any n distinct numbers hold a climb or a fall of √n, and there are orders that allow nothing more. Shuffle a deck at random instead and the longest climb is almost exactly 2√n — with fluctuations of size n to the power one-sixth, distributed exactly as the largest eigenvalue of a large random matrix.

part 7 · discrete

The longest rising chain in a random cloud, by dimension. Mean longest chain divided by n^(1/d) for d = 2, 3, 4, 5 and n = 250, 500, 1000, 2000, 4000, 8000: d=2: 1.768, 1.804, 1.836, 1.863, 1.895, 1.919; d=3: 1.846, 1.928, 1.981, 2.022, 2.091, 2.125; d=4: 1.773, 1.884, 1.934, 2.026, 2.062, 2.141; d=5: 1.694, 1.762, 1.812, 1.913, 2.037, 2.030.

The longest climb in a cube

Among n random points in a square, the longest chain rising to the right has about 2√n points, a fact with a famous proof. Put the points in a cube and ask for a chain rising in all three directions, and its length is about c·n^(1/3) for a constant nobody knows. Béla Bollobás and Peter Winkler proved that the constants for every dimension stay below e and creep up to it. The upper bound is a single count of chains, and simulation shows how far below it the real chains fall.

part 8 · discrete