To prove that the intersection of the given sets is not empty

302 Views Asked by At

Below is a question that I came across recently. Suppose $G = \text{conv}\{k_{1}, . . . ,k_{n}\}$ be a convex set in $R^{d}$. Then we have to prove that the intersection of $F_{i}=\{p :(-1/d)k_{i}+ p\in G\}$ is not empty.

$\textbf{What I have tried}$: Given $ G =\text{conv}\{k_{1}, . . . ,k_{n}\}$ hence it can be written as convex combinations of all $k_{1},...,k_{n}$: $G=\{\sum_{j=1}^{n}\lambda_{j}k_{j};\lambda_{j}\geq 0;\sum_{j=1}^{n}\lambda_{j}=1\}$.

Now $F_{i}=\{p :(-1/d)k_{i}+ p\in G\}=\{\sum_{j=1}^{n}\lambda_{j}k_{j}+(1/d)k_{i}\}$ (I have skipped writing the convexity conditions inside the bracket but its there).

Now by $\sum_{j=1}^{n}\lambda_{j}k_{j}+(1/d)k_{i}$, I believe the author is talking about Minkowski sum. So $F_{i}$ is basically a translation of the convex hull $G$ by $k_{i}/d$.

Now I have to show that $\cap_{i=1}^{n}F_{i}\neq\phi\Rightarrow\cap_{i=1}^{n}\Big\{\sum_{j=1}^{n}\Big(\lambda_{j}k_{j}+(1/d)k_{i}\Big)\Big\}\neq\phi$. This is where I got stuck. Could anyone please help me on how to proceed from here.

Thanks in advance.

$\textbf{P.S.}$: $\textbf{I have edited out the question because earlier there was a mistake in the question.}$

1

There are 1 best solutions below

0
On

Let's suppose $G$ has nonempty interior, so $n \geq d + 1$. For each set $S \subset \{1, \dotsc, n\}$ with $\lvert S \rvert = d+1$, consider the point $p_S = \sum_{i \in S} \frac{k_i}{d}$. For any given $j \in S$, $$(-1/d)k_j + p_S = \sum_{i \in S \setminus \{j\}} \frac{1}{d} k_i \in G.$$

Therefore $p_S \in \bigcap_{j \in S} F_j$.

So we have a collection of $n$ convex sets $F_i$, and the intersection of any $d+1$ of them is nonempty. By Helly's Theorem, the intersection of the whole collection is nonempty.