Also available at http://amc.imfm.si
ARS MATHEMATICA CONTEMPORANEA 1 (2008) 99–111
Hypercube Embeddings of Wythoffians
Michel Deza †
LIGA, École Normale Supérieure, 45 rue d’Ulm, 75005 Paris, France
Mathieu Dutour Sikirić ‡
Rudjer Bošković Institute, Bijenička 54, 10000 Zagreb, Croatia
Sergey Shpectorov §
School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT,
United Kingdom
Received 15 August 2007, accepted 18 August 2008, published online 22 August 2008
Abstract
The Wythoff construction takes a d-dimensional polytope P , a subset S of {0, . . . , d}
and returns another d-dimensional polytope P (S). If P is a regular polytope, then P (S)
is vertex-transitive. This construction builds a large part of the Archimedean polytopes and
tilings in dimension 3 and 4.
We want to determine, which of those Wythoffians P (S) with regular P have their skele-
ton or dual skeleton isometrically embeddable into the hypercubes Hm and half-cubes 12Hm.
We find six infinite series, which, we conjecture, cover all cases for dimension d > 5 and
some sporadic cases in dimension 3 and 4 (see Tables 1 and 2).
Three out of those six infinite series are explained by a general result about the embedding
of Wythoff construction for Coxeter groups. In the last section, we consider the Euclidean
case; also, zonotopality of embeddable P (S) are addressed throughout the text.
Keywords: Coxeter group, embedding.
Math. Subj. Class.: 20F55
†Partly supported by JAIST, Japan.
‡Partly supported by the Croatian Ministry of Science, Education and Sport under contract 098-0982705-2707.
§Partly supported by an NSA grant.
E-mail addresses: Michel.Deza@ens.fr (Michel Deza), mdsikir@irb.hr (Mathieu Dutour Sikirić),
s.shpectorov@bham.ac.uk (Sergey Shpectorov)
Copyright c© 2008 DMFA – založništvo
100 Ars Mathematica Contemporanea 1 (2008) 99–111
1 Wythoff kaleidoscope construction
A flag in a poset is an arbitrary completely ordered subset. We say that a connected posetK is
a d-dimensional complex (or, simply, a d-complex) if every maximal flag in K has size d+ 1.
In a d-complex K every element x can be uniquely assigned a number dim(x) ∈ {0, . . . , d},
called the dimension of x, in such a way, that the minimal elements ofK have dimension zero
and dim(y) = dim(x) + 1 whenever x < y and there is no z with x < z < y.
The elements of a complex K are called faces, or k-faces if the dimension of the face
needs to be specified. Furthermore, 0-faces are called vertices and d-faces (maximal faces)
are called facets. If we reverse the order on K then the resulting poset K∗ is again a d-
complex, called the dual complex. Clearly, the vertices of K∗ are the facets of K and, more
generally, the dimension function on K∗ is given by dim∗(x) = d− dim(x).
We will often use the customary geometric language. If x < y and dim(x) = k, we will
say that x is a k-face of y.
A d-complex is a polytope if every submaximal flag (that is, a flag of size d) is contained
in exactly two maximal flags. In the polytopal case, 1-faces are called edges, because each of
them has exactly two vertices. Starting from the next section we will deal exclusively with
polytopes. The skeleton of a polytope K is the graph formed by all vertices and edges of K.
For a flag F ⊂ K define its type as the set t(F ) = {dim(x)|x ∈ F}. Clearly, t(F ) is a
subset of ∆ = {0, . . . , d} and, reversely, every subset of ∆ is the type of some flag.
Let Ω be the set of all nonempty subsets of ∆ and fix an arbitrary V ∈ Ω. For two subsets
U,U ′ ∈ Ω we say that U ′ blocks U (from V ) if for all u ∈ U and v ∈ V there is a u′ ∈ U ′,
such that u ≤ u′ ≤ v or u ≥ u′ ≥ v. This defines a binary relation on Ω, which we will
denote as U ′ ≤ U . We also write U ′ ∼ U if U ′ ≤ U and U ≤ U ′, and we write U ′ < U if
U ′ ≤ U and U 6≤ U ′.
It is easy to see that ≤ is reflexive and transitive, which implies that ∼ is an equivalence
relation. Let [U ] denote the equivalence class containing U . It will be convenient for us to
choose canonic representatives in equivalence classes. It can be shown that if U ∼ U ′ then
U ∩U ′ ∼ U ∼ U ∪U ′. This yields that every equivalence classX contains a unique smallest
(under inclusion) subsetm(X) and unique largest subsetM(X). IfX = [U ] then m(X) and
M(X) can be specified as follows: m(X) is the smallest subset of U that blocks U , while
M(X) is the largest subset of ∆ that is blocked by U . The subsets m(X) will be called the
essential subsets of ∆ (with respect to V ). Let E = E(V ) be the set of all essential subsets
of ∆. Clearly, the above relation< is a partial order onE. Also, V ∈ E and V is the smallest
element of E with respect to <.
We are now ready to explain the Wythoff construction. Naturally, our description is equiv-
alent to the one given in [4] and [5], that generalized the original paper [28]. Other relevant
reference to the subject are [17] and [24]. Suppose K is a d-complex and let ∆, Ω, V , ≤, and
E be as above. The Wythoff complex (or Wythoffian) K(V ) consists of all flags F such that
t(F ) ∈ E. For two such flags F and F ′, we have F ′ < F whenever t(F ′) < t(F ) and F ′ is
compatible with F (that is, F ∪F ′ is a flag). It can be shown that K(V ) is again a d-complex
and that dim(F ) = d+ 1− |M([t(F )])|. It can also be shown that if K is a d-polytope then
K(V ) is again a d-polytope for all V . For a concrete Euclidean realization of such polytopes,
see [13].
Since there are 2d+1 − 1 different subsets V , there are, in general, 2d+1 − 1 different
Wythoffians constructed from the same complexK. It is easy to see thatK(V ) = K∗(d−V ),
where d − V = {d − v|v ∈ V }. This means that the dual complex does not produce new
Wythoffians. Furthermore, in the case of self-dual complexes (that is, where K ∼= K∗), this
M. Deza, M. Dutour Sikirić, S. Shpectorov: Hypercube Embeddings of Wythoffians 101
reduces the number of potentially pairwise non-isomorphic Wythoffians to 2d + 2d
d−1
2 e − 1.
Some of the Wythoffians are, in fact, familiar complexes. First of all, K({0}) = K and
K({d}) = K∗. Furthermore, K({1}) is also known as the median complex Med(K) of K
and the dual of K(∆) is known as the order complex of K (see [26]). We will call K(∆) the
flag complex of K. Thus, the order complex is the dual of the flag complex.
Since in this paper we are going to deal with the skeletons of K(V ) and K(V )∗ (in the
polytopal case), we need to understand elements of K(V ) of types 0, 1, d − 1, and d. Since
V is the unique smallest essential subset, the vertices (0-faces) of K(V ) are the flags of type
V . For a flag F to be a 1-face of K(V ), U = t(F ) must have the property that M([U ])
misses just one dimension k from ∆. Clearly, k must be in V . Now U = Uk can be readily
computed. Namely, Uk is obtained from V by removing k and including instead the neighbors
of k (that is, k − 1 and/or k + 1). Thus, K(V ) has exactly |V | types of 1-faces. Turning to
the facets (d-faces), we see that, for F to be a facet of K(V ), we need that U = t(F ) be an
essential subset of size one, such that M([U ]) = U . The latter condition can be restated as
follows: U should block no other 1-element set. From this we easily obtain that the relevant
sets U = {k} are those for which k = 0 (unless V = {0}), k = d (unless V = {d}), or
min(V ) < k < max(V ). Finally, if F is a (d−1)-face then U = t(F ) is essential of size one
or two and M([U ]) is of size exactly two. We will not try to make here a general statement
about all such subsets U . However, in the concrete situations below, it will be easy to list
them all.
2 Archimedean Wythoffians: d = 3, 4
In this section we start looking at particular examples of Wythoffians, namely, at the Archi-
medean Wythoffians. These polytopes come by the Wythoff construction from the regular
convex polytopes. A complex (in particular, a polytope) is called regular if its group of
symmetries acts transitively on the set of maximal flags. Convex polytopes are the ones
derived from convex hulls H of finite sets of points in Rd. (We assume that the initial set of
points contains d+ 1 points in general position; equivalently, the interior of H is nonempty.)
The faces of the polytope are the convex intersections of the boundary ofH with proper affine
subspaces of Rd. In particular, the polytope is (d−1)-dimensional, rather than d-dimensional.
It is well-known that the regular convex polytopes fall into four infinite series: regular
p-gon, simplices αd, hyperoctahedra βd, and hypercubes γd; and five sporadic examples: the
icosahedron and dodecahedron for d = 3, and the 24-cell, 600-cell, and 120-cell for d = 4.
The half-cube graph 12Hm (respectively Johnson graph J(m,n)) is the graph formed by
all x ∈ {0, 1}m such that
∑m
i=1 xi is even (respectively equal n) with two vertices adjacent
if their Hamming distance is 2.
We are interested in the following
Main Question: Which Archimedean Wythoffians have skeleton graph or dual skeleton graph
isometrically embeddable, for a suitable m, in the hypercube graph Hm or half-cube graph
1
2Hm?
Recall ([1, 12, 9, 25, 8] and books [7, 6]) that a mapping φ from a graph Γ to a graph
Γ′ is an isometric embedding if dΓ′(φ(u), φ(v)) = dΓ(u, v) for all u, v ∈ Γ. For brevity,
we will often shorten “isometric embedding” to just “embedding”. Notice that Hm is an
isometric subgraph of 12H2m, which means that every graph isometrically embeddable in a
hypercube is also embeddable in a half-cube. There is also an intermediate class of graphs—
those that are embeddable in a Johnson graph J(m,n). A graph is said to be hypermetric if
102 Ars Mathematica Contemporanea 1 (2008) 99–111
its path-metric satisfies the inequality∑
1≤i<j≤n
bibjdG(i, j) ≤ 0
for any vector b ∈ Zn with
∑
i bi = 1. In the special case, when b is a permutation of
(1, 1, 1,−1,−1, 0, . . . , 0), the above inequality is called 5-gonal. The validity of hypermetric
inequalities is necessary for embeddability but not sufficient: an example of hypermetric, but
not embeddable graph K7 − C5 (amongst those, given in Chapter 17 of [7]).
Below, when we state our results on embeddability of the skeleton graphs Γ, we will
indicate the smallest class in the above hierarchy, containing Γ.
We remark that γd is dual to βd, which means that they produce the same Wythoffians.
Thus, one can skip the case K = γd altogether. Similarly, we can skip the cases where K is
the dodecahedron, since the latter is dual to the icosahedron, and the 120-cell, since it is dual
to the 600-cell.
In the remainder of this section we state the results of a computer calculation carried out
in the computer algebra system GAP [11].
We start with the case d = 3. In this case K is 2-dimensional, that is, K is a map (and so,
we switch to the notationM = K). It is easy to see thatM(V ) with V ={0}, {0, 1}, {0, 1, 2},
{0, 2}, {1}, {1, 2}, and {2} correspond, respectively, to the following maps: original mapM,
truncatedM, truncated Med(M), Med(Med(M)), Med(M), truncatedM∗ andM∗.
In Table 1 we give a complete answer to our Main Question in the case d = 3. The table
lists all Archimedean Wythoffians and dual Wythoffians, whose skeleton graph is embed-
dable. The details of the embedding, such as the dimension of the embedding and whether
or not it is equicut, are also provided. Recall that an embedding of a graph Γ in a hyper-
cube is called equicut if each cut on Γ, produced by a coordinate of the hypercube, splits Γ
in half. An embedding is called q-balanced if each coordinate cut on Γ has parts of sizes q
and |Γ| − q. We will indicate in the table whether the embedding is equicut, q-balanced, or
neither. Finally, for brevity, we truncated in the table the word “truncated” to just “tr”.
A striking property of this table is that it contains all possible Wythoffians (all five regular
polytopes and 11 of the 13 Archimedean polytopes; missing are the Snub Cube and Snub
Dodecahedron, which are not Wythoffian). Furthermore, for each of these polytopes, exactly
one of the skeleton and the dual skeleton is embeddable.
This nice picture does not extend to the case d = 4, where far fewer embeddings exist.
Our Table 2 gives a complete answer to the Main Question.
Notice that the total number of Archimedean Wythoffians for d = 4 is 45, see [3, 18, 19].
Thus, Table 2 indicates that the embeddable cases become more rare as d grows, and that,
likely, there are only finitely many infinite series of embeddings. Furthermore, Tables 1 and
2 lead us to a number of concrete conjectures about possible infinite series of embeddings.
In the next section we resolve those conjectures in affirmative by constructing the series and
verifying the embedding properties.
We conclude this section with some further remarks about the embeddings in Tables 1
and 2. The majority of these embeddings are unique. The only exception is the Tetrahedron
α3, whose skeleton, the complete graphK4, has two isometric embeddings. We also checked
that all the skeleton graphs for d = 3, that turn out to be non-embeddable, violate, moreover,
the so-called 5-gonal inequality.
M. Deza, M. Dutour Sikirić, S. Shpectorov: Hypercube Embeddings of Wythoffians 103
Embeddable Wythoffian n embedding equicut?
Tetrahedron= α3({0}) = α3({2}) 4 = J(4, 1); = 12H3 q = 1; yes
Octahedron= β3({0}) = α3({1}) 6 = J(4, 2) yes
Cube= β3({2}) = β3({0})∗ 8 = H3 yes
Icosahedron= Ico({0}) 12 1
2
H6 yes
Dodecahedron= Ico({2}) 20 1
2
H10 yes
(tr Tetrahedron)∗ = α3({0, 1})∗ = α3({1, 2})∗ 8 12H7 no
(Cuboctahedron)∗ = β3({1})∗ = α3({0, 2})∗ 14 H4 yes
(tr Cube)∗ = β3({1, 2})∗ 14 J(12, 6) no
Rhombicuboctahedron= β3({0, 2}) 24 J(10, 5) yes
tr Octahedron= β3({0, 1}) = α3({0, 1, 2}) 24 H6 yes
(tr Icosahedron)∗ = Ico({0, 1})∗ 32 1
2
H10 yes
(Icosidodecahedron)∗ = Ico({1})∗ 32 H6 yes
(tr Dodecahedron)∗ = Ico({1, 2})∗ 32 1
2
H26 no
tr Cuboctahedron= β3({0, 1, 2}) 48 H9 yes
Rhombicosidodecahedron= Ico({0, 2}) 60 1
2
H16 yes
tr Icosidodecahedron= Ico({0, 1, 2}) 120 H15 yes
Table 1: Embeddable Archimedean Wythoffians for d = 3.
3 Relation with Coxeter groups
A group W is a Coxeter group if it is a group generated by a set S = {s0, . . . , sd−1} with the
elements si satisfying to the relations s2i = 1 and (sisj)
mij = 1 with mij ≥ 2. We refer to
[14] for all facts used in this Section.
One can encode the matrix W by a Coxeter graph on vertices {0, . . . , d − 1} with two
edges being adjacent if mij ≥ 3.
The group is called irreducible if the Coxeter graph is connected. The irreducible finite
Coxeter groups are classified and denoted by Ad, Bd, Dd, E6, E7, E8, F4, H3, H4, I2(p) (see
[14, page 34]). A Coxeter group is the symmetry group of a regular polytope if and only if its
Coxeter graph is a path. A finite Coxeter group W can be represented as a group of isometries
of Rd with the si being reflexions and their hyperplanes Hi delimiting a fundamental domain
S.
We now define the Wythoff construction for Coxeter groups. An algebraic way is ex-
plained in [15] but we choose an easier and more geometric way following [20]. Take a finite
Coxeter group W with a fundamental simplex S. If T ⊆ ∆ = {0, . . . , d − 1}, then we take
a point v ∈ S such that v ∈ Hi if and only if i /∈ T . The Wythoff construction W(T ) is then
defined as the convex hull of the orbit W(v). The orbit W(v) is on the sphere and in [20] it is
proved, using Delaunay polytopes, that the combinatorics of W(T ) depends only on W and
T .
If T = {0, . . . , d − 1}, then W(T ) is the flag complex of W. Its skeleton is the Cayley
graph Cay(W, S) of W obtained from the canonical generating set S = {s0, . . . , sd−1}.
Given a Coxeter group W, denote by T the set of elements, which are conjugate to an
element of S.
Proposition 1. If W is a finite Coxeter group, S is its canonical generating set, then the
Cayley graph Cay(W, S) is isometrically embeddable into H|T |.
Proof. Any finite Coxeter group can be realized as a group of isometries of a space Rd. The
104 Ars Mathematica Contemporanea 1 (2008) 99–111
Embeddable Wythoffian n embedding equicut?
α4 = α4({0}) = α4({3}) 5 = J(5, 1) q = 1
β4 = β4({0}) 8 = 12H4 yes
γ4 = β4({3}) = β4({0})∗ 16 = H4 yes
α4({1}) = α4({2}) 10 = J(5, 2) q = 4
α4({0, 3})∗ 30 H5 yes
β4({0, 3}) 64 12H12 yes
α4({0, 1, 2, 3}) 120 H10 yes
β4({0, 1, 2}) = 24− cell({0, 1}) = 24− cell({2, 3}) 192 H12 yes
β4({0, 1, 2, 3}) 384 H16 yes
24− cell({0, 1, 2, 3}) 1152 H24 yes
600− cell({0, 1, 2, 3}) 14400 H60 yes
Table 2: Embeddable Archimedean Wythoffians for d = 4.
W |T | regular polytope
Ad d(d+ 1)/2 αd
Bd d
2 γd or βd
Dd d(d− 1) none
E6 36 none
E7 63 none
E8 120 none
F4 24 24-cell
H3 15 Dodecahedron or Icosahedron
H4 60 120-cell or 600-cell
I2(p) p regular p-gon
Table 3: Embeddings of flag complexes of finite irreducible Coxeter groups.
elements of T are realized as reflections and the corresponding hyperplanes realize a plane
arrangement and W acts simply transitively on its cells. By a theorem of Eppstein ([10]),
the graph formed by the cells with two cells adjacent if they share a (d − 1)-dimensional
face, is isometrically embeddable into the hypercube {0, 1}M with M being the number of
hyperplanes, i.e. |T |.
See in Table 3 the dimensions of the hypercube of embeddings with the corresponding
regular polytopes if existing.
This proposition is, certainly, folklore, but we could not find an appropriate reference.
For example, [2] address the 3-dimensional case. Also, in [21], an embedding of finitely
generated Coxeter group into cube complexes is given. But this is a topological embedding,
while our embeddings are isometric.
The above setting can be generalized to affine Coxeter groups W̃. An affine Coxeter group
is a group W̃ obtained by adding a reflection sd along an hyperplane not passing though 0
to a finite Coxeter group W. The group W̃ then has a fundamental domain delimited by
d+ 1 hyperplanes H0, . . . ,Hd. If T̃ denotes the set of classes of parallel hyperplanes of W̃,
then its Cayley graph Cay(W, S) embeds into Z|T̃ | and one has |T̃ | = |T | according to the
nomenclature in [14].
Note also that (see [23, 16]), given a finite Coxeter group of root system R = {r1, . . . ,
M. Deza, M. Dutour Sikirić, S. Shpectorov: Hypercube Embeddings of Wythoffians 105
rN}, the zonotopal polytope [−r1, r1]+· · ·+[−rN , rN ] is, actually, the Wythoff construction
of W on S. It is easy to see that this zonotopal embedding is isometric embedding into H|T |
given in Proposition 1.
4 Infinite series of embeddings
Since in this section we are only interested in the infinite series of embeddings, we restrict
ourselves to the cases K = αd and βd. These polytopes can be described in combinatorial
terms as follows: The faces of αd are all proper nonempty subsets of the set {1, . . . , d+ 1}.
The order on αd is given by containment, and the dimension of the faceX is |X|−1. Clearly,
αd has
(
d+1
k+1
)
faces of dimension k. The faces of βd are the sets {±i1, . . . ,±ik}, where the
signs are arbitrary and {i1, . . . , ik} is a nonempty subset of {1, . . . , d}. Again, the order is
defined by containment and the dimension of a face X is |X| − 1. Thus, βd has 2k+1
(
d
k+1
)
faces of dimension k.
Two infinite series of embeddable skeletons are well-known:
1. The skeleton of αd({0}) = αd({d− 1}) is the complete graph Kd+1, which coincides
with J(d+ 1, 1).
2. The skeleton of βd({d − 1}) = βd({0})∗ = γd coincides with the hypercube graph
Hd.
The first of these embeddings can be generalized as follows.
Proposition 2. If k ∈ {0, . . . , d − 1} then the skeleton of αd({k}) coincides with J(d +
1, k + 1).
Proof. We refer to the discussion of the vertices and edges at the end of Section 1. According
to that discussion, the vertices of αd({k}) are the k-faces, that is, the subsets of {1, . . . , d+1}
of size k + 1. Furthermore, the only types, leading to edges, are k − 1 (if k > 1) and k + 1.
This means that two vertices are on an edge if and only if their symmetric difference, as sets,
has size two.
Note that the above isomorphism is not quite new, see for example [22, page 18] and [27,
page 8-9].
The above result explains a number of entries in Tables 1 and 2. We now turn to the series
showing up in line 14 of Table 1 and in line 8 of Table 2.
Proposition 3. The skeleton of αd({0, d − 1})∗ coincides with Hd+1 with two antipodal
vertices removed. It is an isometric subgraph of Hd+1.
Proof. Again we refer to the discussion in Section 1. When V = {0, d − 1}, every one-
element subset U of ∆ = {0, . . . , d− 1} has the property that M([U ]) = U . This means that
all elements of αd(V ) (that is, all nonempty proper subsets of {1, . . . , d + 1}) are vertices
of αd(V )∗. This also means that the types corresponding to edges necessarily have size two.
If U = {a, b} ⊂ ∆ and a < b then M([U ]) = {k | a ≤ k ≤ b}. Therefore, edges of
αd(V )∗ are flags, whose type is of the form {k, k + 1}. Thus, we come to the following
description of the skeleton Γ of αd(V )∗: Its vertices are all nonempty proper subsets of
{1, . . . , d + 1}; two subsets are adjacent when one of them lies in the other and their sizes
differ by one. This matches the well-known definition of Hd+1 as the graph on the set of all
106 Ars Mathematica Contemporanea 1 (2008) 99–111
subsets of {1, . . . , d + 1}. In fact, Γ is Hd+1 with two antipodal vertices (∅ and the entire
{1, . . . , d+ 1}) removed. The last claim is clear.
From Proposition 1, we know that αd({0, . . . , d− 1}) is embeddable into H(d+12 ), which
explains line 16 of Table 1 and line 4 of Table 2. Also βd({0, . . . , d − 1}) is embeddable
into Hd2 , which explains line 6 of Table 1 and line 5 of Table 2. There is an easy connection
between those two embeddings, that is the skeleton αd−1({0, . . . , d− 2}) is a subcomplex of
the complex βd({0, . . . , d− 1}).
The dual Wythoff polytope in this proposition is, in fact, the zonotopal Voronoi polytope
of the root lattice Ad. Note that the polytope αd({0, . . . , d − 1}) is known as the permuta-
hedron. It is the zonotopal Voronoi polytope of the dual root lattice A∗d. Remark also that
βd({0, . . . , d− 1}) is not the Voronoi polytope of a lattice, since its number of vertices, 2dd!,
is greater than (d+ 1)!.
The following embedding series leaves trace in Tables 1 and 2 in lines 16 and 7, respec-
tively.
Proposition 4. The skeleton of βd({0, . . . , d−2}) is isomorphic to the skeleton of Dd({0, . . . ,
d− 1}), which is isometrically embeddable into Hd(d−1).
Proof. We define the following linear functions:
fi(x) = xi+1 − xi+2, for 0 ≤ i ≤ d− 2, and fd−1(x) = xd.
Denote by Hi the hyperplane defined by fi(x) = 0 and by si the reflection along the hyper-
plane Hi. Denote by S the simplex defined by the inequalities fi(x) ≥ 0. The reflections
si generate the Coxeter group Bd of fundamental domain S, whose corresponding regular
polytope is βd.
One way to compute βd({0, . . . , d−2}) is to take a vertex v ∈ S∩Hd−1 with v /∈ Hi for
i ≤ d−2. The polytope obtained as convex hull of the orbit Bd(v) is then βd({0, . . . , d−2}).
Now, the key argument is that S ∪ sd−1(S) is also a simplex S ′ defined by the inequalities
f ′i(x) = fi(x) ≥ 0, for 0 ≤ i ≤ d− 2, and f ′d−1(x) = xd−1 + xd ≥ 0.
Those inequalities define hyperplanes which themselves define orthogonal reflections and
so, a finite Coxeter group named Dd. The point v lies inside of S ′ so, the skeleton of
βd({0, . . . d− 2}) is, actually, the skeleton of Dd({0, . . . , d− 1}).
The isometric embedding follows from Proposition 1 and Table 3.
Another way to see the embedding βd({0, . . . , d− 2}) from βd({0, . . . , d− 1}) by pro-
jection, that is removing dimensions and considering the obtained graph. The idea here is
simply to remove the coordinates corresponding to the planes xi = 0.
For d = 3, the polytope βd({0, . . . , d − 2}) is the zonotopal Voronoi polytope of the
lattice A∗3. For d = 4 and higher, it is a zonotope but it is not the Voronoi polytope of a
lattice, since the number of vertices, 2d−1d!, is greater than (d+ 1)!.
The examples in lines 8 and 9 of Tables 1 and 2, respectively, suggest that the skeleton of
βd({0, d − 1}) might be embeddable in a half-cube for all d. The next proposition demon-
strates that the actual situation is somewhat more complicated. We first need to recall some
further concepts.
M. Deza, M. Dutour Sikirić, S. Shpectorov: Hypercube Embeddings of Wythoffians 107
Suppose Γ is a graph and φ is a mapping from Γ to a hypercube Hm. We say that φ
is an embedding with scale λ if for all vertices x, y ∈ Γ the distance in Hm between φ(x)
and φ(y) (the Hamming distance) coincides with λdΓ(x, y). Clearly, isometric embeddings
in a hypercube are scale 1 embeddings, while isometric embeddings in a half-cube are scale
2 embeddings. A graph is an `1-graph if it has a scale λ embedding into a hypercube for
some λ. A finite rational-valued metric embeds isometrically into some space `k1 if and only
if it is scale λ embeddable into Hm for some λ and m. See [1, 25, 8, 7, 6] for details on
`1-embedding.
Proposition 5. The skeleton of βd({0, d− 1}) is an `1-graph for all d. However, if d > 4, it
is not an isometric subgraph of a half-cube.
Proof. Let Γ be the above skeleton graph. The vertices of this graph can be identified with
all tuples of the form (k; ε1, . . . , εd), where 1 ≤ k ≤ d and the signs εi are arbitrary. Thus,
there are d2d vertices. The edges of Γ arise in two ways: (1) We have that (i; ε1, . . . , εd) is
adjacent to (j; ε1, . . . , εd) for all i 6= j. (2) We also have that (i; ε1, . . . , εd) is adjacent to
(i; ε1, . . . , εj−1,−εj , εj+1 . . . , εd), again for all i 6= j.
Let Γ1 be the graph whose vertices are all tuples (ε1, . . . , εd), εi = ±1, and where two
tuples are adjacent whenever they differ in just one entry. Let Γ2 be the graph whose vertices
are ±k, 1 ≤ k ≤ d, and where vertices s and t are adjacent whenever |s| 6= |t|. It is clear
that Γ1 is isomorphic to the hypercube Hd, while Γ2 is isomorphic to the hyperoctahedron
graphKd×2 (complete multipartite graph with d parts of size two; also known as the cocktail-
party graph). Mapping the vertex (k; ε1, . . . , εd) of Γ to the ordered pair ((ε1, . . . , εd), εkk)
defines an embedding φ of Γ into the Cartesian product graph Γ1 × Γ2. It is easy to see
that this embedding is isometric. Since Γ projects surjectively onto both Γ1 and Γ2, we can
now determine the Graham-Winkler Cartesian product graph for Γ (cf. [12]). Namely, that
Cartesian product graph has d complete graphs of size two and the cocktail-party graph Γ2 as
its factors. (We assume that d > 2.) It follows from [25] that Γ has a scale λ embedding in
a hypercube if and only if every factor has. In our case, every factor is an `1-graph, hence Γ
is an `1-graph, too. Furthermore, the cocktail-party graph Kd×2 with d > 4 requires λ > 2,
which proves the second claim of the proposition.
The infinite series exhibited in this section explain a majority of the examples from Tables
1 and 2, including, in fact, all examples from Table 2. This allows us to make the following
conjecture.
Conjecture 6. If Γ is the skeleton of the Wythoffian K(V ) or of the dual Wythoffian K(V )∗,
where K is a regular convex polytope, and Γ is isometrically embeddable in a half-cube, then
Γ can be found either in Table 1, Table 2, or in one of the infinite series discussed in this
section.
5 From the hypercubes to the cubic lattices?
The above conjecture shows one direction of possible further research. Another possibility
is extending the results of this paper to cover the case of infinite regular polytopes, that is,
regular partitions of the Euclidean and hyperbolic space. In this section we briefly discuss
what is known about the easier Euclidean case.
In the infinite case, instead of embedding the skeleton graphs up to scale into hypercubes
Hm, we embed them into the m-dimensional cubic lattice Zm (including m = ∞) taken
108 Ars Mathematica Contemporanea 1 (2008) 99–111
with its metric `1. Notice that this is a true generalization, because, according to [1], a finite
metric that can be embedded into a cubic lattice, can also be embedded into a hypercube.
All regular partitions of Euclidean d-space (d finite) are known [5]. They consist of
one infinite series δd = δ∗d , which is the partition into the regular d-dimensional cubes, two
2-dimensional ones, (36) (partition into regular triangles) and (63) = (36)∗ (partition into
regular 6-gons), and two 4-dimensional ones, hδ4 (partition into 4-dimensional hyperoctahe-
dra) and hδ∗4 (partition 24-cells). Notice that the latter two partitions are the Delaunay and
Voronoi partitions associated with the lattice D4. In particular, below we use the notation
V o(D4) in place of hδ∗4 .
In the following table we give a complete list of Wythoffians of regular partitions of
the Euclidean plane. We use the classical notation for the vertex-transitive partition of the
Euclidean plane; namely, each partition is identified by its type, listing clock-wise the sizes of
the faces containing a fixed vertex. In particular, the regular partitions of the Euclidean plane
are (44) = δ2, (36), and (63) = (36)∗. In the second column we indicate the embedding. We
put Zm for an embedding with scale one and 12Zm for an embedding with scale two.
Wythoffian embedding
δ2 = δ2({0}) = δ2({1}) = δ2({2}) = δ2({0, 2}) Z2
(36) = (36)({0}) 1
2
Z3
(63) = (36)({2}) = (36)({0, 1}) Z3
(4.82) = δ2({0, 1}) = δ2({1, 2} = δ2({0, 1, 2} Z4
(4.6.12) = (36)({0, 1, 2}) Z6
(3.4.6.4) = (36)({0, 2}) 1
2
Z3
(3.6.3.6)∗ = (36)({1})∗ Z3
(3.122)∗ = (36)({1, 2})∗ 1
2
Z∞
Table 4: Embeddable Wythoffian cases for plane partitions.
All Archimedean Wythoffians or their dual, which are not mentioned in Table 4, are non-
embeddable and, moreover, they do not satisfy the 5-gonal inequality.
In this table we separated the three regular plane partitions from the Archimedean (i.e.,
vertex- but not face-transitive) ones. Notice that, out of the eight Archimedean partitions,
five are Wythoffians. Missing are partitions (32.4.3.4), (33.42) and (34.6). It turns out that
for all regular and Archimedean plane partitions (and in particular, for all our Wythoffians)
exactly one out of itself and its dual is embeddable. In this respect the situation here repeats
the situation for the Archimedean polyhedra for d = 3, see Section 2 and Tables 9.1 and
4.1–4.2 in [6].
We now turn to the next dimension, d = 3. Here we identify the Wythoffians as particular
partitions of the Euclidean 3-space in two ways. First, in column 2 we give the number of
that partition in the list of 28 regular and Archimedean partitions of the 3-space from [6].
Secondly, we identify in column 3 the tiles of the partition. Here, as before, β3 and γ3 are
the Octahedron and the Cube, respectively. Also, “Cbt” stands for the Cuboctahedron and
“Rcbt” stands for the Rhombicuboctahedron. Clearly, “tr” stands for “truncated” and Prism8
is the regular faced 8-gonal prism. In some cases we also indicate the chemical names of the
corresponding partitions. In column 4 we give the details of the embedding. If the particular
Wythoffian is non-embeddable, we put “non 5-gonal” in that column to indicate that it fails
the 5-gonal inequality. The information in column 4 is taken from Table 10.1 from [6].
M. Deza, M. Dutour Sikirić, S. Shpectorov: Hypercube Embeddings of Wythoffians 109
Wythoffian no tiles embedding
δ3 = δ3({0}) = δ3({3}) = δ3({0, 3}) 1 γ3 Z3
δ3({1, 2}) = V o(A∗3) 2 tr β3 Z6
δ3({0, 1, 2}) = δ3({1, 2, 3})=zeolit Linde A 16 γ3, tr β3, tr Cbt Z9
δ3({0, 1, 2, 3})=zeolit ρ 9 Prism8, tr Cbt Z9
δ3({1}) = δ3({2}) = De(J − complex) 8 β3, Cbt non 5-gonal
δ3({0, 1}) = δ3({2, 3})=boride CaB6 7 β3, tr γ3 non 5-gonal
δ3({0, 2}) = δ3({1, 3}) 18 γ3, Cbt, Rcbt non 5-gonal
δ3({0, 1, 3}) = δ3({0, 2, 3})=selenide Pd17Se15 23 γ3, Prism8, tr γ3, Rbct non 5-gonal
Table 5: Wythoffians of regular partitions of the 3-space.
As Table 5 indicates, only eight out of 28 regular and Archimedean partitions of the 3-
space arise as the Wythoffians of the cubic partition δ3.
Finally, in Table 6 we collected some information about the dimensions d ≥ 4.
Wythoffian tiles embedding
δd = δd({0}) = δd({d}) = δd({0, d}) γd Zd
δd({0, 1})=tr δd βd, tr γd non 5-gonal
V o(D4) = V o(D4)({0} 24− cell non 5-gonal
V o(D4)
∗ = V o(D4)({4}) β4 non 5-gonal
V o(D4)({1} = Med(V o(D4)) γ4, Med(24− cell) non 5-gonal
V o(D4)({0, 1}=tr V o(D4) γ4, tr 24− cell Z12
Table 6: Some Wythoffians of regular partitions of the d-space, d ≥ 4.
Notice that again, as in Table 2, few Wythoffians for d = 3 possess embeddings. This
gives hope that there is only a small number of infinite series of embeddings in the Euclidean
case. One of the infinite series is shown in line 1 of Table 6.
Proposition 7. (i) The skeleton graph of the Wythoffian flag complex δd({0, . . . , d}) is iso-
metrically embeddable in Zd2 .
(ii) The skeleton graph of the Wythoffian δd({0, . . . , d − 1}) = δd({1, . . . , d}) is also
isometrically embeddable in Zd2 .
Proof. The situation is completely analogous to the one for βd({0, . . . , d−1}) and βd({0, . . . ,
d−2}) of Proposition 4. We simply add the function fd(x) = 1−x1 and the Coxeter groups
Bd and Dd are replaced, respectively, by C̃d and B̃d (see [14, page 96]). The number of
classes of parallel hyperplanes in G̃ is equal to the number of hyperplanes in G. The result
follows from Table 3.
We think that those tilings are zonotopal but we did not check it.
It appears (see line 4 of Table 4 and line 2 of Table 5) that δd({1, 2}) may have an em-
bedding for all d. In this case, however, we are reluctant to formulate an exact conjecture.
Perhaps, the situation will be more clear when the case d = 4 is completed.
We have already pointed out that only eight out of 28 regular and Archimedean partitions
of the Euclidean 3-space are Wythoffians of δ3. This indicates that, maybe, one needs to
derive Wythoffians from a larger class of Euclidean partitions. The obvious candidates are
the Delaunay and Voronoi partitions of interesting Euclidean lattices, in particular, the root
110 Ars Mathematica Contemporanea 1 (2008) 99–111
lattices. For the case of such lattices themselves (that is, for V = {0} or {d}), see Chapter
11 of [6]. The zonotopal embeddings of V o(Ad) in Zd+1 and V o(A∗d) in Z(d+12 ), correspond
to the zonotopal embeddings of the corresponding tiles from Proposition 1.
It is, of course, also very interesting to consider the Wythoffians of the regular partitions
of the hyperbolic d-space. In fact, in [9] (see also Chapter 3 of [6]), the embeddability was
decided for any regular tiling P of the d-sphere, Euclidean d-space, hyperbolic d-space or
Coxeter’s regular hyperbolic honeycomb (with infinite or star-shaped cells or vertex figures).
The large program will be to generalize it for all Wythoffians of such general P .
References
[1] P. Assouad, M. Deza, Espaces métriques plongeables dans un hypercube: aspects combinatoires,
Annals of Discrete Mathematics 8 (1980), 197–210.
[2] B. Bresar, S. Klavzar, A. Lipovec, B. Mohar, Cubic inflations, mirror graphs, regular maps, and
partial cubes, European Journal of Combinatorics 25 (2004), 55–64.
[3] J.H. Conway, Four-dimensional Archimedean polytopes, Proc. Colloquium on Convexity, Copen-
hagen 1965, Kobenhavns Univ. Mat. Institut (1967), 38–39.
[4] H.S.M. Coxeter, Wythoff’s construction for uniform polytopes, Proc. London Math. Soc. 38, no
2, (1935), 327–339; Reprinted in H.S.M. Coxeter, Twelve geometrical essays, Southern Illinois
University Press, Carbondale, 1968, pp. 40–53.
[5] H. S. M. Coxeter, Regular Polytopes, Dover Publications, New York, 1973.
[6] M. Deza, V. Grishukhin, M. Shtogrin, Scale-Isometric Polytopal Graphs in Hypercubes and Cubic
Lattices, Imperial College Press and World Scientific, 2004.
[7] M. Deza, M. Laurent, Geometry of Cuts and Metrics, Springer–Verlag, Berlin, 1997.
[8] M. Deza, S. Shpectorov, Recognition of `1-graphs with complexity O(nm), or football in a
hypercube, European Journal of Combinatorics 17 (1996), no 2-3, 279–289.
[9] M. Deza, M. Shtrogin, Embedding the graphs of regular tilings and star honeycombs into the
graphs of cubical lattices, in Advanced Study in Pure Mathematics 27, Arrangements - Tokyo
(2000) 73–92.
[10] D. Eppstein, Cubic partial cubes from simplicial arrangements, Electronic Journal of Combina-
torics 13 (2006), no 1, R79.
[11] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.4; 2004, http:
//www.gap-system.org.
[12] R. L. Graham, P. M. Winkler, On isometric embeddings of graphs, Trans. Amer. Math. Soc. 288
(1985), no 2, 527–536.
[13] Z. Har’El, Uniform solutions for uniform polyhedra, Geom. Dedicata 47 (1993), 57–110.
[14] J. E. Humphreys, Reflection groups and Coxeter groups, Cambridge University Press, 1990.
[15] G. Maxwell, Wythoff’s construction for Coxeter groups, J. Algebra 123 (1989), no 2, 351–377.
[16] J. McCammond, http://www.math.ucsb.edu/˜jon.mccammond/courses/spring04/227/notes/
chapter1.pdf
[17] P. McMullen, E. Schulte, Abstract Regular Polytopes, Cambridge University Press, Cambridge,
2002.
[18] M. Möller, 4-dimensionale Archimedische Polytope, Result in Mathematics 46 (2004), no 3-4,
271–360.
M. Deza, M. Dutour Sikirić, S. Shpectorov: Hypercube Embeddings of Wythoffians 111
[19] M. Möller, Vierdimensionale Archimedische Polytope, Dissertation, Univ. Hamburg, Hamburg,
2004, available at http://www.sub.uni-hamburg.de/opus/volltexte/2004/2196/pdf/
Dissertation.pdf.
[20] R. V. Moody, J. Patera, Voronoi domains and dual cells in the generalized kaleidoscope with
applications to root and weight lattices, Canadian Journal of Mathematics 47 (1995), no 3, 573–
605.
[21] G. A. Niblo, L. D. Reeves, Coxeter groups act on CAT(0) cube complexes, J. Group Theory 6
(2003), no 3, 399–413.
[22] I. Pak, When and how to n choose k, in: Randomization methods in algorithm design, DIMACS
Ser. Discrete Math. Theoret. Comput. Sci. 43 (1999), 191–238.
[23] V. Reiner G. M. Ziegler, Coxeter-Associahedra, Mathematika 41 (1994), no 2, 364–393.
[24] R. Scharlau, Geometrical realizations of shadow geometries, Proc. London Math. Soc. 61 (1990),
no 3, 615–656.
[25] S. Shpectorov, On scale embeddings of graphs into hypercubes, European Journal of Combina-
torics 14 (1993), 117–130.
[26] R. Stanley, Enumerative Combinatorics, Cambridge University Press, Cambridge, 1997.
[27] F. Vallentin, Optimal distortion embeddings of distance regular graphs into Euclidean spaces,
Journal Combinatorial Theory, Series B 98 (2008), 95–104.
[28] W. A. Wythoff, A relation between the polytopes of the C600-family, Koninklijke Akademie van
Wetenschappen te Amsterdam, Proceedings of the Section of Sciences 20 (1918), 966–970.