Combinatorics • Topic 34

Convex Sets

Convexity is a geometric property with deep combinatorial implications (Helly's Theorem).

Definition

Definition (Convex Set)

A set

S \subseteq R^{n}

is convex if for any two points

x, y \in S

, the entire line segment

x y

lies in

S

Helly's Theorem

Theorem (Helly's Theorem)

Let

F

be a finite family of convex sets in

R^{d}

. If every

d + 1

sets in

F

have a non-empty intersection, then the intersection of all sets in

F

is non-empty.

In 1D (Line segments): If every pair overlaps, they all share a common point.
In 2D: If every 3 sets overlap, they all share a point.

Practice Problems

Exercise (Problem 1)

Prove that the intersection of two convex sets is convex.

Exercise (Problem 2)

(Radon's Theorem) Prove that any set of

d + 2

points in

R^{d}

can be partitioned into two sets whose convex hulls intersect.

Exercise (Problem 3)

Use Helly's Theorem to prove that if a set of points can be covered by a circle of radius 1 pairwise, the whole set can be covered by a circle of radius 1 (wait, radius is

2

? Check Jung's Theorem).