Is this stronger Knaster-Kuratowski-Mazurkiewicz Lemma true?

2012-08-25T16:04:41Z

The Knaster-Kuratowski-Mazurkiewicz Lemma is the continuous analogue of Sperner's lemma. I wonder if the following, more general version is true.

Let S be the standard simplex spanned by the standard orthonormal basis for $\mathbb R^{n+1}$, so S equals the convex hull of $(e_i:i\in [n+1])$. Assume we have n+1 closed subsets $C_1, \ldots, C_{n+1}$ with the property that for every subset $I$ of [n+1] the following holds: the convex hull of $(e_i:i\in I)$ is disjoint from $\cup_{i\notin I} C_i$. Is it true that either there are t $C_i$'s that intersect OR there is a k-dimensional "subspace" of S that is disjoint from all the $C_i$'s, if n is large enough (compared to t and k)?

By k-dim subspace of S I mean a linear subspace (passing through the origin) whose intersection with S is k-dimensional. Any better formulations of the problem and retags are welcome.

Note that for k=0 we get back the KKM lemma. I do not know the answer already for k=1. In case it is false, is it possible to replace the affine subspace by something else?

Edit: As Ilya pointed out in the Edit part of his answer, we cannot hope for a k-dim subspace. Any other reasonable "big" manifold we can hope for?

Answer by Ilya Bogdanov for Is this stronger Knaster-Kuratowski-Mazurkiewicz Lemma true?

2012-08-25T20:10:54Z

$\def\conv{\mathop{\rm conv}}\def\aff{\mathop{\rm aff}}\let\eps\varepsilon$It seems that you may set $n=k+t$. Consider the sets $C_1,\dots,C_t$. If they have a nonempty intersection, we are done. Otherwise, by KKM they do not cover $S_t=\conv\{e_i\colon i\in[t]\}$. Take a point $s\in S_t$ which is not covered. Since $C=\cup C_i$ is closed, its complement is open, hence some neighborhood $U(s)$ does not intersect $C$.

Now choose $\eps>0$ and define $s_i=s+\eps(e_i-s)$ for $i=t+1,\dots,n$; we have $s_i\in U(s)$ if $\eps$ is small enough. Then the subspace $V=\aff\{s_i\colon t< i\leq n+1\}$ is parallel to $\aff\{e_i\colon t< i\leq n+1\}$. Hence it is easy to see that $V\cap S=\conv\{s_i\colon t< i\leq n+1\}$ is a $k$-dimensional subset, and it lies in $U(s)$; thus it is disjoint from $C$.

NB. It seems that the bound $n=k+t$ is optimal for almost all pairs $(k,t)$ (though for $k=0$ you may take $n=t-1$). It is easy to provide a counterexample for $k=1$, $t=2$, $n=2$, and it seems possible to generalize this example for larger values.

EDIT. On the counterexamples for the `large' $k$-dim space. Consider the Voronoi decomposition of your simplex with respect to its vertices; scale the obtained sets to the corresponding vertices to obtain disjoint closed sets $C_i'$. Now all the $k$-dim subsets not intersecting $C_i'$ are close to the boundaries of the Voronoi cells. Now it is easy to change our sets in the neighborhood of their boundaries so that the only such subsets will be very close to the boundary of the simplex. (For every cell border, It is enough to make some hollows in one part and some protuberances in the other one).

Is this stronger Knaster-Kuratowski-Mazurkiewicz Lemma true? - MathOverflow

Is this stronger Knaster-Kuratowski-Mazurkiewicz Lemma true?

Answer by Ilya Bogdanov for Is this stronger Knaster-Kuratowski-Mazurkiewicz Lemma true?