Matpic
mathematics, in pictures
Series

Ramsey theory — the series

5 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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
  2. 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
  3. 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
  4. 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
  5. 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

All series