Matpic
mathematics, in pictures
Concept

Antichain

A collection of elements of an order no two of which are comparable — none is above or below another. The largest one measures how much of an order is undecided, and for the subsets of a set it turns out to be a whole layer of them, which is Sperner's theorem.

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

Also named here as chain, sperner theorem — the same set of essays touches all of them, so they are one junction rather than several.

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

Named alongside it

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

Binomial coefficientChainSperner theoremPosetBijectionCounting argumentCounting two waysDilworth theoremExtremal problemHasse diagramLym inequalityMatching

All concepts