Helly’s Theorem (2/2)

Last week we looked at the concepts of a collection of sets being n-linked or having the finite intersection property. The key theorem was Helly’s theorem which says:

Helly’s Theorem: If a (countable) family of closed convex sets (at least one of which is bounded) in the plane are 3-linked, then they have a point in common, as they have the FIP.

Now I will look at some of the generalizations that Alexander Soifer, author of “The Mathematical Coloring Book”, makes in Chapter 28 of that book. More than pure generalizations they are the combination of Ramsey theory and Helly’s Theorem


First I look at the questions I asked last week:
Question 1:  What does n-linked have to do with the FIP?
Well that is what we are looking at in this post. So more on this later.
Question 2: Find a collection that is n-linked but not n+1 linked.
The collection \{F_i : i \in n\} where F_i =n\setminus\{i\} does this.
Question 3: What does n-linked have to do with the dimension of the real line?
Well, I realized that I made a mistake earlier. For some reason I had convinced myself that \{(n,n+2)\sse \mathbb{R}: n \in \mathbb{Z} \} is two linked. It most certainly is not! For example, (0,2) and (3,4) do not meet. Of course this family does have the property that any subfamily that meets has at most 2 elements. This is almost the antithesis of being 2 linked!

So what did I mean? The real line has the following property: Any open cover can be refined to a “what-Mike-thought-was-2-linked” cover. That is:

Every open cover of \mathbb{R} has a refinement to an open cover in which every real number is contained in at most 2 sets in the refinement.

This fact states that the covering dimension of \mathbb{R} is 2.

Now on to the Ramsey theory!

Remember that the classical Ramsey Theorem says:

Ramsey Theorem: No matter how an enemy colors the pairs of natural numbers, using only finitely many colors, you can find an infinite set where all of the pairs of numbers taken from your set have the same color.

Of course you can replace the word “pair” by “subset of cardinality n”, but this is a bit more confusing to state. Also, pairs of natural numbers have the nice visual interpretation as edges in the graph where the naturals are the vertices.

Here is Soifer’s first attempt at combining Ramsey’s Theorem and Helly’s Theorem:

‘Theorem’ 1: If a countable family of closed convex sets  in the plane are 3-out-of-4-linked with at least one of the sets compact, then there is an infinite subfamily with a point in common.

A collection is 3-out-of-4 linked if out of any 4 sets three have a common point. So here we give up a little on the linkedness property and as a result need to pass to an infinite subfamily. Unfortunately I don’t believe this theorem as stated. Let me give you Soifer’s “proof” which has a very nice technique in it and is easily fixed.

Proof of Theorem 1. Let \{F_n : n \in \mathbb{N}\} be the described family. We color the triples of the naturals using 0,1 as follows: c(i,j,k) = 1 iff  F_i \cap F_j \cap F_k \neq \emptyset . Now we pass to an infinite monochromatic A \subseteq \mathbb{N} . Can it be monochromatic in the bad color 0? No, because then we have 4 sets (infinitely many really) that violate the 3-out-of-4 property. So A must be monochromatic in the good color 1. That means that \{F_i : i \in A\} is 3-linked, so by Helly’s theorem it has a common point.

Done. Or are we? Well, think about the following example:

Example 1: Let F_0 = \{0\} and F_n = [n, +\infty) , for n>0 , which are closed, convex subsets of \mathbb{R} (so also \mathbb{R}^2 if we want). The family has the 3-out-of-4 property, as 3-out-of-4 are not F_0 , but no infinite subfamily has a common point. Uh oh!

So what went wrong? To apply Helly’s Theorem we need that one of our sets is compact. In the proof when we passed to an infinite subset we could have left behind our single lonely compact set. It seems that only demanding that one of the sets be compact was an over-simplification. What Soifer probably intended was that “everything was happening inside of a compact set”. So we can restate Theorem 1 as:

Theorem 2: If a countable family of closed convex sets  in the plane are 3-out-of-4-linked with all but finitely many sets compact, then there is an infinite subfamily with a point in common.

So now the proof really does go through. As Sam Coskey observed, the 3-out-of-4 property could be loosened to the “3-out-of-100 property” or the “3-out-of-a-googol property” and the coloring argument still goes through. Now that I think about it, having the “3-out-of-\infty property” does it too. Since everything is happening inside a compact space I bet this can be framed using limit point compactness now. Hmm…

Now we move on to another (possibly false) strengthening:

