1

Let $A,C_1,\dots,C_m$ be convex sets in $\mathbb{R}^n$ (Let's say $m \gg n$). Suppose that for any triple $(C_i,C_j,C_k)$ we always have a translation of $A$ such that $A\cap C_i\ne \emptyset, A\cap C_j\ne \emptyset$ and $A\cap C_k\ne \emptyset$. Prove that there exists a translation of $A$ that has a common point with each $C_1,C_2,\dots,C_m$.


I think this is just a direct consequence of the Helly theorem by letting $A_i:=A+C_i$ but it is not going any further.

  • This is false. It would only be true for the convex sets being in $\mathbb{R}^2$, so that Helly's theorem can be applied. For a (probability 1) counter-example in $\mathbb{R}^3$, take $A = {(0,0,0)}$ and take $C_1, C_2, C_3, C_4$ as randomly and independently chosen 2-d planes in $\mathbb{R}^3$ (with a suitable continuous distribution of parameters so that perfect alignment has prob 0). Take any three of the planes: With prob 1 they intersect in a single point, and with prob 1 the 4th plane does not touch that point. – Michael Jan 18 '22 at 05:32

1 Answers1

2

This summarizes my comment: This is false. It would be true if the convex sets $A, C_1, \ldots, C_m$ were in $\mathbb{R}^2$ so that Helly's theorem could be applied to sets $D_i = C_i-A$.

For a counter-example in $\mathbb{R}^3$: Define $A=\{(0,0,0)\}$. It suffices to find an example of 4 distinct planes in $\mathbb{R}^3$ such that every three of them intersect, but the 4 planes share no common point of intersection. Just independently generate the planes as follows: $$ C_i = \{x \in \mathbb{R}^3 : Y_i^{\top}x = B_i\}$$ where $Y_i$ is a random vector in $\mathbb{R}^3$ with i.i.d. entries $N(0,1)$, and $B_i$ is a independent random variable with $N(0,1)$ distribution.

Now grab any three of the planes. There is a point of intersection of all three if the equation $Yx = B$ is satisfied, where $Y$ is a random $3 \times 3$ matrix with rows equal to $Y_i^{\top}$ for indices $i$ corresponding to which three planes were chosen. Note that $Y$ is invertible with prob 1. So $Yx=B$ has a single solution with prob 1. On the other hand, the single point of intersection is, with prob 1, disjoint from the (independently drawn) 4th plane. This holds with prob 1 for all choices of 3 planes. So, with prob 1, we produce the desired counter-example.

Michael
  • 23,905