數學資料庫手記: Helly's selection theorem

Yesterday a friend of mine showed me a very cute and completely elementary fact about convex sets in the plane, and perhaps I could share it here. It's a classical theorem due to Helly. It actually works in arbitrarily high dimensions, but for clarity of exposition let's restrict ourselves to the Euclidean plane $\mathbb{R}^2$ . The theorem is the following:

If we are given a finite number of convex sets in the plane and any 3 of them contain a common point, then there is a point that is common to all these convex sets.

You may wish to draw a picture to convince yourself of this theorem before proceeding.

The proof is based on the following lemma:

Let $\{x_1, x_2, x_3, x_4\}$ be any collection of 4 points in the plane. Then we can partition this collection into a disjoint union $A_1 \cup A_2$ such that the convex hull of $A_1$ intersects the convex hull of $A_2$ .

(If some of you are not familiar with the notions used in the above statement, here is another (more clumsy) way of saying the same thing: Let $x_1, x_2, x_3, x_4$ be any 4 points in the plane. Then one can find a set of labels $I$ , consisting of some of the numbers 1, 2, 3 and 4, such that the following is true: Let $A_1$ be the collection of points $x_i$ whose label $i$ is in $I$ , and let $A_2$ be the collection of the remaining points. Let $H_1$ be the smallest convex set containing all the points in $A_1$ , and $H_2$ be the smallest convex set containing all the points in $A_2$ . Then the two sets $H_1$ and $H_2$ contain a common point.)

The proof of the lemma is based on the following linear algebra argument:

Consider the system of 3 linear equations in 4 unknown real numbers $a_1, a_2, a_3, a_4$ :

$a_1+a_2+a_3+a_4= 0$
$a_1x_1+a_2x_2+a_3x_3+a_4x_4 = 0$

(The second equation is a vector equation in the plane, so it actually represents two linear equations.)

A well-known linear algebra fact is that if you have 3 linear equations in 4 unknowns, you can always find a non-zero solution to the equation. Suppose by abuse of notation $a_1, a_2, a_3, a_4$ is such a solution. By relabelling the points if necessary, we can assume that there is a certain label $k$ such that $a_1, \dots, a_k$ are all positive while $a_{k+1}, \dots, a_4$ are all less than or equal to 0.

Now from the first defining equation of $a_1, a_2, a_3, a_4$ , we have

$a_1 + \dots + a_k = -a_{k+1} - \dots - a_4\right)$ .

Since we assumed $a_1, a_2, a_3, a_4$ is a non-zero solution, the quantity on the left hand side of the above equation must be positive. Let's call it $s$ .

From the second defining equation of $a_1, \dots, a_4$ , we have

$a_1x_1+\dots+a_kx_k= -a_{k+1}x_{k+1}-\dots-a_4x_4$ .

Dividing both sides of the equation by $s$ , we get

$\frac{a_1x_1+\dots+a_kx_k}{s}= \frac{-a_{k+1}x_{k+1}-\dots-a_4x_4}{s}$ .

But the left hand side of this equation is a convex linear combination of the points $x_1, \dots, x_k$ , and hence is in the convex hull of $x_1, \dots, x_k$ ; similarly the right hand side of the equation is in the convex hull of $x_{k+1}, \dots, x_4$ . This completes the proof of the lemma.

Next, we shall prove the theorem by induction on the number $N$ of convex sets involved. The theorem is of course trivial if $N = 3$ . Suppose now the theorem has been proved for a certain $N \geq 3$ . We shall prove the theorem for $N+1$ convex sets. Suppose we are given $N+1$ convex sets $S_1,\dots,S_{N+1}$ in the plane such that any 3 of them contain a common point. For each label $i$ from $1$ to $N+1$ , pick a point $x_i$ such that it belongs to all the $N+1$ convex sets except possibly $S_i$ . This is possible by our induction hypothesis. Now consider $x_1,x_2,x_3,x_4$ . By our lemma, relabeling our indices if necessary, we can assume that there exists a label $k$ , $1 \leq k < 4$ , such that the convex hulls of $x_1,\dots,x_k$ and $x_{k+1},\dots,x_4$ contain a common point. Let's call this common point $x$ . Since $x$ belongs to the convex hull of $x_1,\dots,x_k$ , it belongs to $S_j$ for all $j>k$ ; here we make use of the assumptions that the sets $S_j$ are convex. Similarly, since $x$ belongs to the convex hull of $x_{k+1},\dots,x_4$ , it belongs to $S_j$ for all $j\leqk$ . Hence $x$ is contained in all the $N+1$ sets $S_1,\dots,S_{N+1}$ , and this completes the proof.

The theorem actually holds in $\mathbb{R}^n$ for any $n$ . One just needs to replace 3 by $n+1$ in the statement of the theorem. The proof and the lemma works equally well in high dimensions; one just needs to replace every 4 by $n+2$ there.

One interesting question came out of my discussion with my friend though. Suppose now we are in a finite dimensional vector space over a finite field (instead of $\mathbb{R}$ ). It of course doesn't make sense to talk about convexity there. However, we may replace "convex sets" by "affine linear subspaces" (translates of vector subspaces) and ask the following question:

Let $F$ be a finite field. Suppose we are given a finite number of affine linear subspaces of $F^n$ where any $n+1$ of them intersect. Must the intersection of all the given affine linear subspaces be non-empty?

I am not sure how interesting or difficult this problem is; perhaps there is a really easy solution to this problem, and we haven't put much effort into thinking about it anyway. But if some of you come up with any idea on how to approach or solve the problem, I'd be interested to know.

數學資料庫手記

2008年4月21日星期一

Helly's selection theorem

沒有留言:

著作人

stat

網誌存檔