1

In Lectures on Discrete Geometry, Matousek writes (p.11) (excerpt here):

It is very tempting and quite usual to formulate Helly's theorem as follows: "If every $d+1$ among $n$ convex sets in $\mathbb{R}^d$ intersect, then all the sets intersect." But, strictly speaking, this is false, for a trivial reason: For $d \geq 2$ , the assumption as stated here is met by $n = 2$ disjoint convex sets.

I don't understand what is wrong, and the given counterexample?

Michael Grant
  • 19,450
Greg82
  • 261

1 Answers1

1

Counterexample: $n=d=2$ and you have a collection of $n=2$ disjoint convex subsets of the plane. Then the condition "every $d+1$ intersect" is trivially (vacuously) satisfied. Yet clearly not all the sets in our collection intersect.

In the correct statement of the theorem we assume $n>d$, so that the condition about $d+1$ sets intersecting is nontrivial, i.e., it actually means something.

Forever Mozart
  • 9,294
  • But how do you take $d+1$ sets among $n = d$ sets? (Without taking the same at least two times?) – Greg82 Jun 28 '14 at 23:45
  • Exactly, you can't pick 3 sets, so it holds vacuously that any 3 intersect. – Forever Mozart Jun 28 '14 at 23:47
  • It must be assumed that you cannot pick the same set twice. Let's rephrase the theorem a little so that this is clear: Suppose $X$ is a collection of $n$ convex subsets of $\mathbb R ^d$. If every subcollection of $X$ of size $d+1$ has nonempty intersection, then the collection $X$ has nonempty intersection. This eliminates the potential for redundancy in our subcollection. – Forever Mozart Jun 28 '14 at 23:56