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.

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

124361251020153060× 2 →× 3 ↑2^2 × 3 × 5 — 3 × 2 × 2 = 12 divisors

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 better for side one, worse for side twoM1 A4 B2 C1 D3side one's ranks 2, 2, 2, 2M2 A3 B2 C1 D4side one's ranks 3, 2, 2, 3M3 A4 B1 C2 D3side one's ranks 2, 4, 3, 2M4 A3 B1 C2 D4side one's ranks 3, 4, 3, 3join and meet, on every pairpairjoinmeetM1, M2M1M2M1, M3M1M3M1, M4M1M4M2, M3M1M4M2, M4M2M4M3, M4M3M44 of the 24 matchings are stable, drawn with the best for side one at the topevery one of the 16 ordered pairs was joined and met, and all 32 results were themselves stablethe top A4 B2 C1 D3 is what side one proposing returns; the bottom A3 B1 C2 D4 is what side two proposing returns

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 4's true ranking of side one, best firstCDAtruthfulBtruthfully: A4 B2 C1 D3one cell per ranking 4 could submit, labelled with the partner it returnsAAAAAABBBBBBAABBADAADDADthe true rankinga ranking that paysthe 4 profitable misreports, submitted ranking and partner obtainedsubmittedpartnertrue rankCDBAD2 of 4DBACD2 of 4DBCAD2 of 4DCBAD2 of 4the control: the same search, every member of both sides, 24 rankings eachside onepaysside twopaysA010B020C030D0444 truly ranks side one CDAB and gets A, its 3rd choiceof the 24 rankings it could submit instead, 4 return a partner it strictly prefersthe same sweep over every member of the proposing side searched 96 rankings and found none, which is whatmakes the 4 a finding

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 ladder 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

Named alongside it

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

Blocking pairDeferred acceptanceHasse diagramPreference profileStable matchingCounterexampleCounting two waysDivisor functionDivisor sumGeometric seriesLatticeMultiplicative function

All concepts