Helly's Theorem for Biconvex Sets

267 Views Asked by At

Helly's Theorem states the following. Suppose that $X_1,X_2,...,X_N$ are convex sets in $\mathbb{R}^d$, such that for any index-set $I$ with $|I| \leq h(d) := d+1$, we have $\bigcap_{i \in I} X_i \neq \varnothing$. Then $\bigcap_{i=1}^N X_i \neq \varnothing$.

If instead $X_1,X_2,...,X_N$ are biconvex sets in $\mathbb{R}^d$, what is "Helly's number" $h(d)$ (or an upper bound of it)?


Possible hint. Let $\mathcal{X} = \{X_1, ..., X_N\}$ such that the intersection of any its subfamily of size at most $k$ can be expressed as a disjoint union of $k$ closed convex sets. Then $h \leq k(d + 1)$. What is $k$ for biconvex sets?

However, I found that the intersection of $2$ biconvex sets may be the union of an unbounded number of convex sets. So probably this hint is not useful.


Comment. A set $S \subseteq \mathbb{R}^{n} \times \mathbb{R}^m = \mathbb{R}^d$ is biconvex if for all $y \in \mathbb{R}^m$ the set $S_y := \{ x \in \mathbb{R}^n \mid (x,y) \in S \}$ is convex, and for all $x \in \mathbb{R}^n$ the set $S_x := \{ y \in \mathbb{R}^m \mid (x,y) \in S \}$ is convex as well.

1

There are 1 best solutions below

0
On BEST ANSWER

There is no upper bound. Take $n$ vertical strands in the plane and braid them by having the rightmost strand cross over all other strands to reach the left side. Do this until you reach the original configuration. Now, between each of this twists, pinch the rightmost $(n-1)$ strands into a single point. Then tilt this whole configuration to the right 45 degrees.

The 'pinchings' ensure that each subset of size $(n-1)$ had non-trivial intersection, but the intersection of all the sets is empty. The braid can be drawn in such a way that, when tilted, it is biconvex (since all we need is for the strands to never have slope 0 or infinity).

Sorry my drawing skills are poor! I couldn't depict this well.