2
$\begingroup$

The famous Sperner's lemma states that, if a labeling of a triangulation of a simplex satisfies certain conditions on the boundary, then there must exist a sub-simplex in which all labels are different. Here is an example, where the simplex and sub-simplices are right-angled triangles:

1
1   1
2   ?   3
2   2   2   3

I showed only the labels on the boundary. They satisfy Sperner's conditions, and indeed, whatever label we put instead of the ? in the interior (1, 2 or 3), we will have a fully-labeled sub-simplex.

Sperner's boundary conditions are sufficient but not necessary. For example, here:

1
1   2
1   ?   3
1   1   1   1

the labeling does not satisfy Sperner's boundary conditions, but still, whatever label we put instead of the ? in the interior (1, 2 or 3), we will have a fully-labeled sub-simplex.

My question is: are there conditions such that, if the labeling satisfies the conditions on the boundary, then not every completion of the labeling in the interior admits a fully-labeled simplex?

$\endgroup$
1
  • $\begingroup$ Consider the un-ordered pairs made of adjacent boundary labels. If one of the three possibilities does not occur then filling the interior with the third label avoids a fully labeled simplex. That pretty weak though $\endgroup$ Nov 6, 2019 at 22:38

1 Answer 1

3
$\begingroup$

Let $n$ be the dimension of the main simplex, then we are looking for a triangulation without simplices that have $n+1$ labels.

Triangular case ($n=2$)

Let $\ell(u)$ denote the label of vertex $u$, let $\partial$ the boundary of the main simplex, and let $k_\partial(a,b)$ be the number of (clockwise) edges $(u,v)$ along $\partial$ for which $\ell(u)=a$ and $\ell(v)=b$.

Condition 1. For any $a\neq b$, we must have $k_\partial(a,b)=k_\partial(b,a)$.

Necessity

To see that condition 1 is necessary for there not to be a fully-labeled simplex, consider a labeled triangulation without any fully-labeled simplex. The edges with labels $a$ and $b$ dualize to a set of paths, each of which is either a cycle in the interior, or paths that start and end on an edge of the boundary. In particular, the latter type of path always has label $a$ on one side, and label $b$ on the other side, which means that it must use both a clockwise and a counter-clockwise boundary edge with labels $a$ and $b$.

Sufficiency

We also show that if condition 1 applies, then there exists a triangulation without a fully-labeled simplex.

We proceed by induction on $K(\partial):=k_\partial(1,2)+k_\partial(2,3)+k_\partial(1,3)$. Let $\partial$ be a boundary satisfying condition 1, and assume that for any boundary $\partial'$ that satisfies condition 1 and $K(\partial')<K(\partial)$, there exists a labeled triangulation of $\partial'$ without a fully-labeled simplex.

If $K(\partial)=0$, then the boundary has a single label, and we can triangulate and label the interior arbitrarily using only that label without creating any fully-labeled simplex.

Next, suppose that for two labels $a\neq b$ and an integer $k\geq 1$, $\partial$ contains a path of labels $ab^ka$ (i.e. two vertices labeled $a$ connected by a path of vertices labeled $b$). Introduce an interior vertex $v$ (labeled $a$) creating a triangle with each edge along the path $ab^ka$. These triangles use only labels $a$ and $b$. Let $\partial'$ be the cycle obtained from $\partial$ by replacing the path of $b$'s by the vertex $v$. Then $\partial'$ satisfies condition 1 and $K(\partial')=K(\partial)-1$, so by induction we can triangulate and label $\partial'$, and hence the remainder of $\partial$, without creating fully-labeled simplices.

Finally, suppose that $K(\partial)>0$, but there are no two labels $a\neq b$ for which $\partial$ contains a path $ab^ka$. Then the entire boundary is labeled according to the pattern $(a^+b^+c^+)^+$ with $a\neq b\neq c\neq a$. But then $k_\partial(b,a)=0<k_\partial(a,b)$, so $\partial$ violates condition 1 and we are done.

Prescribed triangulations

Note that the above necessary and sufficient condition does not imply that all triangulations satisfying condition 1 can be labeled without creating a fully-labelled simplex. In fact, the converse is true, as illustrated by the figure below: it satisfies condition 1, but no matter what label the interior vertex is given, a fully-labeled simplex will be created.

boundary conditions are insufficient

As a consequence, the labeling of the boundary is insufficient to determine whether any particular triangulation admits a labeling without fully-labeled simplices.

General case ($n>2$)

Let $\partial$ be a labeled triangulated $(n-1)$-sphere, and fix a consistent orientation of its $(n-1)$-simplices. Say that an $(n-1)$-simplex $(v_1,v_2,\dots,v_n)$ has labeling $L=(l_1,l_2,\dots,l_n)$ if there is an even permutation $\pi$ of $L$ such that $\ell(v_i)=\pi(l_i)$ for all $i$. Let $k_\partial(L)$ be the number of $(n-1)$-simplices of $\partial$ with labeling $L$. Call $L$ critical if it has $n$ distinct labels, and call an $(n-1)$-simplex critical if it has a critical labeling.

Condition 2. For any critical $L$ and any odd permutation $\bar{L}$ of $L$, we have $k_\partial(L)=k_\partial(\bar{L})$.

Necessity

Consider a labeled triangulated $n$-ball without any fully-labeled simplex. Let $\sigma$ be one of its $n$-simplices. If $\sigma$ has a face $F$ with a critical labeling $L$, then the vertex $v'$ of $\sigma$ that does not lie on $F$ shares a color with a vertex $v$ of $F$, so there is a second face of $\sigma$ whose labeling (oriented with respect to $\sigma$) is an odd permutation of $L$, and all the other faces of $\sigma$ contain both $v$ and $v'$ and are hence not critical. Therefore, the $(n-1)$-simplices with critical labelings dualize to a set of disjoint paths, each of which is either cycle interior to the ball, or a path between two critical $(n-1)$-simplices on the boundary. Moreover, the labelings of these two simplices are odd permutations of one another since the orientations with respect to consecutive primal $n$-simplices along the path cancel out.

Sufficiency

Pick an arbitrary matching between the simplices of the boundary with critical labels, such that for any pair in the matching, their labelings are odd permutations of one another. Connect any pair of matched simplices by a path of $n$-simplices inside the $n$-ball, creating a prism-like tunnel whose base and top are the matched critical simplices, and whose interior $(n-1)$-simplices all have the same critical labeling as the matched pair. Note that the boundary of this tunnel (except for the matched simplices) consists of only non-critical simplices. We can dig the tunnels in such a way that their faces are disjoint. Now the complement of the tunnels (with respect to the $n$-ball) has only non-critical simplices on its boundary, so we can triangulate the interior arbitrarily, and assign the label $1$ to all interior vertices to obtain a triangulated $n$-ball without any fully-labeled simplex.

$\endgroup$
2
  • $\begingroup$ Beautiful answer, thanks! I can easily see how to extend the necessity argument to $n>3$. Can the sufficiency argument be extended too? $\endgroup$ Nov 7, 2019 at 8:14
  • $\begingroup$ I added the general case. $\endgroup$
    – Tim
    Nov 8, 2019 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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