Concept

Intersecting family

A collection of sets in which every two members share at least one element. The Erdős–Ko–Rado theorem bounds how large such a family of k-sets can be, and in a Kneser graph the families are exactly the sets of vertices that one colour may take.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

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

The pairs from five, joined when disjoint, need three colours. The Petersen graph drawn with its ten vertices labelled by pairs from one to five, edges joining disjoint pairs, and a proper colouring with three colours.

The colours a circle forces

Take every pair from five things and join two pairs when they share nothing. Three colours are enough to colour the result so joined pairs differ, and two are not — but no triangle, no dense cluster and no counting argument explains why. The reason is five points on a circle and a direction that cannot be told apart from its opposite, and the same reason, one sphere at a time, settles Kneser's question for every size.

topology · Borsuk ulam

Named alongside it

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

Antipodal pair Binomial coefficient Chromatic number Continuity Counting argument Counting two ways Cyclic order Erdos ko rado Exhaustive search Existence proof Extremal problem Graph colouring

All concepts