Sperner's lemma in action

  We define a class of sets $S(m,\lambda)$ that are used as vertex sets for graphs. A point (or vertex) $\bar x=(x_0x_1\dots x_\lambda)$ is a vector in $\mathbf N^{\lambda+1}$ for which $\sum_{i\leq \lambda} x_i=m$. Two vertices $\bar x$ and $\bar y$ are adjacent, denoted as $\bar x\sim\bar y$, if $\forall i: x_i-y_i\in\{-1,0,1\}$.

Fact 13395

The number of points in $S(m,\lambda)$ is $\binom{m+\lambda}{\lambda}$.

Proof. Count ``balls and walls.'' Think of m balls that are divided into $\lambda+1$ subsets by $\lambda$ walls. There are $\binom{m+\lambda}{\lambda}$ ways of placing the walls without respect to order.$\Box$

  

Figure 13.1: The graph on the points S(6,2) makes a 2-simplex. To describe one point, three coordinates are used; one of them is redundant. On facet i, coordinate i is zero.

Claim 13411

In any $(\lambda, d(n))$-decomposition of $S(m,\lambda)$, there is always at least one cluster that intersects all facets.

Proof. The proof is by contradiction. Consider the $\lambda$-simplex containing all points in $S(m,\lambda)$, and define a Spencer labeling of $S(m,\lambda)$ as follows. Label the vertex v by

$$l(v) = \min \{ i \mid F_i \cap C(v) = \emptyset \};$$

here C(v) is the cluster in which v belongs, and $F_0,F_1,\dots,F_\lambda$ are the facets of the simplex. The labeling ensures that if the vertex v is on facet i, it will not be labeled i (and thus it is a Sperner labeling). The labeling is well defined since we suppose that for each cluster, there is a facet which does not intersect it. Sperner's lemma ensures that there is a smaller, fully labeled $\lambda$-simplex.

The decomposition we have uses at most $\lambda$ colors, so we know that at least two points of the smaller simplex share the same color. Since these points are neighbors they are in the same cluster. Since the label for a vertex depends only on the cluster in which it belongs, the two vertices with the same color also have the same label; a contradiction.$\Box$

Theorem 13429

Any $(\lambda, d(n))$-decomposition of $S(m,\lambda)$ has $d(n)\geq m/\lambda$.

Proof. We now continue to prove that the cluster which intersects all facets must have high diameter. Denote the cluster that intersects all facets by O. Consider $\bar x=\{x_0x_1\dots x_\lambda\} \in O \cap F_0$. Since $\sum_{i\leq \lambda} x_i=m$ and x₀=0, there is a j such that $x_j\geq m/\lambda$. Now, for $\bar y\in O\cap F_j$ we have that y_j=0, and thus $d(\bar x,\bar y)\geq m/\lambda$ since two neighbors differ by at most one at coordinate j.$\Box$

Corollary 13444

Any $(\lambda, d(n))$-decomposition of $S(m,\lambda)$ has $\lambda d(n) \in \Omega(n)$.

Proof. We have $n=\binom{m+\lambda}{\lambda}$, implying that $m/\lambda \geq n^{1/\lambda}/3$. Thus, $\lambda d(n) \geq \lambda n^{1/\lambda}/3$, which we minimize over $\lambda$ to get $\log n$.$\Box$