Helly's theorem

Remarks

Proof idea: induct on $m$, starting from $m = d + 1$. For $m \ge d + 2$, the induction hypothesis gives, for each $j$, a point $x_j$ in all the sets except possibly $C_j$. Radon's theorem applied to $x_1, \dots, x_m$ gives a partition into $A$ and $B$ with a common point $p$ of their convex hulls. Each $C_i$ contains all of $A$ or all of $B$, so it contains $p$ by convexity.

Example: if every three of finitely many convex sets in the plane meet, then all of them meet.

The number $d + 1$ cannot be lowered: the three lines that contain the sides of a triangle in $\R^2$ meet in pairs but have no common point. For an infinite family the statement can fail: the half-lines $[k, \infty)$, $k = 1, 2, \dots$, in $\R$ meet in pairs but have empty intersection. The infinite version holds when all the sets are compact and convex.

Going deeper

For a student

Helly's theorem is the model of a Helly-type theorem: a global property follows from the same property for all small subfamilies. It has many consequences, such as the centerpoint theorem and Jung's theorem on the smallest ball containing a set. It is used in Kirchberger's theorem and has a fractional version and a colourful version. In optimisation it explains why an infeasible system of convex constraints in $\R^d$ has an infeasible subsystem with at most $d + 1$ constraints.