14
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Oct 19, 2011 at 18:06
  • $\begingroup$ 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? $\endgroup$
    – domotorp
    Oct 31, 2011 at 8:29
  • $\begingroup$ Hi Domotorp, i dont see the precise connection. $\endgroup$
    – Gil Kalai
    Oct 31, 2011 at 12:14
  • $\begingroup$ 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... $\endgroup$
    – domotorp
    Oct 31, 2011 at 19:27
  • $\begingroup$ 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! $\endgroup$
    – Gil Kalai
    Oct 31, 2011 at 19:39

3 Answers 3

4
$\begingroup$

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 [1] and later proved by Amenta in [2].

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

[1] 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.

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

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

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.

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

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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? $\endgroup$
    – Gil Kalai
    Oct 30, 2011 at 15:34
  • $\begingroup$ Yes, you are right, I have only considered intersections of three sets. $\endgroup$
    – domotorp
    Oct 30, 2011 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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