Counting the same thing twice — page 10
Analysis
An area measured by walking round it
A surveyor's instrument from 1854 measures the area of any shape on a map by having its pointer steered once round the boundary; a small wheel rolls and slides, and its reading, times the length of one arm, is the area. Nothing touches the inside. The reason is that area can be written as an integral over the boundary — Green's theorem — and the instrument is that integral built in brass. Walk a curve that crosses itself and the same integral counts some regions twice.
Applied
How few voters any majority needs
Any pattern of head-to-head majorities whatever — cycles within cycles, a candidate who beats the winner of every other contest and loses to its loser — can be produced by voters who each rank the candidates sensibly. McGarvey's recipe needs n(n − 1) of them for n candidates. The truth is far fewer: every pattern on five candidates takes three voters at most, a counting argument shows the number must eventually grow, and it grows only like n divided by its logarithm.
Discrete
The fewest triangles an edge density allows
Half of all possible edges can be drawn without a single triangle. One more, and triangles appear — not one but several at once. Push the density further and the question becomes a curve: for every share of edges, the fewest triangles a large graph can hold. The answer is a string of scallops, touching a simple parabola at the densities of the balanced multipartite graphs and bulging above it between them. It was guessed in the 1980s and proved in 2008 by a method that turns counting into positive-definite matrices.
Discrete
As many points as two steps allow
In a graph where every point has d neighbours and every point is within two steps of every other, there can be at most d² + 1 points — one, its d neighbours, and d(d − 1) more reached through them. Graphs that meet the bound exactly are rare to the point of absurdity. The pentagon does it for d = 2, the Petersen graph for d = 3, a fifty-point graph found in 1960 for d = 7, and an eigenvalue argument proves there is nothing else — except possibly one graph with 3,250 points and 57 neighbours each, which nobody has found or ruled out.
Geometry
Six numbers that need five pentagons
In 1638 Fermat wrote that every whole number is a sum of three triangular numbers, four squares, five pentagonal numbers, six hexagonal numbers, and so on for every polygon — and that he had a proof he would not write down. The claim is true; Cauchy proved it in 1813. What the claim hides is how unequal the cases are. Triangles and squares need their full count infinitely often. For pentagons, only six numbers ever need all five — 9, 21, 31, 43, 55 and 89 — and from hexagons on, two apiece.
Probability
Drawn without putting back
Every concentration bound on this shelf assumes the draws are independent. A real sample is not: a pollster does not ring the same person twice, and every ball taken from an urn changes what is left in it. The dependence runs the helpful way. Wassily Hoeffding proved in 1963 that a sample drawn without replacement is at least as concentrated as one drawn with it, for every convex measure of spread at once — and the variance falls by an exact factor that reaches zero when the whole urn is taken.