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 5 essays across 3 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

A sequence of 3² with no climb and no fall longer than 3. 10 terms plotted in order, each labelled with the longest climb and the longest fall ending at it; the first 9 keep both counters at 3 or below and the last one cannot.

The sequence that cannot avoid a staircase

Any ten numbers in a row contain four that climb or four that fall. The proof gives every term a pair of counters, notices that no two terms can share a pair, and is finished — with a bound that is exactly right.

discrete · Ramsey theory

Building a spanning tree by keeping every edge that closes no loop. Four stages of a greedy pass over the fourteen edges of an eight-point graph, ending with a spanning tree of 7 edges.

A spanning tree for every graph

Every connected graph has a spanning tree: a set of its edges that joins every point and closes no loop. For a finite graph the proof is a greedy pass over the edges. For an infinite graph the greedy pass has to keep going past the end of every list, and the statement turns out to be exactly as strong as the axiom of choice — Zorn's lemma supplies the tree, and the existence of spanning trees in every graph gives back the whole axiom.

logic · Axiom of choice

The flip graph of the hexagon, given a direction. Tamari lattice T4: 14 elements 3210, 3200, 3010, 3100, 3000, 0210, 0200, 1010, 0010, 2100, 2000, 0100, 1000, 0000; 21 covering relations; 68 intervals.

Pairs of trees that count planar maps

Give every flip of a triangulation a direction and the triangulations become an order, the Tamari lattice. Counting the pairs that are in order — 1, 3, 13, 68, 399, 2,530, 16,965, 118,668, 857,956 — gives 2(4n + 1)!/((n + 1)!(3n + 2)!), which is exactly Tutte's 1962 count of planar triangulations. Chapoton noticed the match in 2006; a pair of trees and a map on a sphere turn out to be the same thing.

discrete · Catalan numbers

Named alongside it

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

Hasse diagram Order lattice Antichain Axiom of choice Binary trees Binomial coefficient Blocking pair Catalan numbers Chain Convex position Counting argument Counting two ways

All concepts