Concept

Hasse diagram

A drawing of an ordering in which each element sits directly above those it covers, with the implied steps left out. It is the smallest drawing from which the whole ordering can be recovered, since the implied relations are exactly the paths upward.

Named by 3 essays across 3 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

The widest layer of the subsets of a set of 4. A Hasse diagram of a small order with the widest layer marked, and the largest set of mutually incomparable elements found by examining every subset.

The widest layer and the longest chain

Order sixteen subsets by inclusion and ask for the largest collection with no two comparable. The answer is the six subsets of size two — the widest layer — and no cleverer collection beats it. Ask instead for the fewest chains covering everything, and the answer is the same number again.

discrete · Posets

Named alongside it

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

Order lattice Partial order Antichain Binomial coefficient Blocking pair Chain Counting two ways Deferred acceptance Dilworth theorem Divisor function Divisor sum Geometric series

All concepts