1
$\begingroup$

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

$\endgroup$
4

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – user693
    Jun 10, 2013 at 7:35
  • $\begingroup$ 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. $\endgroup$ Jun 11, 2013 at 19:27

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.