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 where 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 is two linked. It most certainly is not! For example, and 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 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 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 be the described family. We color the triples of the naturals using 0,1 as follows:
iff . Now we pass to an infinite monochromatic . 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 must be monochromatic in the good color 1. That means that 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 and , for , which are closed, convex subsets of (so also if we want). The family has the 3-out-of-4 property, as 3-out-of-4 are not , 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- 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 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 so that each color has a point in common.
Theorem 2 said: “we can get one chunk of to have a common point” but Theorem 3 says “You know what? We can break up all of 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 . We may also suppose that this family is maximal (with respect to having the most members of possible).
Now the remaining sets 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 by Theorem 2 such that has a common point. We can continue in such a way until we have for all . We would like that for all but finitely many .
Now suppose for the sake of contradiction that there are infinitely many non-empty . We again define a (0,1)-coloring, this time on the 4-tuples. Let iff .
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 is 4-linked- so also 3-linked- and by Helly’s Theorem it has a common point, which contradicts the maximality of each .
Thus at most finitely many 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.