Concept

Matching

A set of pairings in which no element appears twice. Whether one covering everything exists is decided by a condition on every set of elements at once, and a largest one is found by improving a partial one along alternating paths.

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

A matching that covers all 5 of one side. A bipartite graph with every possible pairing drawn thin and one complete matching drawn thick, so that each vertex on the left is joined to a distinct vertex on the right.

One 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.

discrete · halls theorem

A table of shares written as a lottery over 3 whole assignments. A doubly stochastic table of shares, and beneath it the permutation matrices and weights that add up to it exactly, each drawn as a grid with one marked cell per row.

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.

applied · assignment

Named alongside it

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

Assignment Convexity Counting argument Deficiency Doubly stochastic Existence proof Fairness Graph Latin square Linear program Permutation Pigeonhole principle

All concepts