Generator

bipartite

A generator in the discrete library, called 7 times across 2 essays. Below: what it draws at its defaults and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

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.

At its defaults

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.

`show: "hall"`

3 applicants who between them can fill only 2 posts. A bipartite graph with no complete matching, and the set of vertices responsible: several on the left whose neighbours between them are fewer in number than they are.

`show: "regular"`

A 3-regular bipartite graph split into 3 matchings. A bipartite graph in which every vertex has 3 edges, with its edges coloured so that each colour class is a complete matching.

`show: "deficiency"`

Matching shortfall against worst overshoot, on three graphs. A table of three bipartite graphs, each with the size of its largest matching, the set of vertices with the fewest neighbours relative to its size, and the two numbers that agree.

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.

round 1 still has a matching covering every vertex ×3
and every neighbour named is a vertex on the right ×1
and no vertex is matched twice ×1
and so does every vertex on the right ×1
and the reason is a set with too few neighbours between them ×1
and the rounds use up every edge exactly once ×1
between two and four graphs the family knows are compared ×1
every edge gets exactly one colour ×1
every matched pair is an edge of the graph ×1
every vertex on the left has a neighbour list ×1
every vertex on the left has the same degree ×1
the graph is one the family knows ×1
the largest matching is exactly the left side less the worst deficiency ×1
the table has both a graph that succeeds and a graph that fails ×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

Where it is called

Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.

Applied

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.

Discrete

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.

The whole library · What the figures prove