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

Let $f: \mathbb{R}^d \times \mathbb{R}^n \rightarrow \mathbb{R}$ be such that for all $x \in \mathbb{R}^d$, $y \mapsto f(x,y)$ is convex, and for all $y \in \mathbb{R}^n$, $x \mapsto f(x,y)$ is convex. Suppose $n \leq d$.

Define the sets $$ X_i := \{ x \in \mathbb{R}^d \mid f( x, y_i ) \leq 0 \}, \ \forall i = 1, 2, ..., N,$$ where $y_1, ..., y_N \in \mathbb{R}^n$ are given vectors.

I am wondering if Helly's Theorem holds true with Helly's number $h$ depending on $n$, not on $d$.

share|improve this question
    
Crossposted to cstheory.stackexchange.com by "Adam" at cstheory.stackexchange.com/questions/17947/… –  Boris Bukh Jun 9 '13 at 12:40
    
see also mathoverflow.net/questions/132335/… –  Yoav Kallus Jun 9 '13 at 20:06
    
It appears that you have crossposted this question simultaneously from cstheory. While we don't mind a question being reposted, cstheory policy (meta.cstheory.stackexchange.com/a/231) prohibits simultaneous crossposting as it duplicates effort and fractures discussion. Crossposting is only permitted after sufficient time has passed and you have not obtained your desired answer elsewhere. When crossposting please summarize the relevant discussions from other sites in your question and link to the copies in both directions. –  Kaveh Jun 9 '13 at 21:47
    
add comment

1 Answer

No, even if you assume that $f$ is convex on $\mathbb R^{d+n}$. Take $n=2$ and let $y_1,\dots,y_{d+1}\in\mathbb R^2$ be vertices of a convex polygon. Let $X_1,\dots,X_{d+1}\subset\mathbb R^n$ be your favorite counter-example to Helly's theorem for $h=d+1$. (For example, the $(d-1)$-faces of a unit regular simplex.) Let $f_i:\mathbb R^n\to\mathbb R$ be the distance function of $X_i$.

The union of these functions can be regarded as a function on $\mathbb R^d\times\{y_i\}$. It admits a convex extension on $\mathbb R^d\times\mathbb R^2$, i.e., there exists a convex function $f:\mathbb R^d\times\mathbb R^2\to\mathbb R$ such that $f(x,y_i)=f_i$ for all $i$. This $f$ is a desired counter-example.

To construct such $f$, it suffices to find, for each $i$ and every $p\in\mathbb R^d$, an affine function $f_{i,p}:\mathbb R^d\times\mathbb R^2$ supporting the partially defined $f$ at the point $(p,y_i)$, i.e. $f_{i,p}(p,y_i)=f_i(p)$ and $f_{i,p}(x,y_j)\le f_j(x)$ for all $x\in\mathbb R^d$ and $j\le d+1$. Then the desired $f$ can be defined as the supremum of all $f_{i,p}$ over all $i$ and all $p\in\mathbb R^d$. To guaratee that the supremum is finite, just make sure that the Lipschitz constants of $f_{i,p}$ are uniformly bounded.

To define $f_{i,p}$, let $f_{i,p}(x,y)=a_{i,p}(x)+b_i(y)$ where $a_{i,p}:\mathbb R^d\to\mathbb R$ is a Lipschitz-1 affine function supporting $f_i$ at $p$, and $b_i:\mathbb R^2\to\mathbb R$ is an affine function such that $b_i(y_i)=0$ and $b_i(y_j)$ is sufficiently negative for $j\ne i$. Such $b_i$ exists because $y_i$ is separated from the convex hull of $y_j$'s.

share|improve this answer
    
I am not clear with the notation. What does $f_{i,x}: \mathbb{R}^d \times \mathbb{R}^2$ mean? First, do you mean $f_{i,x}: \mathbb{R}^d \times \mathbb{R}^2 \rightarrow \mathbb{R}$? Second, is $x$ fixed or not? I mean that if $x$ is fixed, then it should be $f_{i,x}: \mathbb{R}^2 \rightarrow \mathbb{R}$. While if $x$ is not fixed, it should be $f_i: \mathbb{R}^d \times \mathbb{R}^2 \rightarrow \mathbb{R}$. Please explain, thanks. –  Frank Jun 10 '13 at 7:35
    
1. Yes, $\to\mathbb R$ was missing, fixed that. 2. I renamed $x$ to $p$ and $x'$ to $x$. Hope now it is more clear what is fixed in each place. –  Sergei Ivanov Jun 11 '13 at 19:27
add comment

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.