Concept

Partial order

A way of comparing elements that need not compare every pair, being reflexive, transitive, and never putting two distinct elements each below the other. Subsets under inclusion and whole numbers under divisibility are the standard examples, and the pairs it leaves uncompared are what its antichains count.

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

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.

Hasse diagram Antichain Binomial coefficient Blocking pair Chain Deferred acceptance Dilworth theorem Matching Order lattice Preference profile Sperner theorem Stable matching

All concepts