# A curious generalization of Helly's theorem

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".

• 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. Oct 19, 2011 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? Oct 31, 2011 at 8:29
• Hi Domotorp, i dont see the precise connection. Oct 31, 2011 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... Oct 31, 2011 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! Oct 31, 2011 at 19:39

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 Grünbaum and Motzkin in  and later proved by Amenta in .

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.

References

 Branko Grünbaum, Theodore S. Motzkin, "On components in some families of sets" Proceedings of the American Mathematical Society, Vol. 12, No. 4, 607-613, doi:10.2307/2034254, MR0159262, Zbl 0106.01001.

 Nina Amenta, "Helly-type theorems and Generalized Linear Programming" "Discrete & Computational Geometry 12, 241–261 (1994), EuDML: 131330, MR1298910, Zbl 0819.90056.

• Yes. the point is what happens when you replace "at most k" with "exactly k" for k=2 (and maybe also k=3) Oct 28, 2011 at 14:34

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.

• Dear Domotorp, I forgot to say that the intersection should be the disjoin union of two non empty convex sets. Oct 28, 2011 at 4:47
• 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. Oct 28, 2011 at 5:19
• compact, the point here and in the previous question that all non empty intersection are of the same homotopic type. Oct 28, 2011 at 14:31

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.

• 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? Oct 30, 2011 at 15:34
• Yes, you are right, I have only considered intersections of three sets. Oct 30, 2011 at 16:53