Helly’s Theorem – Basic Concepts
(Combinatorics / Discrete Geometry)
1. Simple Explanation
Helly’s theorem tells us when a whole collection of convex shapes in space must have a common point.
Think of a bunch of overlapping discs or polygons: if every small group of them overlaps, then all of them overlap together.
Intuitive picture – In 2‑D, imagine several convex “clouds” of ink on a sheet.
If any three of them share a point, the entire family must share a common point.
2. Key Definitions
| Concept | Meaning | Example |
|---|---|---|
| Convex set | A set (C\subseteq \mathbb{R}^d) such that for any two points (x,y\in C), the whole line segment ([x,y]) lies in (C). | A triangle, a circle, a square, a half‑plane. |
| Helly number | The smallest integer (h) such that for any family of convex sets in (\mathbb{R}^d), if every sub‑family of size (h) has a point in common, then the whole family has a common point. | In (\mathbb{R}^d) the Helly number is (d+1). |
| Family of convex sets | A collection (\mathcal{F}={C_1,C_2,\dots,C_n}) where each (C_i) is convex. | ({,\text{half‑planes},}), ({,\text{discs},}), ({,\text{rectangles},}). |
| Intersection of a family | (\bigcap_{i=1}^n C_i = {x\in\mathbb{R}^d : x\in C_i \text{ for all } i}). | The point where all discs overlap. |
3. Formal Statement
Helly’s Theorem (Euclidean version).
Let (\mathcal{F}={C_1,\dots,C_n}) be a finite family of convex sets in (\mathbb{R}^d).
If every sub‑family of size (d+1) has a non‑empty intersection, i.e.
[ \forall, I\subseteq {1,\dots,n},\ |I|=d+1 \quad\Longrightarrow\quad \bigcap_{i\in I} C_i \neq \varnothing, ]
then the whole family has a non‑empty intersection:
[ \bigcap_{i=1}^n C_i \neq \varnothing. ]
Consequences
- In the plane ((d=2)) the Helly number is (3).
- In (\mathbb{R}^3) the Helly number is (4), etc.
- The theorem is sharp: there are families where all ((d+1))-tuples intersect but the whole family does not intersect when one set is removed.
4. Quick Proof Sketch (for (d=2))
- Choose a point (p) in the intersection of any two sets (possible because all pairs intersect by assumption).
- Consider the lines through (p) that are tangent to each convex set.
- The intersection of all convex sets is the intersection of the corresponding half‑planes defined by these tangents.
- By the planar version of Helly’s theorem, if every triple of half‑planes contains (p), then all half‑planes contain (p).
- Hence (p) belongs to all convex sets.
(Full proofs use induction on (d) and separation theorems; the sketch above captures the idea.)
5. Worked Example
Problem.
Let (C_1, C_2, C_3, C_4) be convex subsets of (\mathbb{R}^2).
Suppose every three of them intersect in at least one point.
Show that all four intersect.
Solution.
- By Helly’s theorem in the plane ((d=2), Helly number (3)), the condition “every triple intersects” is exactly the hypothesis.
- Therefore, the intersection of all four sets is non‑empty.
- Explicitly, pick any three sets, say (C_1, C_2, C_3), and let (p) be a point in their intersection.
- Because (p\in C_1\cap C_2\cap C_3), and by hypothesis (C_4) intersects each pair, we can use the planar Helly argument to see that (p) must also lie in (C_4).
- Hence (p \in C_1\cap C_2\cap C_3\cap C_4).
Thus all four convex sets share a common point.
6. Applications in Combinatorics
| Area | How Helly helps |
|---|---|
| Covering / hitting set | If each small subfamily covers a point, the whole family must cover that point. |
| Intersection graphs | Helly property can be used to test feasibility of simultaneous constraints. |
| Geometric transversal theory | Guarantees existence of transversal lines or points for families of convex sets. |
| Discrete optimization | Helly’s theorem underlies algorithms for feasibility of linear programs and integer programming with convex constraints. |