Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)?


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.

share|improve this question
    

1 Answer 1

up vote 5 down vote accepted

$\infty$.

Let $n=m=1$. We will form our sets with a braid-like construction. Each set will be a curve, and the curves will move back and forth in a fixed strip such that any $h+1$ of them intersect but all $N$ never do. We then stretch the strip out until the curves never move at an angle of more than $\pi/4$ from the length of the strip, and rotate the strip so that its length is along the line $x=y$. Thus, along each curve, $x$ and $y$ are both monotonically increasing, so $S_x$ and $S_y$ are each just a single point, hence each curve is biconvex.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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