Convexity
Named by 52 essays across 8 fields — each of them below, with the objects they name alongside it.
Why the list of perfect solids stops at five
There are infinitely many regular polygons and exactly five regular solids. The reason is not deep, but it is very sharp, and it can be checked on a single row of corners.
Round is not the only way to be the same width
A shape that measures the same in every direction sounds like a description of a circle. It is not — there are infinitely many others, one of them is on a coin in most people's pockets, and a drill built from one cuts a nearly square hole.
One sequence, counting everything
The number of ways to cut a polygon into triangles is 1, 2, 5, 14, 42. So is the number of ways to bracket a product, the number of binary trees, and the number of paths that never cross a diagonal. They are the same count, and the reason is one picture.
The plane, divided by whoever is nearest
Scatter some points and colour every other point of the plane by which one is closest. The result is a tiling nobody designed, and its dual triangulation has a property that no part of the construction mentions.
Four circles cannot do it
Three overlapping circles cut the plane into exactly the eight regions three sets need. Four circles cut it into fourteen, and sixteen are required — so the diagram everyone draws stops working at four, and the reason is a count.
Two numbers that have to meet
Every linear program has a shadow — a second program built from the same numbers read the other way, whose minimum can never fall below the first's maximum. That much is a one-line calculation; the theorem is that the two numbers are always exactly equal.
What a constraint is worth
A linear program and its dual reach the same number. What the dual's variables are is a separate question, and the answer converts a solution into a rate for every constraint — piecewise constant, zero on the constraints that are not doing any work.
The value from both sides
Two choosers move at the same instant, and each asks the cautious question — how much can be guaranteed, whatever the other does. With pure choices the two answers are usually different numbers; allow a probability and they are forced to be the same one.
The road that makes everyone later
An equilibrium is a state nobody can improve alone, which is a much weaker thing than a state anybody would choose. Adding a link that costs nothing to use makes every traveller in this network strictly slower, and the arithmetic says by exactly how much.
The most area a fence can hold
One length of boundary, and the question of what shape to bend it into. The answer is a circle, everybody knows it, and the argument that convinced the nineteenth century turned out to prove something slightly different.
Circles that are diamonds and squares
The theorem hands over a formula for distance. Take the formula as a definition, change the exponent in it, and the set of points one unit from the origin stops being round — while remaining, in every sense that matters, a circle.
A lottery over whole assignments
A table of shares in which every person's shares add to one task and every task is exactly covered is never anything more than a mixture of whole assignments — and finding the mixture is a matter of taking one complete assignment out at a time.
The curve of the average, and the average of the curve
A curve that bends upwards keeps every one of its chords above it. That single fact, applied to a weighted average instead of a midpoint, turns into an inequality that produces the arithmetic–geometric mean inequality, Cauchy–Schwarz and the entropy bound as special cases.
One point in every big enough shape
A determinant measures a lattice, not the basis that happened to describe it — and that measurement is an exchange rate. Any symmetric convex region with more than four times that area has to swallow a lattice point.
One dimension up, and the circles disappear
The Delaunay triangulation is defined by a condition about circles, which is awkward to compute and awkward to reason about. Lift every point onto a paraboloid and the circles turn into planes, the condition turns into convexity, and a two-dimensional problem is solved by looking at a three-dimensional shape from underneath.
Every site in the middle of its own cell
Move each point to the centre of mass of its own Voronoi cell, then redraw the diagram, then do it again. The rule is two lines long, it never mentions hexagons, and what it settles into is a honeycomb.
When the sites are not the same size
Give every site a weight and the boundaries slide. The cells stay convex and the edges stay straight, which is surprising, and one thing happens that the unweighted diagram never allows — a site can end up owning nothing at all.
The shape described from outside
A convex shape can be given by its boundary or by the family of lines that touch it, and the second description turns the constant-width condition into one line of arithmetic — after which the perimeter falls out, and curves with no corners at all can simply be written down.
The corners are whole assignments
A table of shares can be written as a lottery over whole assignments, which one worked example shows. The general statement is that the corners of the set of such tables are exactly the whole assignments, and that single fact is why the whole subject is easy.
One table, two lotteries
A table of shares says what fraction of each task each person does. It does not say how — the same table is a mixture of whole assignments in many different ways, and the differences are exactly what the people being assigned would care about.
A line under every point
The chord above the curve is one definition of convexity. There is a second — a line under the curve at every point, staying under everywhere — and it is the one that turns a statement about a derivative at a point into a statement about the whole function.
The function seen from its tangents
A convex function is the upper envelope of its own tangent lines, so it can be described by giving, for each slope, how far the line of that slope has to be pushed down. That description is a second function, and applying the construction twice returns the original.
Where the guarantee stops
Convexity converts every downhill method into a correct one, and its absence removes the guarantee entirely rather than degrading it. What is left is a collection of partial answers, and knowing which of them apply to a given problem is most of what non-convex optimisation is.
Three points, however many there are
A point inside the hull of a thousand points is inside the hull of three of them. Any four points split into two groups whose hulls meet. And a family of convex sets, every three of which have a common point, has one common to all — three, in each case, being one more than the dimension.
A wall between two bodies
Two convex sets that do not meet can be told apart by a single straight line, and the line is a certificate — one object, checkable in a moment, proving something about every point of both. Remove convexity from either and no line exists, which is what the hypothesis was for.
The least area a width can hold
Barbier's theorem says every curve of constant width has the same perimeter, which removes perimeter as a way of telling the family apart. Area is not like that — the circle holds the most and the Reuleaux triangle the least — and the reason the minimiser has corners is a constraint rather than a preference.
Half a circle against a wall
Lay a fence of fixed length with both ends against a straight wall and the best shape is a half-circle, holding exactly twice what a full circle of the same fence holds. The proof is a mirror: doubled in the wall, any fence becomes a closed curve with twice the length and twice the area, and the closed-curve answer carries over. In a corner the same mirrors give a slice of a circle — until the corner's angle stops dividing a half-turn.
Nearly the most means nearly round
A shape that holds almost as much as a circle of the same perimeter must almost be a circle. Bonnesen made that exact: the ring between a convex shape's largest inscribed circle and smallest enclosing circle is never wider than √(L² − 4πA)/π. Three quite different shapes holding 99% of the circle's area all have rings under 9.55 wide, and not one of 200 random convex shapes breaks the bound.
Patience instead of a contract
Commitment had to assume an announcement binds. Play the same game again tomorrow and the assumption is unnecessary — the future does the binding. What it costs is that nearly every outcome becomes an equilibrium, so a theory that could not choose between two now cannot choose between infinitely many.
A map that offers a choice
Brouwer's theorem needs a function, and the object it was most wanted for is not one — a best reply is a whole set whenever a chooser is indifferent. Allow a point to be sent to a set and the fixed point survives, provided the sets are convex, and the convexity is the entire hypothesis.
Any unevenness brings the match sooner
Real birthdays are not spread evenly across the year, and every such departure pushes the famous twenty-three down rather than up. The proof is one move on two days at a time, and what it leaves behind is a single number — the one ecologists use to count species.
The product that makes a division fair
Divide goods to make the total happiness as large as possible and the result can be monstrously unfair; make the least happy person as happy as possible and it can waste. Multiply the people's values together and maximise the product instead, and something unexpected happens — nobody envies anybody when goods can be split, and nobody envies by more than one item when they cannot.
Moves that only ever add edges
Turán's theorem says the densest graph avoiding a complete graph on r + 1 points is the balanced r-part graph. Zykov's proof finds it by a sequence of moves — turn a point into a copy of a better-connected one it is not joined to — each of which adds edges and none of which can create the forbidden clique. A second proof spreads a unit of weight over the points and gets the same bound from a maximum.
The densest graph without a square
Forbid four points joined in a cycle and a graph can keep only about ½n^(3/2) of its edges — far fewer than the quarter of all pairs a triangle-free graph keeps. Counting pairs of neighbours proves the ceiling in two lines. What reaches it is not a random graph but a finite geometry: the points of a projective plane, joined when they are orthogonal.
When one of the two numbers is missing
The duality theorem is usually quoted as an equality: a linear program and its dual reach the same number. That is one of four cases. A program can run away to infinity, or have no feasible point at all, and then its dual is forced into a matching failure. Every small program with coefficients from minus one to one has been classified, and the table has exactly four occupied cells out of nine.
The lines the optimum lies under
Change the resources a linear program is given and its best value changes too, tracing a graph. Every solution of the dual is a straight line lying above that graph, and the graph is exactly the lowest of those lines — a bent roof of finitely many planks. Require the answer to be in whole numbers and the roof stays where it was while the graph falls away beneath it in steps, and the space between is the part of the problem no price can see.
The cheapest way to send
Put a price on every road as well as a capacity and ask for the cheapest way to send four units. Twenty-eight ways exist and one is cheapest, and two certificates prove it without comparing it with the other twenty-seven: no cycle of roads it leaves unused costs less than nothing to push round, and there are prices at the places that every usable road fails to beat.
The least wall for equal rooms
Divide the plane into rooms of equal area using as little wall as possible, and every wall does double duty. Bees settled on hexagons long ago, and the proof that nothing does better — not even rooms with curved walls — came in 1999. The straight-walled half of it is two facts: the rooms of any division average six sides, and more sides never cost more wall.
Every chord slid to the middle
Take a shape, pick a line, and slide every chord that crosses the line at right angles until the line cuts it in half. The area cannot change, the boundary can only get shorter, and the result is symmetric. Do it again about another line, and another, and the shape is squeezed towards a disc — unless the lines are badly chosen, in which case it stops short.
Every count a solid can have
Euler's formula ties the corners, edges and faces of a convex solid together, but it does not say which numbers are possible. Ernst Steinitz answered in 1906: V corners and F faces occur together exactly when neither is more than twice the other less four. The proof in one direction is two lines of counting; in the other it is two moves — cut off a corner, glue on a tetrahedron — that walk from the pyramids to every allowed pair.
The corners are the orders of arrival
Line the players up, let each join in turn, and pay each what it adds on arrival: every order gives a split. When a newcomer always adds at least as much to a bigger group, those splits are exactly the corners of the core — so the core is never empty, it is the outline of the orders, and the average over all of them lies inside it. For a group worth the square of its size the outline is a hexagon whose corners are the six orderings of 1, 3 and 5.
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.
Every point at the average of its neighbours
A planar graph can be drawn without crossings, but finding such a drawing looks like a search. Tutte found in 1963 that it is not: pin one face to a convex polygon, put every other point at the average of its neighbours, and the drawing that results has straight edges, convex faces and no crossings at all — provided no two points can cut the graph apart. It is the position a network of equal springs settles into, and it is also where a random walk expects to leave.
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.
The shape a random ball grows into
Give every road of the square grid a random travel time and ask what can be reached from one point in time t. The region is ragged, and rescaled it converges to a fixed convex shape — but which shape is unknown for every natural law. Computing it shows a curve within a few per cent of a circle for continuous travel times, a flat side where fast roads percolate along a diagonal, a time per step that is still drifting at a hundred and twenty-eight steps, and fluctuations that grow like the distance to the power one third rather than one half.
A rent nobody envies is not one rent
Three housemates, three rooms, one rent, and Sperner's lemma promises a split nobody envies. It does not promise one split. For housemates who judge rooms by value for money, the envy-free splits fill a polygon, and in a typical house some room's rent can move across a quarter of the total without anyone envying anyone. Choosing inside it is a second decision. The rule the rent-splitting websites use makes the worst-off housemate as well off as possible, and in almost every house it rewards a housemate who understates what the rooms are worth.
Only one curve through the factorials bends the right way
Infinitely many smooth curves pass through 1, 1, 2, 6, 24, 120, and some of them even obey the factorial's own rule, f(x + 1) = (x + 1)·f(x), at every x. Ask that the logarithm of the curve bend upwards everywhere and exactly one survives — Euler's integral. A wiggle of any size breaks the condition somewhere, the smaller the wiggle the further out, and the proof that nothing else survives is a squeeze that computes √π along the way.
The point nearest in total to three corners
Three towns want one depot with the least total road to all of them. The answer is not the centroid or any of the classical centres: it is the point from which every side of the triangle is seen at 120°, found by building equilateral triangles on the sides. Three straight lines through it have the same length, and that length is the least total. When an angle of the triangle reaches 120°, the answer jumps to that corner — and the same 120° rule shapes soap films and the shortest networks joining many points.
A market too large to bargain in
Two traders swapping goods can settle anywhere along a stretch of possible deals; nothing forces a price. Bring in a second pair of the same traders and some of those deals can be refused by a group of three. With thirty of each, the only deals no group can refuse lie within a few thousandths of the one a price would produce. Edgeworth guessed in 1881 that competition shrinks bargaining to prices; Debreu and Scarf proved it, and the shrinking can be computed.
A cut that gets sharper as the map gets lazier
Iterating a map that shrinks distances by 0.9999 takes 141,254 steps to reach its fixed point to a millionth. Cutting takes six: read the map at one point, and the fixed point must lie on the far side of the line halfway between the point and its image. The cut gets better exactly where iteration gets worse, because a map that barely shrinks puts its fixed point almost on every such line.
The corners of a random hull
Drop ten thousand points at random into a triangle and stretch a band round them: about twenty points touch it. Drop them into a disc and about seventy-three do. The count grows like a logarithm in one shape and like a cube root in the other, and the reason is where the boundary bends.
A core is a rare thing to find at random
A game has a core when the whole can be shared so that no group would do better on its own, and Bondareva and Shapley turned that into a finite list of checks. For three players there are five checks; for four, forty-one; for five, 1,291. Draw the coalitions' values at random and the list wins: a third of three-player games fail, nineteen four-player games in twenty, and not one five-player game in two thousand passes. The cores that theorems promise come from structure, and structure is exactly what a random game lacks.
Named alongside it
The objects these essays reach for when they reach for this one.
DualityLinear programAreaCircleExistence proofConvex hullOptimalityOptimisationTilingVoronoi diagramConstant widthEuler characteristic