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

  • $\begingroup$ Crossposted to cstheory.stackexchange.com by "Adam" at cstheory.stackexchange.com/questions/17947/… $\endgroup$
    – Boris Bukh
    Commented Jun 9, 2013 at 12:40
  • $\begingroup$ see also mathoverflow.net/questions/132335/… $\endgroup$ Commented Jun 9, 2013 at 20:06
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Jun 9, 2013 at 21:47
  • $\begingroup$ See math.stackexchange.com/questions/414971/… $\endgroup$ Commented Jun 10, 2013 at 9:03

1 Answer 1


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.

  • $\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
    Commented 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$ Commented 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.