Matpic
mathematics, in pictures
Concept

Poset — where it appears

A set with a rule saying that some pairs of its elements come before others, consistently and without cycles, leaving the rest incomparable. It is the mathematics of partial information: what is known about an order, before everything has been compared.

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

Everybody's share of the 24 chains. The subsets of a set of 4, each labelled with the fraction of maximal chains it lies on; the shares of any antichain add to at most one, and to exactly one only for a whole layer.

Everybody's share of the chains

There are twenty-four ways to build a four-element set one element at a time. Every subset lies on some of them, and no two incomparable subsets share one — so an antichain is a set of disjoint shares of a single whole.

discrete · posets The cube cut into 6 symmetric chains. The subsets of a set of 4 partitioned into 6 chains by the bracket rule, each chain running from size k to size 4 − k and passing once through the middle layer.

The cube cut into chains

Write a subset as a string of brackets, match them the ordinary way, and the unmatched ones say which chain it is on. Six chains cover all sixteen subsets of a four-element set, and the bound and the example arrive together.

discrete · posets At most 3 of the 7 arcs can pairwise meet. The 7 elements arranged round a circle with the 7 arcs of 3 consecutive drawn, and the largest collection of arcs that pairwise intersect picked out.

The largest family that always meets

Change the question from "no two comparable" to "every two share an element" and the answer changes shape. The best antichain is a whole layer; the best intersecting family is a star, and the proof is a circle.

discrete · posets 16 ways to sort it. A small order with its 16 linear extensions counted, and for each incomparable pair the fraction of extensions putting one before the other.

How many ways to sort it

An order says some things come before others and leaves the rest open. Counting the orderings consistent with it measures how much is still unknown — and the counting is as hard as any counting problem gets.

discrete · posets

Named alongside it

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

Binomial coefficientCounting argumentAntichainChainCounting two waysExtremal problemSperner theoremBijectionComplexityConjectureCyclic orderErdos ko rado

All concepts