Matpic
mathematics, in pictures
Concept

Certificate

A short piece of data accompanying an answer that lets anybody verify it without repeating the computation. A set of dual prices certifies an assignment's optimality in a quadratic number of comparisons, against a factorial search.

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

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

However much a network can carry from one place to another, there is a way of cutting it in two whose total capacity is exactly that number. One quantity is a maximum over ways of routing and the other a minimum over ways of severing, and they are never off by even one.

discrete · Network flow A cheapest assignment, and the proof that it is cheapest. A 4 by 4 cost table with the cheapest assignment marked, and a row price and column price beside each. Every used cell's two prices add to its cost, and the prices total the assignment's cost.

A price for every person and task

The cheapest assignment can be found without comparing it to any other. Attach a number to each person and each task so that no pair's two numbers exceed its cost, and if the numbers add to an assignment's total, that assignment is cheapest — proved, by an argument that never mentions the alternatives.

applied · Assignment Two convex sets 1.50 apart, and the line that separates them. Two convex polygons with a straight line drawn between them, together with the shortest segment joining the two sets, whose perpendicular bisector the line is.

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.

analysis · Convexity Three pairs of places sharing one hub. A hub with three spokes of capacity one, the three pairs of outer places each routing half a unit through it, beside the total that can be sent fractionally, in whole units, and the cost of the cheapest set of roads separating every pair.

When several pairs share the roads

For one pair of places, the most that can travel between them equals the cheapest cut that separates them. Give three pairs a hub of three roads to share and the two numbers come apart: the pairs can send 3/2 between them, while separating every pair costs 2. Two pairs still meet their cut, but only by splitting units in half.

discrete · Network flow A network of six places and the tree that holds all fifteen of its cheapest cuts. A network with capacities on its roads beside a tree on the same places, whose edge numbers give the cheapest cut between any two places as the smallest number on the path joining them.

One tree for every cut

A network of six places has fifteen pairs, and each pair has its own cheapest cut. All fifteen can be read off a tree with five numbers on it: the cheapest cut between any two places is the smallest number on the tree's path between them. Gomory and Hu proved in 1961 that such a tree always exists, and building it takes five cuts, not fifteen.

discrete · Network flow A matching of 4 and a cover of 4. A bipartite graph with its largest matching drawn thick and a smallest set of vertices meeting every edge ringed, the two having the same size.

What the search has when it fails

A largest matching is easy to find and hard to certify: the claim that nothing larger exists is a claim about every arrangement not tried. The certificate turns out to be free — it is the wreckage of the search that failed.

discrete · Halls theorem The duality theorem's four cases, counted over 6,561 small programs. A three-by-three table crossing the status of a linear program — optimal, unbounded or infeasible — with the status of its dual, counting every small program with coefficients from minus one to one. Five of the nine cells are empty.

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.

applied · Duality The cheapest way to send 4 units, for 25. A directed network from s to t with a capacity and a price on each road, showing the whole-number flow of 4 units with the least total cost, the arrows thickened by the amount they carry.

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.

discrete · Network flow An auction for 4 objects, bid by bid, with increment 1/5. A 4 by 4 table of values beside the log of 12 bids of an auction with increment 1/5: bidder, object, the raise, and the prices after each bid; it ends with total value 26.

Prices the bidders raise

The cheapest assignment is certified by a price on every task, and those prices can be found without anyone in charge. Let each unassigned person bid for the task that suits them best at current prices, raise its price by a little more than it is worth to them over the next best, and wait. The bidding ends, and when the increment is small enough the prices it ends at are a proof of optimality.

applied · Assignment 3 moves along the edges to the corner that maximises 2x₁ + 3x₂. The simplex method on a two-variable program with 5 constraints, started at the origin. It visits (0, 0), (0, 8), (1, 8), (5/2, 15/2), with objective values 0, 24, 26, 55/2, and stops where the prices on both binding constraints are non-negative.

Prices at every corner

The duality theorem says a linear program's best value equals its dual's, and says nothing about how to find either. The simplex method finds both at once — it walks from corner to corner, and at each one asks the constraints that meet there for prices. A negative price names an edge that climbs; when none is negative, the prices are the proof.

applied · Duality Two stable cycles a hair from the classical Hénon attractor. The Hénon attractor at a = 1.4 with the certified stable period-13 orbit at a = 1.39945 and period-19 orbit at a = 1.4001616 drawn over it.

Stable cycles a hair from Hénon's chaos

Nobody knows whether the Hénon map at a = 1.4 is chaotic, because a stable cycle in a window too thin to see would look exactly the same. So hunt the windows: a stable orbit of period 19 at a = 1.4001616, proved to exist and to attract by interval arithmetic, in a window 15 hundred-millionths wide and 0.00016 from the classical value — and nothing nearer, down to a spacing of a ten-billionth.

dynamics · Strange attractor

Named alongside it

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

DualityFlowLinear programComplementary slacknessConvexityCounterexampleCutMatchingMin-max theoremAlgorithmAssignmentCapacity

All concepts