A curious generalization of Helly's theorem - MathOverflow

A curious generalization of Helly's theorem

2011-10-19T17:15:27Z

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

Answer by domotorp for A curious generalization of Helly's theorem

2011-10-27T06:51:36Z

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.

Answer by Gjergji Zaimi for A curious generalization of Helly's theorem

2011-10-27T23:54:37Z

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.

Answer by domotorp for A curious generalization of Helly's theorem

2011-10-30T13:02:10Z

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.