A curious generalization of Helly's theorem - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T22:28:08Z http://mathoverflow.net/feeds/question/78595 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/78595/a-curious-generalization-of-hellys-theorem A curious generalization of Helly's theorem Gil Kalai 2011-10-19T17:15:27Z 2011-10-30T22:50:00Z <p>Here is a curious conjectural extension of Helly's theorem.</p> <p>It may follow (if true) from a useful theorem of the kind asked in <a href="http://mathoverflow.net/questions/78585/a-desirable-extension-of-the-nerve-theorem" rel="nofollow">this MO question</a>:</p> <blockquote> <p><strong>Conjecture:</strong> 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 </p> <p>(1) $m \ge d+2$</p> <p>(2) Every intersection of $i$ members of $\cal F$, $i &lt; m$ is also the disjoint union of two NONEMPTY <em>compact</em> convex sets.</p> <p>Then the intersections of all members of $\cal F$ is not empty.</p> </blockquote> <p>Remark: Micha A. Perles showed (in the 70s) that even when $d=2$ you cannot replace "two" by "48".</p> http://mathoverflow.net/questions/78595/a-curious-generalization-of-hellys-theorem/79241#79241 Answer by domotorp for A curious generalization of Helly's theorem domotorp 2011-10-27T06:51:36Z 2011-10-30T22:46:07Z <p><strong>This answer refers to an earlier, slightly inaccurate, version of the problem. (GK)</strong></p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/78595/a-curious-generalization-of-hellys-theorem/79334#79334 Answer by Gjergji Zaimi for A curious generalization of Helly's theorem Gjergji Zaimi 2011-10-27T23:54:37Z 2011-10-30T22:50:00Z <p><strong>This answer provides a nice background to the question.</strong></p> <p>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 <a href="http://www.jstor.org/pss/2034254" rel="nofollow">"On components in some families of sets"</a> and later proved by Amenta in <a href="http://www.springerlink.com/content/bx1262r145x60505/" rel="nofollow">"Helly-type theorems and Generalized Linear Programming"</a>.</p> <blockquote> <p><b>Theorem</b> 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.</p> </blockquote> <p>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.</p> http://mathoverflow.net/questions/78595/a-curious-generalization-of-hellys-theorem/79519#79519 Answer by domotorp for A curious generalization of Helly's theorem domotorp 2011-10-30T13:02:10Z 2011-10-30T22:48:05Z <p><strong>This answer shows that you cannot strengthen the conditions of the questions and demand condition (2) only for $m-1$ sets.</strong></p> <p>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.</p>