Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Here is a curious conjectural extension of Helly's theorem.

It may follow (if true) from a useful theorem of the kind asked in this MO question:

Conjecture: Let ${\cal F}=P_1,P_2,\dots,P_m$ be a family all whose members are disjoint union of two convex sets in $R^d$. Suppose also that

(1) $m \ge d+2$

(2) Every intersection of $i$ members of $\cal F$, $i < m$ is also the disjoint union of two NONEMPTY compact convex sets.

Then the intersections of all members of $\cal F$ is not empty.

Remark: Micha A. Perles showed (in the 70s) that even when $d=2$ you cannot replace "two" by "48".

share|improve this question
    
A friend of mine did her master thesis on Helly type theorems: www2.math.su.se/gemensamt/grund/exjobb/matte/2008/rep2/… You might find something there. –  Per Alexandersson Oct 19 '11 at 18:06
    
So if I see well, this question is a special case of the characterization of the f-vectors of d-representable colored simplicial complexes which has been open for a long time (but probably the known results are enough to give a proof for d=2). Could you recommend a survey of these results? –  domotorp Oct 31 '11 at 8:29
    
Hi Domotorp, i dont see the precise connection. –  Gil Kalai Oct 31 '11 at 12:14
    
E.g. if d=2, then you basically have 8 sets, colored with four colors, two in each class, but we don't even have to care about the colors. Take the f-vector of their nerve complex, i.e. where f_i denotes how many i+1 of them intersect. Then your condition demands that f_3 is 0, f_2 is 8 (four triples with two intersections each) and f_1 is 12 (six pairs with two intersections each), plus you demand a little more because of the colors. I think you know Eckhoff's conditions better than me... –  domotorp Oct 31 '11 at 19:27
    
Dear Domotorp, you are right. Indeed these questions can be regarded as questions about multicolored representable complexes although they are not directly related to questions about f-vectors. Interesting! –  Gil Kalai Oct 31 '11 at 19:39
add comment

3 Answers 3

This answer provides a nice background to the question.

I can say that a theorem similar to the one in the OP is certainly true. The following was conjectured by Grunbaum and Motzkin in "On components in some families of sets" and later proved by Amenta in "Helly-type theorems and Generalized Linear Programming".

Theorem Let $\mathcal C$ be a family of sets in $\mathbb R^d$ such that the intersection of any non-empty finite subfamily of $\mathcal C$ is the disjoint union of at most $k$ closed convex sets. Then the intersection of all sets in $\mathcal C$ is non-empty if and only if the intersection of any $k(d+1)$ elements of $\mathcal C$ is non-empty.

In particular this implies that the conjecture in the OP is true when $m\geq 2d+3$. I believe there are counter examples for $m\le k(d+1)$, showing it is best possible.

share|improve this answer
1  
Yes. the point is what happens when you replace "at most k" with "exactly k" for k=2 (and maybe also k=3) –  Gil Kalai Oct 28 '11 at 14:34
add comment

This answer refers to an earlier, slightly inaccurate, version of the problem. (GK)

I think your conditions might be insufficient, even if in (2) you require the intersection to be a convex set. If d=1, first take three intervals, A, B and C. Your sets can be $A\cup B$, $B\cup C$ and $A\cup C$. The intersection of any two will be an interval.

A similar example if d=2 is to take four squares, $A=[0,1]\times [0,1]$, $B=[0,1]\times [1,3]$, $C=[1,3]\times [0,1]$, $D=[1,3]\times [1,3]$. Now take the four sets to be $conv(A,B)\cup C$, $conv(B,C)\cup D$, $conv(C,D)\cup A$, $conv(D,A)\cup B$. The intersection of any three sets will be a square.

share|improve this answer
    
Dear Domotorp, I forgot to say that the intersection should be the disjoin union of two non empty convex sets. –  Gil Kalai Oct 28 '11 at 4:47
1  
Well, convex sets are usually easy to split into two, non-empty convex sets... Maybe you want that their closures do not intersect or their distance is non-zero or something like that. –  domotorp Oct 28 '11 at 5:19
2  
compact, the point here and in the previous question that all non empty intersection are of the same homotopic type. –  Gil Kalai Oct 28 '11 at 14:31
add comment

This answer shows that you cannot strengthen the conditions of the questions and demand condition (2) only for $m-1$ sets.

Answer for new version IF we only consider the intersection of m-1 sets (as construction fails otherwise, as pointed out by Gil in the comment): Now it is not hard to prove that the statement is true for d=1 but there is a counterexample for d=2. Take a circle and divide its perimeter into six equal parts, A, B, .., F such that e.g. A, B and C are on the top. Now take a point somewhere high, P, and another somewhere low, Q. Our four sets will be the following: conv(A,P) $\cup$ conv(D,Q), conv(B,P) $\cup$ conv(E,Q), conv(C,P) $\cup$ conv(F,Q) and finally the last set is the disc. Now the intersection of the first three will be around P and Q, while the intersection of the fourth with any two other sets will be around two disjoint arcs of the perimeter.

share|improve this answer
2  
Dear Domotorp, I was first worried about the intersection of the first third and the disk. But this looks ok. Now I am a bit worried about the intersection of the first and third. Doesnt it contain something around P something around Q and also something around the intersection of A and F and something around the intersection of C and D? –  Gil Kalai Oct 30 '11 at 15:34
    
Yes, you are right, I have only considered intersections of three sets. –  domotorp Oct 30 '11 at 16:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.