Matpic
mathematics, in pictures
Concept

Deficiency

How far a set overshoots what it can be matched to: the size of a set of vertices less the number of vertices its edges reach. Its largest value over all such sets is exactly how many vertices a largest matching must leave out, which turns a claim about every arrangement into a set anybody can count.

Named by 3 essays across one field — 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 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 A graph whose matching misses 2 of its 10 vertices. A graph with its largest matching drawn thick, a set of vertices ringed, and the pieces left when that set is deleted marked by whether they hold an odd number of vertices.

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

discrete · Halls theorem

Named alongside it

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

Counting argumentExistence proofGraphMatchingCertificateConnectivityDualityLatin squareParityPigeonhole principleTransversalVertex cover

All concepts