Matpic
mathematics, in pictures
Concept

Sperner theorem

The statement that the largest collection of subsets of a set with no two comparable is a whole layer — all the subsets of one size, the middle one. It is the founding result of extremal set theory, and its proofs generalise far better than the statement does.

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

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.

AntichainBinomial coefficientChainPosetBijectionCounting argumentCounting two waysDilworth theoremExtremal problemHasse diagramLYM inequalityMatching

All concepts