Concept

Bipartite graph

A graph whose vertices split into two sides, every edge joining one side to the other. It models pairings — applicants and posts, rows and columns — and its matchings are governed by Hall's condition on groups of vertices.

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

A cycle through the middle two levels of the 5-cube: 20 words. The words of length 5 with 2 or 3 ones placed round a ring in the order of a Hamiltonian cycle, alternating between the two levels, each step changing a single place.

The walk through the middle levels

On seven places, the words with three ones and the words with four number thirty-five each. Is there a closed walk through all seventy, changing one place at a time and never leaving those two levels? On five places the answer is 24 walks, on seven and nine a search finds one in moments — and whether one exists for every odd length was open for thirty years, until Torsten Mütze proved in 2016 that it always does.

discrete · Hamiltonian cycles

An infinite graph that passes every finite test. Two columns of vertices continuing downward without end. The top left vertex joins every vertex on the right; each other left vertex joins only the one beside it.

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

discrete · Halls theorem

Named alongside it

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

Axiom of choice Binomial coefficient Combinations Compactness Counting argument Gray code Hypercube Infinity Matching Parity Pigeonhole principle

All concepts