Matpic
mathematics, in pictures
Concept

Order lattice

An ordering in which every two elements have a greatest lower bound and a least upper bound, whatever else is incomparable. The power set of any collection is one, with intersection and union playing the two roles.

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

The divisors of 60. Every divisor as a lattice point, one axis per prime, joined when one divides the other by a single prime.

The shape of a number's divisors

Lay a number's divisors out as a lattice with one axis per prime, and two of the most useful facts in arithmetic stop being formulas and become the width and the corner of a rectangle.

number · Unique factorisation The 4 stable matchings of the instance, ordered by side one's preference. A Hasse diagram of the stable matchings with the best for side one at the top, beside a table giving the join and the meet of every pair.

The side that proposes wins

An instance usually has several stable matchings, and the set of them is not a heap — it is a lattice, closed under taking the better partner and under taking the worse. The two ends of that lattice are exactly what deferred acceptance returns from the two sides, so whoever proposes decides which end the instance lands on.

applied · Stable matching Every ranking 4 could submit, and the 4 that pay. One participant's true ranking, a cell for every ranking they could submit instead labelled with the partner it returns, the profitable misreports listed, and the same search run on the proposing side finding none.

No stable rule is safe from a lie

A stable matching always exists, and the side that proposes gets the best one it could hope for. This essay closes the story with the result that spoils it — one participant's whole strategy space searched, four submissions found that beat the truth, and a theorem saying no rule anywhere escapes.

applied · Stable matching Every stable matching leaves out the same people. 4 stable matchings of a market with short lists, drawn as two columns joined by edges; every one leaves the same letter and number unmatched.

The people every stable answer leaves out

Let the lists be short and let one side take several partners. Stable matchings still exist and there can be many of them — but every one leaves out exactly the same people, and a member who is left with an empty place holds exactly the same partners in every one. A three-line count proves it.

applied · Stable matching

Named alongside it

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

Blocking pairDeferred acceptancePreference profileStable matchingCounting two waysHasse diagramCounterexampleDivisor functionDivisor sumExhaustive searchGeometric seriesInvariant

All concepts