A polytopal generalization of Sperner''s lemma.
We prove the following conjecture of Atanassov (Studia Sci. Math. Hungar. 32 (1996), 71-74). Let T be a triangulation of a d-dimensional polytope P with n vertices v1, v2,...., vn. Label the vertices of T by 1,2,..., n in such a way that a vertex of T belonging to the interior of a face F of P can only be labelled by j if vj is on F. Then there are at least n - d full dimensional simplices of T, each labelled with d different labels. We provide two proofs of this result: a non-constructive proof introducing the notion of a pebble set of a polytope, and a constructive proof using a path-following argument. Our non-constructive proof has interesting relations to minimal simplicial covers of convex polyhedra and their chamber complexes, as in Alekseyevskaya (Discrete Math. 157 (1996), 15-37) and Billera et al. (J. Combin. Theory Ser. B 57 (1993), 258-268).
Introduction
Sperner's Lemma is a combinatorial statement about labellings of triangulated
simplices whose claim to fame is its equivalence with the topological xed-point
theorem of Brouwer [8, 16]. In this paper we prove a generalization of Sperner's
Lemma that settles a conjecture proposed by K.T. Atanassov [2].
Consider a convex polytope P in R d dened by n vertices d . For
brevity, we will call such polytope an (n; d)-polytope. Throughout the paper we
will follow the terminology of the book [20]. By a triangulation T of the polytope
P we mean a nite collection of distinct simplices such that: (i) the union of the
simplices of T is P , (ii) every face of a simplex in T is in T , and (iii) any two
simplices in T intersect in a face common to both. The points v are called
vertices of P to distinguish them from vertices of T , the triangulation. Similarly, a
simplex spanned by vertices of P will be called a simplex of P to distinguish it from
simplices involving other vertices of T . If S is a subset of P , then the carrier of S,
denoted carr(S), is the smallest face F of P that contains S. In that case we say S
is carried by F . A cover C of a convex polytope P is a collection of full dimensional
simplices in P such that [ 2C . The size of a cover is the number of simplices
in the cover.
2000 Mathematics Subject Classication. Primary 52B11, Secondary 55M20.
Key words and phrases. Sperner's lemma, polytope, path-following, simplicial algorithms.
[ Department of Mathematics, University of California Davis, Davis, CA 95616,
deloera@math.ucdavis.edu.
Magdalen College, Oxford University, Oxford OX1 4AU, U.K.,
elisha.peterson@magdalen.oxford.ac.uk.
\ Department of Mathematics, Harvey Mudd College, Claremont, CA 91711, U.S.A.,
su@math.hmc.edu.
J. A. DE LOERA, E. PETERSON, AND F. E. SU
Let T be a triangulation of P , and suppose that the vertices of T have a labelling
satisfying these conditions: each vertex of P is assigned a unique label from the set
and each other vertex v of T is assigned a label of one of the vertices
of P in carr(v). Such a labelling is called a Sperner labelling of T . A d-simplex in
the triangulation is called a fully-labeled simplex or simply a full cell if all its labels
are distinct. The following result was proved by Sperner [16] in 1928:
Sperner's Lemma. Any Sperner labelling of a triangulation of a d-simplex must
contain an odd number of full cells; in particular, there is at least one.
Constructive proofs of Sperner's lemma [4, 9, 12] emerged in the 1960's, and
these were used to develop constructive methods for locating xed points [18, 19].
Sperner's lemma and its variants continue to be useful in applications. For example,
they have recently been used to solve fair division problems in game theory [14, 17].
The main purpose of this paper is to present a solution of the following conjecture.
Conjecture (Atanassov). Any Sperner labelling of a triangulation of an (n; d)-
polytope must contain at least (n d) full cells.
In 1996, K.T. Atanassov [2] stated the conjecture and gave a proof for the case
2. Note that Sperner's lemma is exactly the case 1. In this
paper we prove this conjecture for all (n; d)-polytopes. Here is the central result of
our paper:
Theorem 1. Any Sperner labelling of a triangulation T of an (n; d)-polytope P
must contain at least (n d) full cells. Moreover, the collection of full cells in T
corresponds to a cover of P under the piecewise linear map that sends each vertex
of T to the vertex of P that shares the same label.
We provide a non-constructive and a constructive proof of Theorem 1. The non-constructive
proof in Section 2 is obtained via a degree argument and the notion
of a pebble set. Section 3 develops background on path-following arguments in
polytopes that is closely related to classical path-following arguments for Sperner's
lemma [4, 9, 18]. This is applied to give a constructive proof for simplicial poly-
topes. In Section 4 we extend the construction to prove the conjecture for arbitrary
polytopes. The nal section of the paper is devoted to two interesting consequences
of Theorem 1 and its proofs. From our rst proof we derive the following corollary:
Corollary 2. Let c(P ) denote the covering number of an (n; d)-polytope P , which
is the size of the smallest cover of P . Then, c(P )  n d. This result is best
possible as the equality is attained for stacked polytopes.
We also obtain a slight strengthening of Theorem 10 of [10]. We need to recall
the notion of chamber complex of a polytope P (see [1]): let  be the set of all
d-simplices of P . Denote by bdry() the boundary of simplex . Consider the
set of open polyhedra P [ 2 bdry(). A chamber is the closure of one of these
components. The chamber complex of P is the polyhedral complex given by all
chambers and their faces.
Corollary 3. Let P be an (n; d)-polytope with vertices
ng be a collection of closed sets covering the (n; d)-polytope P , such that each
face F is covered by [fC h j v h 2 Fg.
Then, for each p 2 P , there exists a subset J p  ng such that (1) p
lies in the convex hull of the vertices v j with j 2 J p , (2) J p has cardinality d
A POLYTOPAL SPERNER'S LEMMA 3
(3) \ j2Jp C j 6= ;, and (4) if p and q are interior points of the same chamber of P ,
then . There are at least c(P ), the covering number, dierent such subsets,
and the simplices of P indicated by the labels in these subsets form a cover of P .

Figure

1 illustrates with an example the content of the above corollary.

Figure

1. Part (A) shows several closed sets covering a hexagon
and their four intersection points. The points of intersection correspond
to a cover of the hexagon, in this case a triangulation,
illustrated in part (B).
2. A Non-Constructive Proof using Pebble Sets
The non-constructive proof of Theorem 1 that we give in this section is an extension
of \degree" arguments for proving the usual Sperner's lemma. We rst
establish a proposition that yields the covering property, then show how the construction
a pebble set will yield a lower bound for the number of full cells.
Let P be an (n; d)-polytope with Sperner-labelled triangulation T . Consider the
piecewise linear (PL) maps each vertex of T to the vertex of
P that shares the same label, and is linear on each d-simplex of T .
Proposition 4. The dened as above is surjective, and thus the
collection of full cells in T forms a cover of P under f .
Before proving this result, we recall a few facts about the degree of a map f
between manifolds. If y and the Jacobian determinant of f exists and is
non-zero at x, then x is called a regular point of f , and the sign of x is the sign (1)
of this determinant. The point y is called a regular value of f if every pre-image
of y is a regular point. Any regular value y has nitely many pre-images, and the
sum of the signs of its pre-images is, in fact, independent of the choice of y and is
known as the degree of the map f .
The degree is a homotopy invariant of mappings between manifolds (relative to
their boundaries) and may also be computed as the multiplicative factor induced by
the map f on the corresponding top homology groups (relative to their boundaries).
See [5, Ch.1] or [13, Sec.38] for expositions of the topological degree of simplicial
maps, or [7] for the general theory.
4 J. A. DE LOERA, E. PETERSON, AND F. E. SU
Thus for the above, the interior points of simplices of T
are regular points; interior points of chambers of P are regular values. Observe that
the sign of a regular point x depends essentially on the orientation of the labels of
the simplex of T that contains x.
Proof. We shall show, by induction on the dimension d of P , that f has degree 1.
If then P is a point and the statement is clearly true. So assume that the
above statement holds for all polytopes of dimension less than d.
Given a d-dimensional polytope P , let @P denote the boundary of P (i.e., the
union of the facets). If consists of two points on which the map
is the identity (due to the Sperner labelling), and therefore @f  :
is the identity map on (reduced) homology groups. For
d > 1, we use the Sperner labelling on the facets and the inductive hypothesis to
show that the map @f  is the identity map. Specically, if F is any facet of P ,
. Then the map @f induces the following commutative diagram of
(reduced) homology groups:
where the rows are exact. Since H i 2g, the maps
are isomorphisms. By excision, H d 1 (@P;
f  to be induced by f on the facet F (a polytope of one lower dimension)
which by the inductive hypothesis has degree 1 and must therefore be the identity.
Since the maps   are isomorphisms and f  is the identity map, @f
also the identity map.
The map @f  appears in another commutative diagram of (reduced) homology
groups induced by f :
where the rows are exact. Since H 1g, the maps @  are
isomorphisms, which implies that f  is the identity map. Hence f has degree 1.
Therefore the number of pre-images of any regular point y in the image of f is
(when counted with sign). So the map f is surjective, and full cells in T gives a
cover of P under f .
Thus if we can nd a set of points in P such that any d-simplex spanned by
vertices of P contains at most one such point in its interior, then the pre-image
of each such point will correspond to a full cell in P (in fact, an odd number,
because the number of pre-images, counted with sign, is 1). Thus nding full cells
in Theorem 1 corresponds precisely to looking for the following kind of nite point
Denition. A pebble set of a (n; d)-polytope P is a nite set of points (pebbles)
such that each d-simplex of P contains at most one pebble in its interior.
It is worth remarking now two facts about pebble sets. First, the larger the
pebble set, the more full cells we can identify, i.e., the number of full cells is at
A POLYTOPAL SPERNER'S LEMMA 5
least the cardinality of the largest size pebble set in P . Second, by the denition of
chamber, only one pebble can exist within a chamber and when choosing a pebble p
we have the freedom to replace it by any point p 0 in the interior of the same chamber
because p and p 0 are contained by the same set of d-simplices. We now show that
a pebble set of size (n d) exists for any (n; d)-polytope P by a \facet-pivoting"
construction.

Figure

2. A pebble set with pebbles
In the simplest situation, if one of the facets of P is a simplex, call this simplex
the base facet. Choose any point q 0 (the basepoint) in the interior of this base facet.
Now for each vertex v i not in the base facet, choose a point p i along a line between
very close to v i . Exactly how close will be specied in the proof.
The collection of all such points fp i g forms a pebble set; it is size (n d) because
the simplicial base facet has d vertices. See, for example, Figure 2 for the case of a
pentagon; it is a (5; 2)-polytope with pebble set fp 1 g.
If none of the facets are simplicial, then one must choose a non-simplicial facet
as base. In this case, choose a pebble set fq i g for the base facet (an inductive
hypothesis is used here) and then use any one of them for a basepoint q 0 to construct
above. The remaining pebbles are obtained from the other q i by perturbing
them so they are interior to P . See Figure 3.
Theorem 5. Any (n; d)-polytope contains a pebble set of size (n d).
Proof. We induct on the dimension d. For dimension a polytope is just a
line segment spanned by two vertices. Hence n clearly any point in the
interior of the line segment forms a pebble set.
For any other dimension d, let V =fv 1 ; :::; vn g 2 R d denote the vertices of the
given (n; d)-polytope P . Choose any facet F of P as a \base facet", and suppose
without loss of generality that it is the convex hull of the last k vertices
d. Then F is a (d 1)-dimensional polytope with k
vertices, and by the inductive hypothesis, F has a pebble set QF with
pebbles . (If F is a simplex, then consists of one point
which can be taken to be any point on the interior of F .)
Let diam(P ) denote the diameter of the polytope P , i.e., the maximum pairwise
distance between any two points in P . Let H be the minimum distance between
6 J. A. DE LOERA, E. PETERSON, AND F. E. SU
any vertex v 2 V and the convex hull of the vertices in V n fvg. Since there are
nitely many such distances and the vertices are in convex position, H exists and
is positive. Set
(1)
Using denote the collection of (n points dened
by
(2)
positive constant given by (1). Thus points in
along straight lines extending from q 0 and very close to the vertices of P not
in F .

Figure

3. A pebble set with pebbles
. The pebbles
lie just above (not shown) on the base of the
polytope. Note how q arise from the pebble set construction
in Figure 2.
Because q i is in F , it lies on the boundary of P and borders exactly one chamber
of P (since by induction it is interior to a single chamber in the facet F ). Ignoring
momentarily, for 1
i denote a point obtained by \pushing" q i
into the interior of the unique chamber that it borders. Let Q
g.
We shall show that
is a pebble set for the polytope P . Note that if P has a simplicial facet F , then with
this facet as base, the set Q suces; for then Q
F is empty and the construction
(2) yields the required number of pebbles by choosing any q 0 in the interior of a
simplicial facet F .
First we prove some important facts about the p i and q
Lemma 6. Let S be a d-simplex spanned by vertices of P . If S contains p i , it
must also contain v i as one of its vertices.
A POLYTOPAL SPERNER'S LEMMA 7
Proof. By construction, each p i has the property that p i is not in the convex hull
of g. This follows because
hence implying that the distance of p i from the convex hull of
is greater than or equal to H=2.
Since the convex hull of V n fv i g does not contain p i , if S is to contain p i it
must contain v i as one of its vertices.
Lemma 7. Let S be a non-degenerate d-simplex spanned by vertices of P . Then
i is in S if and only if q i is in S \ F .
Proof. Since q
i is in the unique chamber of P that q i borders, any non-degenerate
simplex containing q i must contain q
. Conversely, any simplex S containing q
must contain its chamber and therefore contains q i . Since q i is in F , then q i is in
The next three lemmas will show that Q [ Q
F is a pebble set for P .
Lemma 8. Any d-simplex S spanned by vertices of P contains no more than one
pebble of Q.
Proof. If S is degenerate (i.e., the convex hull of those vertices is not full dimen-
sional), then it clearly contains no pebbles of Q because the p i are by construction
in the interior of a chamber. So we may assume that S is non-degenerate.
denote the vertices of S. Suppose by way of contradiction
that S contained more than one point of Q. Then are contained in S
for distinct implies that v i must both
be vertices of S. Without loss of generality, let s A be a
matrix whose columns consist of q 0 and the vertices of S, adjoined with a row of
1's:
This is a (d+1)(d+2) matrix that has rank (d+1) because the s i are anely independent
(by the non-degeneracy of S). So the kernel of A, ker(A) is 1-dimensional.
Note that p i 0 2 S implies that it is a convex combination of the rst (d+1) columns
of A. On the other hand, by construction, it is also a convex combination of s 1 and
. Thus there exist constants 0  x
x d+1
8 J. A. DE LOERA, E. PETERSON, AND F. E. SU
where the rst equality follows from (2). Similarly,
y d+13
for some constants 0  y 1. The above equations show that
are both in ker(A).
But since ker(A) is 1-dimensional, and the last coordinates of these vectors are
equal, all entries of these vectors are identical. In particular, x
We now claim that x would show that p j 0
could not have been in S after all, a contradiction.
To establish the claim, use equations (2) and (3) to express q 0 as an ane
combination of the vertices of S:
is not in the interior of S, it must be the case that
then by (4), q 0 is on a facet of S. This means that it is spanned
by d vertices on the facet F of P . Thus the vertices of S must include those d
vertices but by Lemma were not on the facet
F (because S is non-degenerate), we obtain a contradiction since S cannot contain
more than d vertices. Thus the equality x
as desired.
Lemma 9. Any d-simplex S spanned by vertices of P contains no more than one
pebble in Q
F .
Proof. Since S \ F is a simplex in F that contains at most one point of QF , then
by Lemma 7, S can contain at most one point of Q
F .
Lemma 10. Any d-simplex S spanned by vertices of P cannot contain pebbles of
F simultaneously.
Proof. Suppose S contained a point q
i of Q
F . Then by Lemma 7, S \ F contains
q i of QF . Since QF was a pebble set for the facet F , S \F cannot also contain q 0 .
If S also contained a pebble p i 0 of Q, then by Lemma 6, S contains v i 0 as a
vertex. Since S \ F contains q i which is interior to a chamber of F , S must also
contain d vertices of F . Since q 0 is in F (but not in S \ F ), q 0 is expressible as
a linear combination (but not convex combination) of those d vertices. This linear
combination, when substituted for q 0 in (2), would show that the pebble p i 0 is not
a convex combination of v i 0 and those d vertices. This contradicts the fact that p i 0
was in S to begin with.
Together, the three lemmas above show that S cannot contain more than one
point of Q [ Q
F , which concludes the proof of Theorem 5.
Together, Proposition 4 and Theorem 5 prove Theorem 1.
A POLYTOPAL SPERNER'S LEMMA 9
3. Graphs for Path-following and Simplicial Polytopes.
Sperner's lemma has a number of constructive proofs which rely on \path-
arguments (see, for example, the survey of Todd [18]). Path-following
arguments work by using a labelling to determine a path through simplices in a
triangulation, in which one endpoint is known and the other endpoint is a full cell.
In this section we adapt these ideas for Sperner-labelled polytopes, which are used
in the next section to give a constructive \path-following" proof of Theorem 1.
Let P be an (n; d)-polytope with triangulation T and a Sperner labelling using
the label set ng. We dene some further terminology and notation
that we will use from now on. Let L(), the label set of , denote the set of distinct
labels of vertices of . Let L(F ) denote the label set of a face F of P . As dened
earlier, a d-simplex  in T is a full cell if the vertex labels of  are all distinct.
Similarly, a (d 1)-simplex  in T is a full facet if the vertex labels of  are all
distinct. Note that a full facet on the boundary of P can be regarded as a full cell
in that facet.
Denition. Given a Sperner-labelled triangulation T of a polytope P , we dene
three useful graphs:
1. The nerve graph G is a graph with nodes that are simplices of T whose label
set is of size at least d. Formally,  is a node of G if jL()j  d. Two nodes
in G are adjacent if (as simplices) one is a face of the other.
2. If K is a subset of the label set ng of size (d 1), the derived
graph GK is the subgraph of the nerve graph G consisting of nodes in G whose
label sets contain K.
3. Let G 0 denote the full cell graph, whose nodes are full cells in the nerve graph
G. Two full cells ;  are adjacent in G 0 if there exists a path from  to  in
G that does not intersect any other full cell. If
G is a connected component
of G, construct the full cell graph
similarly.
Thus the nodes of G and GK are either full cells, full facets, or d-simplices with
exactly one repeated label. The full cell graph G 0 only has full cells as nodes.
Example. The pentagon in Figure 4 has dimension 2. Let
of cardinality (d 1). Then the derived graph GK consists of 1-simplices and
2-simplices that are darkly shaded, and it is a subgraph of the nerve graph G
consisting of the dark and light-shaded 1-simplices and 2-simplices in Figure 4. In

Figure

4, G 0 is a 3-node graph with nodes A; B; C, the full cells. In G 0 , A is adjacent
to B, and B is adjacent to C, but A is not adjacent to C.
As the example shows, the nerve graph G branches in (d directions at full
cells, while the derived graph GK is the subgraph consisting of paths or loops that
\follow" the labels of K along the boundary of the simplices in G. We prove these
assertions.
Lemma 11. The nodes of the derived graph GK are either of degree 1 or 2 for
any K of size d 1. A node  is of degree 1 if and only if  is a full facet on the
boundary of P . Hence GK is a graph whose connected components are either loops
or paths that connect pairs of full facets on the boundary of P .
Proof. Recall that each node  of GK has a label set containing K and is either a
full cell, full facet, or d-simplex with exactly one repeated label.
J. A. DE LOERA, E. PETERSON, AND F. E. SU134453521

Figure

4. A triangulated (5; 2)-polytope (a pentagon) with
Sperner labelling. If nodes of GK consist of the dark-
shaded simplices, nodes of G consist of dark and light-shaded sim-
plices, and nodes of G 0 consist of the three full cells marked by
If  is a full cell, since we see that L() consists of labels in K and
two other labels l 1 ; l 2 . There are exactly two facets of  whose label sets contain
K; these are the full facets with label sets K [ l 1 and K [ l 1 , respectively. Thus
has degree 2.
If  is a full facet with label set containing K, then it is the face of exactly two
d-simplices, unless  is on the boundary of P , in which case it is the face of exactly
one d-simplex. Thus  is degree 1 or 2 in GK , and degree 1 when  is a full facet
on the boundary of P .
If  is a d-simplex with exactly one repeated label, then it must possess exactly
two full facets. Since K  L(), these full facets must also have label sets that
contain K. Hence these two full facets are the neighbors of  in GK , so  has
degree 2.
Lemma 12. The nodes of the nerve graph G are of degree 1, 2, or d + 1. A node
is of degree 1 if and only if  is a full facet on the boundary of P . A node  is
of degree d only if  is a full cell.
Proof. As noted before, each node  of G is either a full cell, full facet, or d-simplex
with exactly one repeated label. The arguments for the latter two cases are identical
to those in the proof of Lemma 11 by letting K be the empty set.
If  is a full cell, then every facet of  is a full facet, hence the degree of  is
G.
The nerve graph G may have several components, as in Figure 4. In Theorem 16,
we will establish an interesting relation between the labels carried by a component
G and the number of full cells it carries. First we show that all the labels in a
component are carried by the full cells.
A POLYTOPAL SPERNER'S LEMMA 11
Lemma 13. If  is adjacent to  in G, then L()  L(), unless  is a full cell,
in which case L()  L(). Thus adjacent nodes in
G carry exactly the same labels
unless one of them is a full cell.
Proof. Suppose  is a d-simplex with exactly one repeated label. Then it is adjacent
to two full facets with exactly the same label set, so the conclusion holds.
Otherwise, if  is a full facet, then it is adjacent to two d-simplices that contain
it as a facet. Hence L()  L() for  adjacent to .
Finally, if  is a full cell, any simplex  adjacent to  in G is contained in  as
a facet, so L()  L() in that case.
Lemma 14. Suppose
G is connected component of G. If
G contains at least one
full cell as a node, then all the labels in
G are carried by its full cells.
For example, in Figure 4, G has two components. One of them has no full cells.
In the other component, all of its labels f1; 2; 3; 4; 5g are carried by its full cells
Proof. Since
G is connected and contains at least one full cell, each simplex  that
is not a full cell is connected to a full cell  via a path in
G that does not intersect
any other full cell in
G. Call this path g. By Lemma 13,
Therefore labels carried by the full cells
contain all labels carried by any other node of the graph.
Since the label information in a nerve graph is found in its full cells, it suces
to understand how the full cells connect to each other.
Lemma 15. Any two adjacent nodes in G 0 are full cells in T whose label sets
contain at least d labels in common.
Proof. Let  1 and  2 be adjacent nodes in G 0 . By construction they must simplices
connected by a path in G; let  be any such node along this path. Repeated
application of Lemma 13 yields L()
contains at least the d labels in L( ).
We will say the full cell graph G 0 is a fully d-labelled graph because it clearly
satises four properties:
(a) all nodes in the graph are assigned (d (simply assign to a node  of
G 0 the label set L()),
(b) all edges are assigned d labels (assign an edge the d labels specied
in Lemma 15),
(c) the label set of an edge (; ) (denoted by L(; )) is contained in L() \ L( ),
and
are nodes each adjacent to , then L(; )
Proposition 16. Suppose G 0 is a connected fully d-labeled graph. Let L(G 0 ) denote
the set of all labels carried by simplices in G 0 and jG 0 j the number of nodes in G 0 .
Then
We shall use this theorem for graphs G 0 arising as a full cell graph of one connected
component of a nerve graph G. In Figure 4, the full cell graph G 0 has just
one connected component, and L(G 0 indeed 3  5 2.
J. A. DE LOERA, E. PETERSON, AND F. E. SU
Proof. We induct on jG 0 j. If jG the one full cell in G 0 has d labels. Hence
so the statement holds.
We now assume the statement holds for fully d-labeled graphs with less than j
nodes, and show it holds for fully d-labeled graphs G 0 with jG
has j full cells. We claim that it is possible to remove a vertex v from G 0 and leave
connected. This is true because G 0 contains a maximal spanning tree, and the
removal of any leaf from this tree will leave the rest of the nodes in G 0 connected
by a path in this tree.
Now G 0 with v and all its incident edges removed is a new graph (denoted by
nodes. Note that this new graph is still fully d-labeled, so by the
inductive hypothesis, jG 0 vj  jL(G 0 v)j d.
v has at least
d labels in common with some vertex in G 0 v, by Lemma 15. Hence jG
Adding 1 to both sides gives the desired conclusion.
This will prove the following useful result.
Theorem 17. Let T be a Sperner-labelled triangulation of an (n; d)-polytope P .
If the nerve graph G has a component
G that carries all the labels of G, then T
contains at least (n d) full cells.
Proof. Use
G to construct the full cell graph
G 0 as above, which is a fully d-labelled
graph. Note that if
G is connected then
G 0 is also connected. By Lemma 14,
Using Proposition 16, we have
which shows there are at least (n d) full cells in
G, and hence in G itself.
Thus to prove Atanassov's conjecture for a given (n; d)-polytope it suces to
nd some component
G of the nerve graph G for which L(
This is the
central idea of the proofs in the next sections.
We now use path-following ideas to outline a proof of Atanassov's conjecture in
the special case where the polytope is simplicial. This will motivate the proof of
Theorem 1 for arbitrary (n; d)-polytopes in the subsequent section.
Theorem 18. If P is a simplicial polytope, there is some component
G of the nerve
graph G which meets every facet of P , and hence carries all labels of G.
Proof. Let F be a simplicial facet of the polytope P . Let (G; F ) count the number
of nodes of G that are simplices in F . This may be thought of as the number of
endpoints of paths in G that terminate on the facet F .
Consider two \adjacent" whose intersection is a ridge of
the polytope P spanned by (d 1) vertices of P . These vertices have distinct
labels; let K be their label set. The derived graph GK consists of loops or paths
whose endpoints in GK must be full facets in F 1 or F 2 , since the Sperner labelling
guarantees that no other facet of P has a label set containing K.
Since every facet of P is simplicial, all the full facets in F 1 and F 2 contain K in
their label set. Thus all the nodes of G that are full facets in F 1 and F 2 must also
be nodes in the graph GK . Since GK is a subgraph of G and consists of paths with
endpoints that pair up full facets in F 1 and F 2 , we see that (G; F 1
mod 2. In fact, since paths in GK are connected, this argument shows that
G;
G;
A POLYTOPAL SPERNER'S LEMMA 13
for any connected component
G of G.
were arbitrary, the same argument holds for any two adjacent
facets. This yields the somewhat surprising conclusion that the parity of (
G; F )
is independent of the facet F . We denote this parity by (
G). Since (G; F ) is also
independent of facet, we can dene (G) similarly.
Since (G; F ) is the sum of (
G; F ) over all connected components
G of G,
it follows that (G)
connected components
G of G.
Moreover, because the usual Sperner's lemma applied to (any)
simplicial shows that there are an odd number of full facets of T in the
Hence there must be some
G such that (
G meets
every facet of P . Because the facets of P are simplicial,
G carries every label, i.e.,
Theorem 19. Any Sperner-labelled triangulation of a simplicial (n; d)-polytope
must contain at least (n d) full cells.
Proof. This follows immediately from Theorem 18 and Theorem 17.
To extend this proof for non-simplicial polytopes requires some new ideas but
follows the basic pattern: (1) nd a function  that counts the number of times a
component
G of G meets a certain facet in a certain way, and show that this function
only depends on
G, and (2) appeal to the usual Sperner's lemma for simplices in
a lower dimension to constructively show that the parity of  summed over all
components
G must be odd. For the non-simplicial case, we cannot guarantee that
any faces of P except those in dimension 1 are simplicial. How to connect dimension
1 to dimension d is tackled in the next section, and the
ag graph introduced there
gives a constructive procedure for nding certain full cells. Then we construct a
counting function  to show that there are at least (n d) full cells for an (n; d)-
polytope.
4. The Flag Graph and Arbitrary Polytopes.
Throughout this section, let the symbol  denote equivalence mod 2. Recall
that L(F ) denotes the label set of a face F . Let F denote a
ag of the polytope
a choice of faces F 1  F 2  :::  F d where F i is an i-face of P . When the
choice of F i is not understood by context, we refer to the i-face of a particular
ag
F by writing F i (F).
Given a
ag F , it will be extremely useful to construct \super-paths" containing
simplices of P of various dimensions whose endpoints are either on a 1-dimensional
edge or a d-dimensional full cell.
Denition. Let P be an (n; d)-polytope with a Sperner-labelled triangulation T .
Let F be a
ag of P . We dene the
ag graph GF in the following way. For
d, a k-simplex  2 T is a node in the graph GF if and only if  is one of
four types:
(I). the k-simplex  is carried by the k-face F k and
(II). the k-simplex  is carried by the 1)-face F k+1 and
14 J. A. DE LOERA, E. PETERSON, AND F. E. SU
(III). the k-simplex  is carried by the k-face F k and
(IV). the k-simplex  is carried by the k-face F k and
there is an I such that
Two nodes are adjacent in GF if (as simplices) one is a facet of the other and at
least one of the pair is of type (I) or (II).
Note that if  is a type (I) simplex in GF , then it is a \non-degenerate" full cell
of the k-face that it is carried in, i.e., the vertices of P corresponding to the labels
in L() span a k-dimensional simplex. A type (II) simplex is a non-degenerate full
facet in the 1)-face that it is carried in. A type (III) simplex has just one
repeated label and satises a certain kind of non-degeneracy (that ensures its two
full facets are non-degenerate). A type (IV) simplex is one kind of degenerate full
cell in the k-face that it is carried in (but such that it has exactly two facets which
are non-degenerate).422
admits labels 1,2,3,4,5,6,7
F 2admits labels 1,2,3,4,5
F

Figure

5. A path in the
ag-graph of a (7; 3)-polytope. The gure
at left shows simplices along a path in the triangulation. Simplices
carried by F 2 are shaded. The gure at right shows the label
sets of the simplices along this path. Simplices  1 ; :::;  7 occur in
counterclockwise order along this path.
Example. Let P be a (7; 3)-polytope P , i.e., a 3-dimensional polytope with 7
vertices, and suppose T is a Sperner-labelled triangulation of P . Let F 1  F 2  F 3
be a
ag F of P with label sets f1; 2g  f1; 2; 3; 4; 5g  f1; 2; :::; 7g, respectively.
Consider the following collection of simplices shown in Figure 5. Let
be simplices with label sets: L( 1 (with repeated label 2),
6g such that in each pair f i ;  i+1 g, one is a facet of the other. The simplices
are carried by the face F 2 and others are carried by the face F 3 . Each of
these simplices is a node in the graph
are of type (II),  2 is of type (III), and  5 is of type (IV). Furthermore, each pair
A POLYTOPAL SPERNER'S LEMMA 15
i and  i+1 are adjacent in GF . Except for  1 and  7 , each of these simplices has
exactly 2 neighbors in GF so the above sequence traces out a path.
The following result shows that GF does, in fact, consist of a collection of loops
or paths whose endpoints are either 1-dimensional and d-dimensional.
Lemma 20. Every node  of GF has degree 1 or 2, and has degree 1 only when
is a 1-simplex or a d-simplex in GF .
Proof. Consider a k-simplex  of type (I). If k  2, then  has a facet determined
by the k labels in L() \L(F k 1 ), and this facet is a (k 1)-simplex of type (I) or
so it is adjacent to . No other facets of  are types (I)-(IV). If k  d 1, then
is a facet of exactly one (carried by F k+1 ) that must be of type
(I) or (III) or (IV). Thus a type (I) simplex has degree 2 unless d, in
which case it has degree 1.
In case (II), the k-simplex  is the facet of exactly two 1)-simplices in F k+1 ;
these are either of type (I) or (III) or (IV) and are thus neighbors of  in GF .
Facets of  are not types (I)-(IV) because they are co-dimension 2 in the face F k+1 .
Thus type (II) vertices have degree 2.
In case (III), the k-simplex  has exactly two facets determined by the k labels
in L(); each of these is a (k 1)-simplex adjacent to  in GF because it is either
of type (I) in F k 1 or of type (II) in F k . No other facets of  are types (I)-(IV).
Thus type (III) vertices have degree 2.
In case (IV), the labelling rules show that the set L() \ (L(F I ) n L(F I 1 )) is of
size two. Call these labels a and b. There is exactly one facet of  that omits the
label a and one facet which omits the label b; each of these is a (k 1)-simplex of
type (I) in F k 1 or of type (II) in F k , so is adjacent to  in GF . No other facets
of  are non-degenerate; therefore  cannot be types (I) or (II). Thus type (IV)
vertices have degree 2.
We remark that in the denition of the
ag graph, we require at least one of an
adjacent pair to be of type (I) or (II) because without this restriction, some type
vertices could have degree greater than 2. For instance, in a Sperner-labelled,
triangulated (9; 4)-polytope, suppose F 1  F 2  F 3  F 4 is a
ag F of P with
label sets f1; 2g  f1; 2; 3; 4; 5g  f1; 2; :::; 7g  f1; 2; :::; 9g, respectively. If  is a
4-simplex in F 4 with label set f1; 2; 3; 4; 6g such that its face  with labels f1; 2; 3; 4g
is carried in F 3 , then both  and  are of type (IV). They each already have two
facets in GF of type (I) or (II), so we would not want to dene them to be adjacent
to each other.
Theorem 21. A Sperner-labelled triangulation of an (n; d)-polytope contains, for
each edge F 1 of P , a non-degenerate full cell whose labels contain L(F 1 ).
Proof. For any
ag F containing the edge F 1 , Lemma 20 shows that GF consist of
loops or paths whose endpoints are non-degenerate full cells in F 1 or F d ; thus the
total number of such end points full cells in F 1 and in F d must be of the same parity.
On the other hand, the 1-dimensional Sperner's lemma shows that the number of
full cells in F 1 is odd. So the number of non-degenerate full cells in F d in GF must
be odd. In particular there is at least one non-degenerate full cell in F d whose label
set contains L(F 1 ).
J. A. DE LOERA, E. PETERSON, AND F. E. SU
Notice that the above proof is constructive; the graph GF yields a method for
locating a non-degenerate full cell for any choice of
ag F , by starting at one of the
full cells on the edge F 1 (an odd number of them are available). At most an even
number of them are matched by paths in GF , so at least one of them is matched
by a path to a non-degenerate full cell in F d .
However, as we show now, more can be said about the location of full cells.
Rather than locating all of them at the endpoints of paths in a
ag-graph, we can
show that there is some component
G of the nerve graph G that contains at least
(n d) full cells. One can trace paths through this component to nd them. We
nd a component
G of G that carries all labels. Theorem 16 will imply that the
component must have (n d) full cells. As in the case for simplicial polytopes, the
key rests on dening a function  that counts the number of times that
G meets
a facet in a certain way, and then showing that the parity of  exhibits a certain
kind of invariance| it really only depends on
G. Any component with non-zero
parity will be the desired component.
Denition. Suppose F is a facet of P and R is a ridge of P that is a facet of F .
Let (G; F; R) denote the number of nodes  of the nerve graph G in the facet F
such that jL() \
Similarly if K is any (d 1)-subset of L(F ), let (G; F; K) denote the number
of nodes  of the graph G in the facet F such that jL() \
If
G is a connected component of G, dene (
G; F; R) and (
G; F; K) similarly
using
G instead of G.
Thus (G; F; R) (resp. (
G; F; R)) counts non-degenerate full cells of type (I)
from GF (resp.
GF ) in the facet F , for all
ags F of P such that
It is easy to show that the parity of (G; F; R) is independent
of both F and R:
Theorem 22. Given any
ag F of P , suppose
Then
(G; F; R)  1:
Proof. Consider the subgraph contains simplices of dimension (d 1) or lower. This
subgraph must be a collection of loops or paths (since GF is) whose endpoints (even
number of them) are non-degenerate full cells in either F 1 or F d 1 . But Sperner's
lemma in 1-dimension (or simple inspection) shows that the number of full cells in
must be odd. Hence the number of non-degenerate full cells of GF that meet
must be odd as well.
The next two theorems show that for connected components
G of G, the parity
of (
G; F; R) is also independent of F and R. This fact does not follow directly
from Theorem 22 since we do not know that endpoints of GF for dierent
ags are
connected in
G. To establish this we need to trace connected paths in the nerve
graph G rather than the
ag graph GF .
Lemma 23. Let
G be a connected component of G. Suppose that R; R 0 are ridges
of P and F a facet of P such that R; R 0 are both facets of F . Then
G; F; R)  (
G; F; R 0
A POLYTOPAL SPERNER'S LEMMA 17
Proof. First assume that R and R 0 are \adjacent" ridges sharing a common facet
C (it has dimension d 3, if you are keeping track). We claim that
A;x
G;
where x runs over all labels in L(F ) that are not in L(C) and A runs over all (d 2)-
subsets of L(C). (Here we write A[ x instead of A[ fxg to reduce notation.) The
above sum holds because it only counts fully-labelled simplices  from
G in F that
contain a (d 2)-subset A of L(C), and every such  appears exactly twice in this
counted once each in (
G; F; A [ a) and in
G; F; A [ b).
On the other hand, if x is not the label set of any ridge of P , then any
fully-labelled simplex on the boundary of P that contains K must be contained in
the facet F . Since K is of size d 1, by Lemma 11, we see that (
G; F; K)  0
because there is an even number of endpoints of paths in GK , and such paths are
connected subgraphs of the connected graph
G.
Thus the only terms surviving the above sum correspond to label sets of the two
ridges R; R 0 that are facets of F and share a common face C, i.e.,
G;
G;
which yields the desired conclusion for neighboring ridges R, R 0 .
Since any two ridges of a facet F are connected by a chain of adjacent ridges,
the general conclusion holds.
Lemma 24. Let
G be a connected component of G. Let F; F 0 be adjacent facets of
the polytope P bordering on a common ridge R. Then
G; F; R)  (
G;
Proof. Let R denote the ridge common to both F and F 0 . Let K be any non-degenerate
subset of L(R) of size (d 1), i.e., K is not a subset of F i for i <
(d 2). Consider the derived graph GK . By Lemma 11, this graph consists of
paths connecting full cells from
G on the boundary of P that contain the label set
K. Since these paths are connected subgraphs of
G, there is an even number of
endpoints of these paths in
G.
On the other hand, because of the Sperner labelling, all such endpoints must lie
in facets of P that contain R. There are exactly two such facets, F and F 0 . Hence
G;
G;
which produces the desired conclusion.
Theorem 25. Let
G be a connected component of G. The parity of (
G; F; R) is
independent of F and R.
Proof. Since all facet-ridge pairs (F; R) are connected by a sequence of adjacent
facets and ridges, the statement follows from Lemmas 23 and 24.
Hence we may dene the parity of
G to be (
G; F; R) for any facet-ridge
Similarly, dene the parity of G to be (G)  (G; F; R) for any facet-
ridge pair (F; R), which is well-dened and equal to 1 in light of Theorem 22. Now
we may prove
J. A. DE LOERA, E. PETERSON, AND F. E. SU
Theorem 26. If P is an (n; d)-polytope, there is some component
G of G which
carries all labels of P .
Proof. Fix some
ag F of P , and let
(G; F; R) is the sum of (
G; F; R) over all connected components
G of G, it follows
that (G)
connected components
G of G. Moreover, Theorem
22 shows that (G)  1.
Hence there must be some
G such that (
G carries the labels
in L(R). Since the
ag F was arbitrary,
G must carry all labels of P .
This concludes our alternate\path-following" proof of Theorem 1, because the
(n d) count follows immediately from Theorems 26 and 17, while the covering
property follows (as before) from Proposition 4.
5. conclusion
As applications of Theorem 1, we prove the corollaries mentioned in the intro-
duction, and make some further remarks.
Corollary 2 follows directly from the degree and covering arguments in the non-constructive
proof of Section 2 and the fact that stacked polytopes have triangulations
of size (n d) [11].
Corollary 3, proved below, is stronger than the version stated in [10], which
does not mention the covering property of the full cells, nor their cardinality. That
weaker version follows also from the combinatorial results of Freund in [6] (in particular
his Theorem 4). In fact we should note the similar
avor of Freund's results
to our theorem although he considers triangulations of polytopes with the number
of labels equal to the number of facets (not vertices). His results seem to imply a
\dual" version of our polytopal Sperner but without an estimate of how many full
cells exist.
Proof of Corollary 3. Let C j , be the closed sets in the statement. Consider
an innite sequence of triangulations T k of the polytope P with the property
that the maximal diameter of their simplices tends to zero as k goes to innity. For
each triangulation, we label a vertex y of T k with ng j y 2
g. This is clearly a Sperner labelling.
By Theorem 1, each triangulation T k targets a collection of simplices of P corresponding
to full cells in T k . There are only nitely many possible collections (since
they are subsets of the set of all simplices of P ), and because there are innitely
many T k , some collection C of simplices must be targeted innitely many times
by a subsequence T k i
of T k . By Theorem 1, this collection C is a cover of P and
therefore has at least c(P ) elements.
For each simplex  in C, choose one full cell  i in T k i
that shares the same label
set. The  i form a sequence of triangles decreasing in size. By the compactness of
subsequence of these triangles converges to a point, which (by the labelling
rule) must be in the intersection of the closed sets C j with j 2 L().
Thus given a point choose any simplex  of C that contains P (since C
is a cover of P ), and let J L(). Then the above remarks show that J p satises
the conditions in the conclusion of the theorem. Moreover, there are at least c(P )
dierent such subsets, one for each  in C.
We remark that in the statement of Theorem 1, the full cells not only correspond
to a cover of the polytope P but, in fact, to a face-to-face cover. While this is not
A POLYTOPAL SPERNER'S LEMMA 19
apparent from the rst proof of Theorem 1, it may be seen from the second proof;
in particular, the adjacencies in full cell graph G 0 indicate how the simplices of the
cover meet face-to-face. Thus the subsets in Corollary 1 also satisfy this property.
We close with a couple of questions. For a specic polytope P , dene the pebble
number p(P ) to be the size of its largest pebble set. The (n d) lower bound
of Theorem 1 is tight, achieved by stacked polytopes whose vertices are assigned
dierent labels. But for a specic polytope P , the arguments of Section 2 show
that the lower bound (n d) can be improved to p(P ). What can be said about
the value of p(P )?
We can provide at least two upper bounds for this number. On one hand p(P )
c(P ), because for a maximal pebble set, at most one pebble lies in each simplex of
a minimal size cover. On the other hand, consider the simplex-chamber incidence
introduced in [1]. As the columns correspond to chambers a pebble
selection is essentially a selection of a \row-echelon" submatrix; therefore the rank
of M is an upper bound on the size of pebble sets. Our pebble construction gives
an algorithm for selecting an explicit independent set of columns of M (although
this may not always be a basis).
A related question is: for a specic polytope P , how can one determine the
minimal cover size c(P )? Although Corollary 2 gives a general sharp lower bound
for all polytopes, we know that sometimes minimal covers are much larger for
specic polytopes, such as for cubes (as the volume arguments in [15] show). Also
note that the minimal cover may be strictly smaller than the minimal triangulation
(an example is contained in [3]).
Finding other explicit constructions of pebble sets (besides our \facet-pivoting"
construction of Section 2) that work for specic polytopes may shed some light on
these questions.



--R

Combinatorial bases in systems of simplices and chambers
Hungarica
Minimal simplicial dissections and triangulations of convex 3-polytopes
On the Sperner lemma

Combinatorial Analogs of Brouwer's Fixed-Point Theorem on a Bounded Polyhedron

Ein Beweis des Fixpunktsatzes f
Simplicial Approximation of Fixed Points
Intersection theorems on polytopes
On triangulations of the convex hull of n points
The Approximation of Fixed Points of a Continuous Mapping
Seifert and Threlfall: A Textbook of Topology

A lower bound for the simplexity of the n-cube via hyperbolic volumes
Neuer Beweis f
Sperner's lemma in fair division



--TR
Combinatorial analogs of Brouwer''s fixed-point theorem on a bounded polyhedron
Duality and minors of secondary polyhedra
Combinatorial bases in systems of simplices and chambers
A lower bound for the simplexity of the <italic>n</italic>-cube via hyperbolic volumes
Extremal Properties for Dissections of Convex 3-Polytopes

--CTR
Frdric Meunier, Sperner labellings: a combinatorial approach, Journal of Combinatorial Theory Series A, v.113 n.7, p.1462-1475, October 2006
Timothy Prescott , Francis Edward Su, A constructive proof of Ky Fan's generalization of Tucker's lemma, Journal of Combinatorial Theory Series A, v.111 n.2, p.257-265, August 2005
sperner's lemma;path-following;polytopes;simplicial algorithms