Matpic
mathematics, in pictures
Concept

Lower bound

A proof that no method can do better than some amount, as opposed to a method that achieves it. Lower bounds are usually harder than upper bounds because they must defeat every possible strategy, including ones nobody has thought of.

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

Even and Paz's halving, for 4 people. The recursive halving procedure run on a cake valued differently by 4 people: each round's marks and cuts, and the final pieces, each worth at least a 1/4 share to its owner. 8 marks are made.

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.

applied · Fair division Breadth-first levels in a planar triangulation. A Delaunay triangulation of 160 random points with each point coloured by whether it is inside, on or outside the level 4 steps from the centre; that level of 23 points separates 31 from 106.

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.

discrete · Planarity

Named alongside it

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

RecursionComplexityDivide and chooseEuler formulaFair divisionGraphMoving knifePlanar graphPlanarityProportionalitySquare rootValuation measure

All concepts