Helly, Radon, and Tverberg: finite intersection principles
Connect affine dependence, small intersection certificates, and partitions with intersecting convex hulls.
On this page
The question for today
What you’ll understand
- Construct a Radon partition from a nontrivial affine dependence.
- State finite Helly’s theorem with the correct subfamily size.
- Distinguish affine Tverberg’s theorem from its topological variants.
Convexity can turn a large geometric question into a small certificate. Helly’s theorem says that failure of a finite convex feasibility problem is witnessed by at most d + 1 constraints. Radon’s theorem finds two intersecting convex hulls from only d + 2 points, and Tverberg extends the partition idea to many parts. These are related statements with different inputs and conclusions. Understanding the distinction prevents “many local intersections” from being mistaken for the exact hypothesis that guarantees a global one.
Affine dependence creates a Radon partition
Take d + 2 points in real d-dimensional space and append a coordinate one to each. These d + 2 vectors live in a space of dimension d + 1, so they have a nontrivial linear dependence. The coefficients sum to zero and their point-weighted sum vanishes. Some coefficients are positive and some negative; separating the signs and normalizing their common total yields equal convex combinations on two disjoint index sets.
Any zero coefficients can be assigned to either part without changing the common point. This proves Radon’s theorem even when the original points are degenerate or repeated as an indexed list. The partition need not be unique. The proof uses affine dependence, not the fact that all points are vertices of a polytope; points inside another point’s convex hull are allowed and sometimes make the partition particularly transparent.
A small infeasibility witness is enough
Finite Helly’s theorem states that a finite family of convex subsets of real d-space has a common point if every subfamily of at most d + 1 members has a common point. Using “at most” also handles families containing fewer than d + 1 sets. Convex sets need not be compact for this finite statement. An infinite-family version requires additional hypotheses, such as compactness conditions; one cannot simply delete the word finite.
To see the mechanism, assume a minimal infeasible subfamily has more than d + 1 sets. For every omitted set choose a point lying in all the others. Choose d + 2 of these points and apply Radon. For any particular set, at most one chosen point can fail membership; one of the two Radon parts therefore lies wholly inside that set. Convexity places the common Radon point inside every set, contradicting infeasibility.
Many-part partitions and a topological boundary
Affine Tverberg’s theorem says that for any integer r at least two, every indexed collection of (r − 1)(d + 1) + 1 points in real d-space admits a partition into r nonempty parts whose convex hulls share a point. The case r = 2 is Radon. The general existence theorem is stated here rather than proved; our examples verify individual partitions, which is different from proving a partition always exists.
A topological version replaces the affine map from the simplex of dimension (r − 1)(d + 1) into real d-space by an arbitrary continuous map with that same domain and target, and asks for intersecting images of r pairwise disjoint faces. That stronger statement holds for prime-power r, but unrestricted extensions to all r fail in sufficiently high dimensions when r is not a prime power. This does not weaken the affine theorem, which holds for every r. The kind of map is a substantive hypothesis: continuous maps need not preserve convex combinations, so Radon’s linear-algebra argument no longer applies.
Work it through
A three-part partition on the real line
Partition the five indexed points 0, 1, 2, 3, 4 in the real line into three nonempty parts whose convex hulls intersect.
Check the affine threshold with d = 1 and r = 3: (3 − 1)(1 + 1) + 1 = 5, so Tverberg’s theorem applies to these five points.
Choose the disjoint parts {0, 4}, {1, 3}, and {2}. Their convex hulls are the intervals [0, 4], [1, 3], and the singleton {2}.
The point 2 lies in all three hulls; it is the midpoint of each two-point part and is already the point in the singleton. The parts together use every original point exactly once.
This is a valid Tverberg partition with common point 2. The verified example illustrates, rather than proves, the general theorem.
The living notebook
Explore the model
Interactive lab · matrix
Affine maps preserve a common convex combination
Pause and Reset, then set diagonal scale a = 1.5 and shear b = 0.5. Predict that the opposite corner pairs of the transformed unit square both have midpoint (1, 0.5). Check the four final corner coordinates after playing, computing the midpoints by hand. The readouts describe the selected final matrix. This is one Radon-partition example; the instrument does not search partitions or display arbitrary convex families.
- Area scale · det A
- 1.4
- Singular values · σmax, σmin
- 1.597, 0.876
- Condition number · κ₂(A)
- 1.823
The selected matrix is A = [[a,b],[0,1]]. Playback interpolates geometry between the identity and A; readouts always describe A. Its determinant is a and its singular values come from AᵀA. Positive a makes every supported matrix invertible. This two-dimensional family is not a general eigensolver or a learned network. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forAn affine transformation preserves the coefficients witnessing an intersection of convex hulls.
Pause & reason
Check your understanding
Your turn
Try it yourself
Give three closed halfplanes in the plane that intersect pairwise but have no common point. Explain why this is consistent with Helly’s theorem.
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Try two lower bounds on x and y and one incompatible upper bound on their sum.
Compare with the solution
Take x ≥ 1, y ≥ 1, and x + y ≤ 1. The first two meet at (1, 1); the first and third meet at (1, 0); the second and third meet at (0, 1). Yet the first two force x + y ≥ 2, contradicting the third, so the triple intersection is empty. Helly in dimension two requires all subfamilies of at most three to intersect, and this family violates precisely the three-set condition. It therefore supplies a sharp warning against replacing that condition by pairwise intersection.
Keep the idea
Take it with you
- Radon follows by splitting an affine dependence into positive and negative coefficients.
- Finite Helly gives an infeasibility certificate of size at most d + 1.
- Affine Tverberg holds for every r; topological variants have different hypotheses and limitations.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.