Matpic
mathematics, in pictures
Concept

Ramsey number

The smallest number of points at which every two-colouring of the pairs contains a given number all agreeing. Only a handful are known exactly; the upper bounds come from counting arguments and the lower ones from constructions or from proofs that constructions exist.

Named by 7 essays across 3 fields — each of them below, with the objects they name alongside it.

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.

discrete · Ramsey theory 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.

discrete · Ramsey theory 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.

discrete · Ramsey theory 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.

discrete · Ramsey theory 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.

discrete · Ramsey theory A rectangle of the parity table, nearly balanced. A 32 by 32 grid of +1 and −1 entries — the parity of the inner product of row and column — with a 15 by 14 rectangle of chosen rows and columns highlighted; its entries sum to 8.

Two weak sources make one fair bit

No fixed rule can turn every weakly random source into fair bits: for any rule, some source with almost full unpredictability makes it constant. Two independent sources are different. Multiply their bits in pairs, add, and keep the parity — and if the two together carry more unpredictability than the length of one, the result is nearly fair, whatever else the sources do. The reason is that the table of those parities is balanced on every large rectangle.

computation · Pseudorandomness Which Paley graphs answer every small request. size 2: first passes at 13; size 3: first passes at 29; size 4: first passes at 89; primes checked up to 113.

The squares that answer every request

Rado's graph has, for any finite sets U and V, a vertex joined to all of U and none of V. A finite graph can only answer the small requests, and the Paley graphs — residues modulo a prime, joined when their difference is a square — are the classic way to build one. Checking every request exactly finds the thresholds: 13 residues answer every request of two, 29 every request of three, 89 every request of four. The theorem that guarantees it asks for 64, 576 and 4,096. Coin-toss graphs of the same sizes almost never manage it.

logic · Models

Named alongside it

The objects these essays reach for when they reach for this one.

Counting argumentExistence proofComplete graphPigeonhole principleGraphIndependenceModular arithmeticNonconstructivePaley graphParityProbabilistic methodQuadratic residue

All concepts