‘Theorem’ 3: If a countable family \mathcal{F} of closed convex sets  in the plane are 3-out-of-4-linked with all but finitely many sets compact, then there is a finite coloring of \mathcal{F} so that each color has a point in common.

Theorem 2 said: “we can get one chunk of \mathcal{F} to have a common point” but Theorem 3 says “You know what? We can break up all of \mathcal{F} into chunks that each have a common point!”.

In Soifer’s book he mentions that this theorem (with ‘all but finitely many’ replaced with ‘2’) is a conjecture of Branko Grünbaum, of which a proof does not fit in the margins “look easy”.

I tried the ‘dumb case-by-case’ approach which looked like it was going to work, but was going very slowly. How about this one:

Proof (?) of Theorem 3. By Theorem 2 we can find an infinite set with a common point, say \mathcal{F}_0 =\{F_i : i \in A_0\} . We may also suppose that this family is maximal (with respect to having the most members of \mathcal{F} possible).

Now the remaining sets \{F_i : i \notin A_0\} still have the 3-out-of 4 property. If there are only finitely many sets in this collection we can use up a color on each of them and be done. Otherwise we can find an infinite set A_1 by Theorem 2 such that \mathcal{F}_1 =\{F_i : i \in A_1\} has a common point. We can continue in such a way until we have \mathcal{F}_n for all n \in \mathbb{N} . We would like that \mathcal{F}_n = \emptyset for all but finitely many n\in \mathbb{N} .

Now suppose for the sake of contradiction that there are infinitely many non-empty \mathcal{F}_n . We again define a (0,1)-coloring, this time on the 4-tuples. Let c(i,j,k,l) = 0 iff \exists F_i \in \mathcal{F}_i, \exists F_j \in \mathcal{F}_j, \exists F_k \in \mathcal{F}_k, \exists F_l \in \mathcal{F}_l .

Can we have an infinite monochromatic set in the bad color 0? No because of the 3-out-of-4 property. Can we have an infinite monochromatic set A in the ‘good’ color 1? No because then we would have that \bigcup_{a\in A} \mathcal{F}_a is 4-linked- so also 3-linked- and by Helly’s Theorem it has a common point, which contradicts the maximality of each \mathcal{F}_n .

Thus at most finitely many \mathcal{F}_n are non-empty, so pick a common point of each of the families to witness the theorem.

Remark: I am not so convinced by the line ‘contradicts the maximality’ above. I will have to think about it.

 

 

5 thoughts on “Helly’s Theorem (2/2)”

  2. My first question about the argument for theorem 3: In the =0 case, I don’t see how you are using the 3-out-of-4 property. Since you are coloring 4 sets, it looks like you want to apply a 4-out-of-more property?

    Like

    1. You’re right! My argument for the 0-colour case is no good. It seems that once I have the decomposition into \mathcal{F}_i then I want to do something “diagonal” with the families. Although it doesn’t seem like it will be straightforward; I will probably still need to break it up into cases somewhere.

      Like

  3. Pingback: My first entry! “Helly’s Theorem” | Mike Pawliuk

  4. Hi, I enjoyed your posts. I wanted to offer a citation for a theorem that I think comes close to expressing what you are interested in.

    There is also some popular terminology for some of the things you are discussing.

    For X a set and P(X) its power set, let F \subseteq P(X). (I assume TeX does not work in this box?)

    A transversal of F is a subset X_0 of X such that f \cap X_0 \neq \emptyset for each f \in F. The transversal number of F is the minimal cardinality of a transversal of F.

    This is closely related to your colorability idea. In fact a finite coloring of F such that every color has non-empty intersection gives a finite transversal, and vice versa.

    Also, what you call k out of p linked for integers p,k is called by some authors a (p,k) property. More formally, F has the (p,k) property if for every p elements of F, some k have non-empty intersection.

    I now want to cite a theorem, Theorem 10.5.1 of Lectures on Discrete Geometry by Jiri Matoušek. If you google
    “jiri matasouek, theorem 10.5.1”, google books should let you see the statement of the theorem. I am attempting to include a link here:

    It says something very similar to what you want. In fact, I think you can prove your theorem like this:

    Let F’ = F with the finitely many non-compact sets removed. Apply Matoušek’s theorem to F’, to get a finite coloring (or transversal) as desired. Now throw in new colors for the non-compact sets in F, and done. No?

    This limit question of whether the witnessing intersection points are actually present is closely related to consistency and compactness in mathematical logic. I’m sure Sam can say much more about this; even if the intersection points are “missing” it is consistent that they exist in an elementary extension.
    H.

    Like

Comments are closed.