Generator

Two colours avoid a progression up to 8, and no further

A generator in the discrete library, called 23 times across 4 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

progression is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

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.

12 points, a cup of 5 and a cap of 5

The most points with no k-cup and no l-cap: Pascal's triangle

6 points with no 4-cup and no 4-cap, and the two blocks they are made of

Eight points with no convex pentagon among them

Points that force a convex k-gon: the bound, the construction, and the four known values

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

and has no 3-cup and no 3-cap ×15
the construction for (3, 3) has C(k + l − 4, k − 2) points ×15
nothing survives at 9 either ×7
between 5 and 30 points ×2
its longest cup has 3 points and its longest cap 3 ×2
a point set in general position was found for every seed ×1
although many fours are ×1
and all three sizes of hull turned up in the test ×1
and climbs toward it ×1
and equals the construction's count where known ×1
and four of them in convex position ×1
and its longest fall is n ×1
and neither colour can be given to the next number without making one ×1
and the extra term's label leaves the n by n square it would have to fit in ×1
and the first column is the longest decreasing one ×1
and the surviving lengths run right up to it with no gap ×1
between 8 and 26 cards ×1
between one and four seeded point sets are drawn ×1
each entry is the sum of the one above and the one to the left ×1
eight times the cards, about half the gap ×1
every five points in general position hold four in convex position ×1
every known value lies between the construction and the bound ×1
every term carries a different pair of counters ×1
its longest climb is n ×1
k and l between 4 and 6 ×1
k and l run to between 4 and 7 ×1
no five of the eight are in convex position ×1
one more term and a climb or a fall of n+1 appears ×1
one point more, anywhere, makes a k-cup or an l-cap ×1
the cap turns downward at every point ×1
the claim is tested on between 200 and 20,000 point sets ×1
the colouring drawn contains no such pattern ×1
the cup turns upward at every point ×1
the exhaustive search runs to between 5 and 14 numbers ×1
the extremal sequence has n² terms ×1
the first row of the shape is the longest increasing subsequence ×1
the longest chain found by search matches the number of patience piles ×1
the lower-left block has no (k − 1)-cup ×1
the number of piles is the longest increasing run in the deal ×1
the panels drawn show different hull sizes ×1
the pattern is a progression or a sum ×1
the ratio stays below 2 ×1
the rescaled lengths centre near −1.77 with spread near 0.9 ×1
the scaled shape lies close to the limit curve ×1
the search reaches a length at which no colouring survives ×1
the search runs to between 5 and 14 numbers ×1
the sequence is built from between 2 and 5 blocks ×1
the set has C(k + l − 4, k − 2) points ×1
the set is small enough to escape a longer cup and a longer cap together ×1
the shape has n boxes ×1
the upper-right block has no (l − 1)-cap ×1
the view is one the family draws ×1

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Discrete

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.

Discrete

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.

Discrete

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

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.

The whole library · What the figures prove