Concept

Extremal problem

A question asking how large or small a structure can be while keeping some property. The answer usually has two halves that are proved separately: a bound saying nothing can beat some number, and a construction reaching it.

Named by 2 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

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

Named alongside it

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

Binomial coefficient Counting argument Counting two ways Poset Antichain Chain Cyclic order Erdos ko rado Intersecting family Lym inequality Sperner theorem Star

All concepts