Helly's number from biconvex functions

Question

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

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.