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?

  • $\begingroup$ In view of the answer below, I wish to change the notion of $k$-dimensional affine subspace; it seems that this subspace should be `large enough'. On the other hand, if it will be too large, then the conjecture becomes false... $\endgroup$ – Ilya Bogdanov Aug 25 '12 at 20:48
  • $\begingroup$ Why does it become false? $\endgroup$ – domotorp Aug 25 '12 at 20:58
  • $\begingroup$ Now I don't understand. What is the principal difference between affine and linear subspace, if (as in your definition) $S$ does not contain the origin? $\endgroup$ – Ilya Bogdanov Aug 26 '12 at 8:11
  • $\begingroup$ As I defined linear subspace of S, it is required that it passes through the origin if we extend it beyond S. I am sorry that I defined it so vaguely that it is hard to understand what I want. Anyhow, now it is unimportant, as your example showed that we cannot have it.. Do you have any ideas about some theorems that could guarantee some high dim manifold stretching to many boundaries of S? $\endgroup$ – domotorp Aug 26 '12 at 15:55
  • 1
    $\begingroup$ The correct statement seems to be as follows. Assume that the intersection of any $t+1$ of $C_i$'s is empty. Then there exists a connected component of $S\setminus \cup C_i$ which touches every $t$-dimensional face of $S$. $\endgroup$ – Ilya Bogdanov Aug 27 '12 at 10:26

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

  • $\begingroup$ I think there is a misunderstanding in the definition of my definition of k-dim affine subspace of S. It must the whole intersection of S and a linear subspace. $\endgroup$ – domotorp Aug 25 '12 at 20:58
  • $\begingroup$ Where is a misunderstanding? The intersection of $V$ with $S$ is exactly a small piece contained in $U(s)$. You may consider also the linear hull of $V$ --- it changes nothing since $S$ lies in $\mathop{\rm aff}\{e_i\colon i\in [n+1]\}$. . $\endgroup$ – Ilya Bogdanov Aug 25 '12 at 21:43
  • $\begingroup$ I still think that we have a misunderstanding, probably I should not have called it affine subspace of S but rather subspace of S. I have tried to make the def in the original post more clear. Do you see the problem now or is it my bad and am I missing something? $\endgroup$ – domotorp Aug 26 '12 at 6:48
  • $\begingroup$ Okay, the Edit part answers my original question. In this construction the uncovered part is a high dim manifold stretching to every face. So can we guarantee the existence of something like this? I know this is a vague question... $\endgroup$ – domotorp Aug 26 '12 at 7:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.