5. Applications of Helly’s Theorem in Combinatorial Geometry 21
(Colored Helly’s Theorem). Let A1,... , Ad+1 be non-empty finite families
of convex sets in
Suppose that for each choice Ai ∈ Ai, i = 1, . . . , d + 1, we
have A1 ∩ . . . ∩ Ad+1 = ∅. Prove that for some i the intersection of the sets in the
family Ai is non-empty.
Hint: This can be deduced from Problem 2 of Section 2.3; see also [Bar82] and
Chapter 8 of [Mat02].
5. Applications of Helly’s Theorem in Combinatorial
In the next two sections, we discuss various applications and appearances of Helly’s
Theorem. The proofs are almost immediate once we recognize the relationship
of the problem to Helly’s Theorem but may be quite non-trivial if we miss that
(5.1) Separating points by a hyperplane. Suppose that there is a finite set R
of red points in Rd and a finite set B of blue points in Rd. A hyperplane H ⊂ Rd is
the set described by a linear equation H = x ∈ Rd : c, x = α , where c = 0 is
a non-zero vector and α is a number. We say that the hyperplane H ⊂ Rd strictly
separates red and blue points if c, x α for all x ∈ R and c, x α for all x ∈ B.
The following result, called Kirchberger’s Theorem, was proved by P. Kirchberger
in 1903, that is, before Helly’s Theorem.
Proposition. Suppose that for any set S ⊂
of d+2 or fewer points there exists
a hyperplane which strictly separates the sets S ∩ R and S ∩ B of red, resp. blue,
points in S. Then there exists a hyperplane which strictly separates the sets R and
Proof. A hyperplane H = x ∈ Rd : c, x = α , where c = (γ1, . . . , γd) ∈ Rd,
can be encoded by a point (c, α) = (γ1, . . . , γd,α) ∈ Rd+1. For every point r ∈ R
we define a set Ar ⊂
Ar = (c, α) ∈
: c, r α
and for every point b ∈ B we define a set Ab ⊂ Rd+1:
Ab = (c, α) ∈
: c, b α .
It is clear that Ab and Ar are convex sets in Rd+1. Therefore, by Helly’s Theorem
is non-empty, provided for any subset S ⊂ R ∪ B of at most d + 2 points the