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

Improve this question
$\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$
    – Per Alexandersson
    Commented 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
    Commented Oct 31, 2011 at 8:29
  • $\begingroup$ Hi Domotorp, i dont see the precise connection. $\endgroup$
    – Gil Kalai
    Commented 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
    Commented 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
    Commented Oct 31, 2011 at 19:39

3 Answers 3

Reset to default
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.

Improve this answer
$\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
    Commented 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.

Improve this answer
$\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
    Commented 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
    Commented 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
    Commented 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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .