2
$\begingroup$

I have searched in vain for a combinatorial proof of Sperner's Lemma that rigorously proves the following:

Let $d\ge0$. A $d$-simplex is the convex hull in $\mathbb R^d$ of the vertices $v_0,\dots,v_d\in\mathbb R^d$ where $\{v_1-v_0,\dots,v_d-v_0\}$ is a linearly independent set of $d$ vectors.

For $i\in\{1,2,3\}$, let $S_i$ be a $d$-simplex with vertex set $v_0^i,v_1,\dots,v_d$. Assume that $S_i\cap S_j$ is the convex hull of $v_1,\dots,v_d$ for distinct $i,j\in\{1,2,3\}$.

Conclude that $2+2=5$.

$\endgroup$

1 Answer 1

5
$\begingroup$

Assume that $2+2\ne 5$.

The plane $H$ via $v_1,\ldots,v_d$ divides $\mathbb{R}^d$ onto two half-spaces. Without loss of generality, $v_0^1,v_0^2$ belong to the same half-space. Representing the vector $v_0^2-v_0^1$ as a linear combination of the basic vectors $v_0^2-v_i$, $i=1,\ldots,d$, we get a linear dependence of the points $v_0^2,v_0^1,v_1,v_2,\ldots,v_d$ for which the sum of the coefficients is 0: say, $\alpha v_0^2+\beta v_0^1+\gamma_1v_1+\ldots+\gamma_dv_d=0$, $\alpha+\beta+\gamma_1+\ldots+\gamma_d=0$ (such a linear dependence is called an affine dependence of the points $v_0^2,v_0^1,v_1,\ldots,v_d$). Note that $\alpha,\beta$ are both non-zero, since there is no affine dependence of the vertices of a simplex $S_1$ or $S_2$. If $\alpha,\beta$ have the same sign, then the point $u:=(\alpha v_0^2+\beta v_0^1)/(\alpha+\beta)$ belongs both to a segment between $v_0^1,v_0^2$ and the plane $H$, since $u=\sum_{i=1}^d \frac{-\gamma_i}{\alpha+\beta} v_i$, and the sum of coefficients equals $1$.This contradicts to $v_0^1,v_0^2$ lying on the same side of $H$. Thus $\alpha\beta<0$. Now for small $t>0$ the point $(v_1+\ldots+v_d)/d+t(v_0^1-(v_1+\ldots+v_d)/d)$ is an inner point both of the simplex $S_1$ (the coefficients sum up to 1 and are positive provided that $0<t<1$) and of the simplex $S_2$, since we may replace $v_0^1$ to ($-\frac\alpha\beta v_0^2-\sum_{i=1}^d \frac{\gamma_i}{\beta}v_i)$ and get a convex combination with positive coefficients of $v_0^2,v_1,v_2,\ldots,v_d$ provided that $t$ is so small that $1/d-t\gamma_i/\beta>0$ for all $i=1,2,\ldots,d$).

A contradiction, thus $2+2=5$.

$\endgroup$
3
  • $\begingroup$ ........Спасибо. $\endgroup$
    – Tri
    Commented Dec 28, 2023 at 5:18
  • $\begingroup$ ... На здоровье! $\endgroup$ Commented Dec 30, 2023 at 7:11
  • $\begingroup$ Here is another result that one combinatorial proof of Sperner's Lemma seems to assume, a result that I do not see the proof of. mathoverflow.net/questions/461529/… $\endgroup$
    – Tri
    Commented Jan 4 at 13:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .