A matching that covers all 5 of one side
bipartite is one function. Everything below came out of it during this
build, at parameters taken from the essays rather than invented for this page — so a figure
here is the same figure a reader meets in an essay, and if the generator changes, this page
changes with it.
With nothing chosen
3 applicants who between them can fill only 2 posts
A 3-regular bipartite graph split into 3 matchings
An infinite graph that passes every finite test
Partial matchings that all die
Why greedy always gets at least half
What it checks while it draws
Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.
- the branch giving a₀ the partner b1 dies when a1 is reached ×5
- round 1 still has a matching covering every vertex ×3
- a largest matching of the contracted graph, plus two edges inside the cycle, is a largest matching of the original — which is why contracting is allowed ×1
- a largest matching of this graph holds three edges ×1
- a sliding domino lands on a free square of the diamond ×1
- a typical random order matches more ×1
- an order as bad as the adversary's is rare ×1
- and each level has at most two nodes, one of them about to die ×1
- and every neighbour named is a vertex on the right ×1
- and it is a smallest one, against a scan of every subset of the vertices ×1
- and it leaves the stem's end unmatched, which is where a search would start ×1
- and no vertex is matched twice ×1
- and one whose obstruction is a set that has to be deleted before the odd pieces appear ×1
- and one whose obstruction needs no vertices deleted at all — an odd graph is already short by one ×1
- and so does every vertex on the right ×1
- and stays above it, up to sampling ×1
- and the empty set already gives an excess of at least nothing ×1
- and the reason is a set with too few neighbours between them ×1
- and the rounds use up every edge exactly once ×1
- arrivals choosing by rank and places choosing by arrival time give the same matching ×1
- between four and nine vertices a side are drawn ×1
- between four and twelve vertices a side ×1
- between three and seven graphs the family knows are compared ×1
- between two and five graphs with sides are compared ×1
- between two and four graphs the family knows are compared ×1
- blocked: and it is the size of the largest matching ×1
- blocked: the cover the search leaves is a smallest one ×1
- cycle5: the matching's shortfall is the worst odd excess ×1
- dominoes in an Aztec diamond of this order ×1
- each of which is reached trivially ×1
- every board missing a corner and a square of the other colour can be tiled ×1
- every edge gets exactly one colour ×1
- every edge of the best matching touches a greedy edge ×1
- every finite set of left vertices has at least as many neighbours ×1
- every hole is a two-by-two block ×1
- every level of the finite-degree tree is nonempty ×1
- every matched pair is an edge of the graph ×1
- every right vertex reached is matched — an unmatched one would be an augmenting path and the matching would not be largest ×1
- every vertex on the left has a neighbour list ×1
- every vertex on the left has the same degree ×1
- four to seven levels ×1
- frozen squares and the outside of the circle mostly coincide at order 100 ×1
- greedy in the adversary's order matches half ×1
- greedy, taking the first available, matches one ×1
- in the adversary's order the rule matches exactly half ×1
- jobs: and it is the size of the largest matching ×1
- jobs: the cover the search leaves is a smallest one ×1
- minus signs round a unit face ×1
- narrow: and it is the size of the largest matching ×1
- narrow: the cover the search leaves is a smallest one ×1
- net: the matching's shortfall is the worst odd excess ×1
- no graph found beats the proved floor for RANKING in random order ×1
- no order does worse than the adversary's half ×1
- no ranking does worse than half, as any greedy rule guarantees ×1
- no signing of K3,3 makes the determinant 6 ×1
- nor the floor 1 − 1/e for greedy in random order ×1
- plain determinant terms that come out positive ×1
- random-order greedy and adversarial RANKING both approach 1 − 1/e ×1
- RANKING in random order climbs well above both on this graph ×1
- RANKING's share on the triangle approaches 1 − 1/e ×1
- rectangles whose plain determinant is 0 or 1 ×1
- regular: and it is the size of the largest matching ×1
- regular: the cover the search leaves is a smallest one ×1
- signings of K3,3 giving 0 or 4 ×1
- so exactly one vertex is left out ×1
- so greedy has at least half as many edges ×1
- star: the matching's shortfall is the worst odd excess ×1
- tail: the matching's shortfall is the worst odd excess ×1
- the attempted partner for a₀ is one of the drawn b's ×1
- the best matching matches both ×1
- the column rule alone is wrong exactly when the hole is interior ×1
- the cover is strictly larger than the matching, which is where König's equality fails ×1
- the cycle is odd, which is what makes it a blossom ×1
- the determinant with the cut agrees with the listed count ×1
- the diamond has 2 to the 1/4 tilings per square at every order ×1
- the disagreement shrinks as the diamond grows ×1
- the formula agrees with the listed count ×1
- the graph is one the family knows ×1
- the graph is the counterexample or the finite-degree one ×1
- the largest matching is exactly the left side less the worst deficiency ×1
- the matching drawn is made of edges of the graph ×1
- the order is drawable ×1
- the per-square rate climbs to its limit from below ×1
- the plain determinant of the 4 by 4 board ×1
- the search starts at every left vertex the matching missed ×1
- the search starts from the triangular graph and keeps anything worse ×1
- the set built from the failed search touches every edge of the graph ×1
- the signs count the 4 by 5 board ×1
- the step drawn deletes a colliding pair ×1
- the table has both a graph that succeeds and a graph that fails ×1
- the table holds a graph that succeeds and a graph that fails ×1
- the table holds both a graph with a perfect matching and one without ×1
- the triangular graph has a perfect matching: arrival t to place t ×1
- the vertices a largest matching misses are exactly the worst excess of odd components over the set removed ×1
- the view is one the family draws ×1
- this view is for a graph that has no complete matching ×1
- this view is for a graph whose matching covers the whole left side ×1
- this view is for a graph with an odd cycle in it ×1
- tilings of the 4 by 4 board ×1
- tilings of the board missing two opposite corners ×1
- tilings of the order-2 Aztec diamond ×1
- triangle: the matching's shortfall is the worst odd excess ×1
- trident: the matching's shortfall is the worst odd excess ×1
- two of the matching's edges lie inside the cycle, and the fifth vertex is matched outside it ×1
- which is König's theorem: the smallest cover and the largest matching are one number ×1
- with the signs every tiling contributes alike ×1
Where it is called
Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.
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.
DiscreteEnough partners in every finite group
Hall's theorem says a matching exists unless some group has too few partners between them. On an infinite graph that is false: one vertex that can be paired with anybody, and every other with exactly one, passes the test on every finite group and has no matching at all. The failure needs a vertex with infinitely many choices. Forbid that, and the theorem comes back, by an argument about trees rather than about matchings.
DiscreteMatching as they arrive
Applicants arrive one at a time, and each must be given a post or turned away on the spot. Any sensible rule matches at least half as many as the best assignment chosen with hindsight, and an adversary arranging the arrivals can hold every fixed rule to exactly half. Shuffle the posts once, at random, and give each arrival its best-ranked free post: the guarantee rises to 1 − 1/e, about 63%, and no rule of any kind can do better.
DiscreteMatching when the arrivals are shuffled
An adversary who chooses the order in which applicants arrive can hold any fixed matching rule to half the best. Take the order away and let it be random, and the plainest rule of all — give each arrival its first free place in a fixed list — rises to 1 − 1/e, because shuffling the arrivals turns out to be exactly the trick RANKING plays with the places, seen from the other side. Shuffle both and the guarantee rises again, to somewhere between 0.696 and 0.727, and where in that interval it lies is not known.
ComputationNine thousand four hundred and eight
There are four Latin squares of order four once the first row and column are fixed, fifty-six of order five, and nine thousand four hundred and eight of order six. The exact answer is known for eleven orders and for no more — and yet a half-finished square can always be finished.
DiscreteOne bottleneck and nothing else
A set of jobs can be filled by distinct people unless some group of jobs has too few candidates between them — and that single obstruction is the only one there is, which is what makes the theorem worth having.
DiscreteSigns that make a determinant count
Hall's theorem says whether a board can be covered by dominoes. How many ways it can be covered is a different question, and for a general graph a hopeless one — the count is a permanent, and nobody expects an efficient way to compute permanents. On a flat board it is a determinant. Put a minus sign on the vertical pairs in every second column and the thirty-six coverings of a four-by-four board stop cancelling and add up; the chessboard has 12,988,816. A hole in the board breaks the rule in a way a cut repairs, and on K₃,₃, which cannot be drawn flat, no choice among its 512 signings works at all.
DiscreteThe 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.
DiscreteThe diamond that freezes its corners
A square board's domino tilings grow like 1.3385 choices per square. Arrange the same squares in a staircase-edged diamond and the count is exactly 2 to the n(n+1)/2 — only 1.1892 choices per square, at every size. The boundary has reached into the middle. Pick one of the diamond's tilings at random and the reason is visible: outside the circle inscribed in the diamond the dominoes are frozen into solid brickwork, and only inside it is the tiling free.
DiscreteThe edge that forces a triangle
A graph on six points can carry nine edges with no three of them closing a triangle. It cannot carry ten. The bound is n²/4, the graphs that achieve it are all the same shape, and both facts fall out of examining every graph there is.
DiscreteThe piece that cannot pair off
Take the sides away and the obstruction to a matching changes character completely. It is no longer a shortage of partners; it is a parity, and the quantity that measures it counts pieces of odd size rather than vertices of any size.
AlgebraThe same sum without its minus signs
Delete the signs from the determinant's sum over permutations and what is left counts things directly rather than by cancellation. It is a better count and a far worse object — because the cancellation was what made the determinant computable.
DiscreteWhat 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.