The collection

Every essay — page 13

Page 13 of 44, continuing through the fields in the same order.

Geometry Analysis Algebra Discrete Topology Probability Number Dynamics Logic Computation Applied What's new Series Concepts Search

Discrete

Counting, graphs, and things that come in whole pieces.

Arithmetic on a dial of 12. A dial with 12 positions. Starting at 8 and stepping forward 9 places lands on 5, because the walk passes the top 1 time on the way.

Numbers that wrap

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

A closed walk on the 3-cube changing one place at a time. The corners of a 3-dimensional cube with a path through every one of them exactly once, each step moving along an edge, and the last corner one step from the first.

A walk that changes one thing at a time

A lattice polygon of area 22.5. A polygon with all its corners on the integer grid, with the 20 grid points strictly inside and the 7 on its boundary marked; its area is the first count plus half the second, less one.

Area by counting dots

Two graphs that will not lie flat

All 16 trees on 4 labelled points. Every tree on 4 labelled points, drawn one by one. There are 16 of them, which is 4 to the power 2.

Sixteen trees on four points

One swap frees a colour. A vertex of degree five whose neighbours carry five different colours, before and after a Kempe chain is recoloured. The swap frees one colour for the middle vertex.

Five colours, and a chain that can be followed

Counting the colourings, by deleting and contracting. A graph beside the two smaller graphs its edge deletion and contraction produce, with the number of proper colourings of each at every number of colours up to 5.

Counting the colourings

Seven regions on a doughnut, each touching all six others. A brick pattern of seven labelled regions on a torus, drawn as a rectangle whose opposite edges are identified. Every pair of regions shares a border, so no two may take the same colour.

Seven regions on a doughnut

A three-coloured triangulation, and the walk that finds a rainbow triangle. A triangle cut into 36 smaller ones, its corners coloured under Sperner's rule. The 9 small triangles carrying all three colours are shaded, and a path enters through a door on one edge and ends inside one of them.

Three colours force a triangle

A matching that covers all 5 of one side. A bipartite graph with every possible pairing drawn thin and one complete matching drawn thick, so that each vertex on the left is joined to a distinct vertex on the right.

One bottleneck and nothing else

A product of 3 polynomials, and what its coefficients count. The coefficients of a product of small polynomials, with the combinations of choices that reach one marked total written out beneath it.

A polynomial that counts

The most triangle-free edges on 6 points. A graph on 6 points carrying 9 edges and no triangle, found by examining every graph on those points, with the two sides its edges cross between drawn apart.

The edge that forces a triangle

A largest flow of 5 through two wide ends and a narrow middle. A network with a capacity on every road, the amount a largest flow sends along each, and the cut whose capacity equals that flow's value drawn as a line separating the places.

The bottleneck is the whole story

The widest layer of the subsets of a set of 4. A Hasse diagram of a small order with the widest layer marked, and the largest set of mutually incomparable elements found by examining every subset.

The widest layer and the longest chain

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

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

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

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

6 figures $Everybody's share of the 24 chains. The subsets of a set of 4, each labelled with the fraction of maximal chains it lies on; the shares of any antichain add to at most one, and to exactly one only for a whole layer.$

Everybody's share of the chains

The cube cut into 6 symmetric chains. The subsets of a set of 4 partitioned into 6 chains by the bracket rule, each chain running from size k to size 4 − k and passing once through the middle layer.

The cube cut into chains

At most 3 of the 7 arcs can pairwise meet. The 7 elements arranged round a circle with the 7 arcs of 3 consecutive drawn, and the largest collection of arcs that pairwise intersect picked out.

The largest family that always meets

7 figures $16 ways to sort it. A small order with its 16 linear extensions counted, and for each incomparable pair the fraction of extensions putting one before the other.$

How many ways to sort it

A bad path, and the path it reflects to. Two grids, 6 by 5. On the left a monotone path that dips below the diagonal, with its first offending step marked; on the right the same path with everything after that step reflected, which ends one square right and one square below the corner.

Counting the paths that go wrong