Matpic
mathematics, in pictures
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 3 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 Several colours on every vertex of a Kneser graph. A grid of Kneser graphs on pairs from five to eight points against the number of colours per vertex, each cell giving the fewest colours needed and the counting lower bound.

Several colours on every vertex

Give every pair from six points three colours, so that pairs with nothing in common share no colour. Counting says nine colours might do; ten are needed. Stahl conjectured in 1976 exactly how many colours every such problem needs — a formula that meets Lovász's topological answer at one colour a vertex and the obvious answer at k — and a search over stars and triangles confirms it in every case small enough to run.

topology · Borsuk ulam

Named alongside it

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

Antipodal pairChromatic numberExhaustive searchGraph colouringBinomial coefficientContinuityCounting argumentCounting two waysCyclic orderErdos ko radoExistence proofExtremal problem

All concepts