Lower bound
Named by 11 essays across 7 fields — each of them below, with the objects they name alongside it.
How many cuts a fair share costs
Every person can be guaranteed a share of a cake worth at least one n-th by their own measure, and the oldest rule that does it asks about n²/2 questions. Splitting the people into halves and the cake at a median mark asks about n log n — and a theorem says nothing can ask fewer. Fairness has a price, and it can be counted.
The few points that cut a flat graph
Any graph that can be drawn without crossings, however large, falls into pieces of at most two thirds once a few points are removed — about the square root of its size, never more than 2.83 times it. A grid shows the square root cannot be beaten, a ring of breadth-first neighbours comes close, and a cycle through a shallow tree finishes the job.
Several colours on every vertex
Give every pair from six points three colours, so that pairs with nothing in common share no colour. Counting says nine colours might do; ten are needed. Stahl conjectured in 1976 exactly how many colours every such problem needs — a formula that meets Lovász's topological answer at one colour a vertex and the obvious answer at k — and a search over stars and triangles confirms it in every case small enough to run.
At least as many lines as points
Sylvester's theorem says some line through two of the points misses all the rest. Remove one end of that line and the line itself disappears, taking at least one line away with one point. Run that backwards and it proves that n points not all in a line determine at least n lines — and the only sets that manage exactly n are a line of n − 1 points with one point off it.
Thirty-one moves from solved
Parity settles which half of a sliding puzzle's arrangements can be reached and is silent about how far away any of them is. Searching every reachable arrangement of the three-by-three tray answers the second question exactly — two arrangements sit thirty-one moves out — and parity turns up again, this time as a law about distance.
The crossings a graph cannot avoid
Five points all joined need one crossing, six need three, seven need nine. Euler's formula gives a lower bound that grows like the square of the number of points and is badly wrong; a sampling trick turns the same formula into a bound that grows like the fourth power and is right to within a constant. And for drawings with straight edges the count turns out to be something else entirely: the number of quadrilaterals the points make.
The fewest moves to draw it
Every construction with ruler and compass is a sequence of moves — draw this line, draw that circle — and it is natural to ask for the shortest. Nobody can answer that by cleverness alone, but a machine can answer it by trying everything: the midpoint of a segment takes four moves and no fewer, the square on it five, a third of it five. Take the ruler away and the compass pays for it: six circles for the midpoint, seven for the square.
How many gates a truth table needs
Every truth function can be built from gates, and the natural measure of a function is the fewest gates that build it. For three letters the whole answer can be computed: no function needs more than four. For n letters, a count shows that almost every function needs about 2ⁿ/n gates, and a construction shows that none needs more. And for any function anyone can actually write down, the best proof in fifty years says it needs 3.1n.
The formula that cannot share
A circuit computes the parity of n letters with a chain of n − 1 exclusive-or gates. A formula in and, or and not, which may use each result only once, needs n² letters at least — a bound Khrapchenko proved by counting the cube's edges between true and false — and exhaustive search over every formula of four letters finds parity sitting exactly on it.
The centre a compass finds in six circles
A circle is drawn and its centre was never marked. A straightedge alone can never find it again. A compass alone can, from two points on the circle, in six circles — and a search through every construction of five circles or fewer shows that six is the least. The reason six works is an inversion that turns the circle into a straight line; the price of discarding the straightedge is exactly one move.
The arcs that make the centre cheap
Finding a circle's centre with the compass alone, from two points on it, costs six circles when the points are placed with no special relation — and as few as two when the arc between them is 60°. Searching every arc in steps of five degrees maps the price exactly, and it is not a smooth function of the arc: it is a list of coincidences, each one a small number of compass steps that happens to land on a chord equal to the radius.
Named alongside it
The objects these essays reach for when they reach for this one.
Exhaustive searchConstructionParityCircleCircuit complexityCompassCompass and straightedgeEuler formulaPlanar graphRecursionAntipodal pairBoolean circuit