数理解析研究所講究録
第 899 巻 1995 年 114-120

114

Skeletons of some relatives of the n-cube
Antoine DEZA

Michel DEZA$*$$\star$$(\sim\backslash \overline{\mathcal{T}}^{\grave{\backslash }}\Psi^{\backslash })$$(7 \sqrt[\backslash ]{}\vdash\nabla- \overline{\mathcal{T}}^{\grave{\backslash }}\Psi^{\backslash })$$* \ovalbox{\tt\small REJECT}_{\nearrow}\hat{p_{\backslash }}I\ovalbox{\tt\small REJECT}\star\succ\backslash \mp^{l}\Phi I^{\mu,}\mp\Re^{7}\pi^{t}R^{r}|\ovalbox{\tt\small REJECT}\not\equiv R\ovalbox{\tt\small REJECT}+’\frac{\backslash }{\mp}\cdot\neg E_{I}X$$\star 7\overline{7}\sqrt[\backslash ]{}R\mapsto\mp ffl^{p}\pi^{t}\Gamma\tau$Ecole Normale Sup\’erieure, Paris, France

January 1995
Abstract
We study the skeleton of several polytopes related to the n-cube, the halved
n-cube, and the folded n-cube. In particular, the Gale polytope of the n-cube,
its dual and the duals of the halved n-cube and the complete bipartite subgraphs polytope.

1

Introduction

The general references are [2, 6, 12] for polytopes, [4] for graphs and [5] for lattices.
We first recall some basic properties of the cube and the halved cube.
The vertices of the n-cubeare all the characteristic vectors
for$S\subset N=\{1,2, \ldots, n\}$ , that is,for $i\in S$ and otherwise. Withdenoting the size of the symmetric difference of the subsets and $S’$ , two vertices
andare adjacent if and only if $|S\triangle S’|=1$ . The skeleton of is denoted by$H(n, 2)$ and the skeleton of its dual, the cross-polytope, is, which isalso called the Cocktail-Party graph. The diameter of the n-cube and its dual are,respectively, and 2.
The halved n-cube(see Section 8.6 of [6]) is obtained from the n-cubebyselecting the vertex of even cardinality on each edge, that is,is the convex hullof all thecharacteristic vectors
for $S\subset N=\{1,2, \ldots, n\}$ andeven. Twoverticesandare adjacent if and only if $|S\triangle S’|=2$ . The skeleton of the halved
n-cube is denoted by $H(n, 2)$ ; its diameter is.
$\gamma_{n}=[0,1]^{n}$$2^{n}$$\chi_{i}^{s}=1$$\chi^{s}$$0$$|S\triangle S’|$$S$$\chi^{s}$$\chi^{S’}$$\gamma_{n}$$\beta_{n}=\gamma_{n}^{*}$$K_{2\cross n}$$n$$h\gamma_{n}$$\gamma_{n}$$h\gamma_{n}$$2^{n-1}$$\chi^{s}$$\chi^{s}$$|S|$$\chi^{S’}$-$L\frac{n}{2}\rfloor$

115

2Skeleton of the dual halved n-cube
The halved 3-cube is a regular tetrahedron . The halved 4-cube is the simplicial. For $n>4$ , the facets ofpolytope-cube are partitioned into the following
two orbits of its symmetry group $2^{n-1}Sym(n)$ . The orbit
consists of the $2n$ facets
belonging to the facets of the n-cube and defined by the inequalities:$\alpha_{3}$$h\gamma_{4}=\beta_{4}$$h\gamma_{n}$$O_{1}^{n}$for $i\in N$ ,for $i\in N.$$x_{i}\leq 1$$x_{i}\geq 0$

(1)
(2)

The orbit
consists of the
facets cutting off the vertices of odd cardinality
from the n-cube and defined by the inequalities:$2^{n-1}$$O_{2}^{n}$for $A\subset N$ and$\sum_{i=1}^{n}x_{i}(1-2\chi_{i}^{A})\leq|A|-1$

$|A|$

odd.

(3)

The facets defined by the inequalities (1), (2) and (3) are respectively denoted by. Since the symmetries of a polytope preserve adjacency and linear
andindependence, we can describe the properties of its facets by simply considering a
representative facet of each orbit. The facets(here and in the“followingis the simplex
denotes the affine equivalency) and each facet
containing the vertices:
for $i\in A$ .
forand
, is the graph whose nodes
The skeleton of the dual halved n-cube, denoted by, two facets being adjacent if and only if their intersection is a
are the facets offace of codimension 2. This skeleton is given below.
$F_{1}^{i},$$F^{A}$$F_{0}^{i}$$F_{1}^{i}\simeq F_{0}^{i}\simeq h\gamma_{n-1}$$F^{A}$$”\simeq$$\chi^{A\cup\{i\}}$$n$$i\in\overline{A}$$\chi^{A\backslash \{i\}}$$h\gamma_{n}^{*}$$h\gamma_{n}$Lemma 2.1 The facets of; each facet
cocliqueeach $i\in N$ .

$F^{A}$$\overline{K}_{2^{n-1}}$

form, respectively, the cocliqueandis adjacent, either toif $i\in A$ , or to$O_{1}^{n}$$O_{2}^{n}$$\overline{K}_{2n}$$F_{0}^{i}$$F_{1}^{i}$if, and $ihe$$i\in\overline{A}$for

Corollary 2.2 For $n\geq 4$ , the skeleton of the dual halved n-cube is a bipartite graphof diameter 4.
, is half, respectively to
PROOF.
Since the valency of a facet belonging to. On the other hand, the facets
the size of , respectively of , we haveand , having no common neighbour, we get.
$O_{1}^{n}$$O^{1}$$O_{2}^{n}$$F_{1}^{i}$$\delta(h\gamma_{n}^{*})\leq 4$$\delta(h\gamma_{n}^{*})>3$$F_{0}^{i}$$O_{2}^{n}$$\square$Corollary 2.3 The halved n-cube has $n2^{n-2}$ faces of codimension 2 which are all
simplices, that is
is quasi-simplicial. For $narrow\infty,$
is asymptotically simplicial.
$h\gamma_{n}$$h\gamma_{n}$116

Since the number of faces of codimension 2 of a polytope is half of the
PROOF.
total valency of the skeleton of its dual, the result is a straightforward calculation. All, the halved n-cube
faces of codimension 2 being incident to the simplex facets of
is a quasi-simplicial.
$h\gamma_{n}$$\square$3

Gale transform of the n-cube

be a $(2^{n}-n-1)\cross 2^{n}$ matrix which rows form a basis for the space of allLet
is thethe affine dependencies on the vertices of the n-cube. A Gale transform of
points inwhich are the columns of .
collection of the
We consider the matrix induced by the following $2^{n}-n-1$ affine dependencies
on the vertices of :$A$$\gamma_{n}$$R^{2^{n}-n-1}$$2^{n}$$A$$A$$\gamma_{n}$for $T\subset N$ and $|T|\geq 2$ .

$(1-|T|) \chi^{\emptyset}+\sum_{i\in T}\chi^{\{i\}}-\chi^{T}=0$(4)offor $S\subset N$ , we simply
Since each column of corresponds to a vertex
denote by
the vector formed by this column of . For example, the first column
which $2^{n}-n-1$ coordinates arecorresponds toand forms the vectorof, whereis naturally indexed by $T\subset N,$ $|T|\geq 2$ .
A Gale polytope, Gale $(P)$ , of a polytope is the convex hull of a Gale transform
associated to the affine dependencies (4).
of . In the following we consider Gale
is a prism over a tetrahedron; see also Example 5.6 in [3] for
The polytope Gale
relation with Lawrence polytopes. For $n\geq 4$ , we introduce some edges and facets ofin order to compute its diameter and the one of its dual.
Galefor $T\subset N$ and $|T|\geq 2$ are theConsider the following inequalities, where“1indexed by $T\subset N,$ $|T|\geq 2$ .
coordinates of a point in$A$$\chi^{s}$$\gamma_{n}$$A$$v^{s}$$A$$v^{\emptyset}$$\chi^{\emptyset}$$v_{T}^{\emptyset}=(1-|T|)$$R^{2^{n}-n-1}$

$P$

$P$

$(\gamma_{n})$$(\gamma_{3})$$(\gamma_{n})$$x_{T}$$x$$R^{2^{n}-n}$$x_{A\cup\{i\}}-x_{A}\leq 1$

for $|A|=2$ ,for $|A|\geq 3$ and $i\in A$ ,for $|A|=2$ ,,for $|A|\geq 2$ and$2 \sum_{j\in N}x_{\{j\}}-2x_{\{i\}}+(n-1)(x_{N}-1)\leq 0$

for $i\in N$ ,$(e_{5})$for $|A|,$ $|B|\geq 2$ and $2(|A|+|B|)\leq n+3$ .

$(e_{6})$$\sum_{|T|\geq 2}x_{T}-2^{n}(x_{A}+x_{B})\leq 2^{n}-1$$-x_{A}\leq 1$$x_{A\backslash \{i\}}-x_{A}\leq 1$$x_{A}\leq 1$$i\not\in A$$(e_{1})$$(e_{2})$$(e_{3})$$(e_{4})$

117

One can easily check that each of those inequalities induces an edge of Gale
. Moreprecisely,
andinduce the edges
for $|A|\geq 2,$
andinduce$|A|\geq1$
the edges
forandor $A=N$ andinduce the edges$|A|,$$|B|\geq2$
forand $2(|A|+|B|)\leq n+3$ .
$(\gamma_{n})$$(e_{1})$$(e_{2})$$(e_{3}),$ $(e_{4})$$[v^{\emptyset}, v^{A}]$$[v^{i}, v^{A}]$$i\not\in A$$(e_{5})$$[v^{A}, v^{B}]$$(e_{6})$

Property 3.1 The diameter of Galeis at most 2. Moreover, $\delta(Gale(\gamma_{3}))=2$
and $\delta(Gale(\gamma_{4}))=1$ .
PROOF.
The vertices
andare respectively linked by the edges
and$|A|\geq2$
for $|A|=1$ and by the edge
. The verticesforand$j\not\in
A$ , foralways form an edge,
andare linked by
andwith$2\leq|A|\leq n-1$ , andform an edge. Finally, the vertices
andare linked$|B|\geq2$$|A|,$
by the edges
and
.
for
$(\gamma_{n})$$v^{A}$$v^{\emptyset}$$[v^{\emptyset}, v^{N}]$$[v^{N}, v^{A}]$$v^{A}$$v^{i}$$[v^{j}, v^{A}]$$[v^{i}, v^{j}]$$v^{A}$$[v^{i}, v^{N}]$$[v^{A}, v^{\emptyset}]$$v^{j}$$v^{i}$$[v^{\emptyset}, v^{A}]$$v^{B}$$[v^{\emptyset}, v^{B}]$We then consider the following$\square$$2^{n-1}$

inequalities.

$2^{n-1}x_{\overline{A}}- \sum_{|T|\geq 2}x_{T}\leq 1$

for $A\subset N$ and $|A|\leq 1$ ,$2^{n-1}(x_{A}+x_{\overline{A}})- \sum_{|T|\geq 2}x_{T}\leq 1$

for $A\subset N$ and $2\leq|A|\leq n-1$ .

One can easily check that each of those inequalities induces a facetof Gale$A\subset
N$
for
and $|A|\leq n-1$ . Since each facet
contains all vertices except the pair
, we call them the huge facets.
$G^{A}$$(\gamma_{n})$$G^{A}$$\{v^{S}, v^{\overline{s}}\}$

Lemma 3.2 The huge facets form the clique.
in the skeleton of
PROOF. Let us first consider $g=G^{A}\cap G^{B}$ with $A,$ $B\subset N$ and $2\leq|A|,$ $|B|\leq n-1$ .
. We show thatexcept
The face contains all the vertices of Gale
is of codimension 2 by exhibiting a familyof $2^{n}-n-2$ affinely independent
vertices belonging to , this will imply thatandare adjacent. Namely,
is formed by the vertices
withand $|S|\geq 2$ and the vertices
with $1\leq i<j\leq n$ such that $v_{A}^{i}=d_{B}=1$ and $v_{B}^{i}=d_{A}=0$ . In the case$0\leq|A|,$ $|B|\leq 1,$
is formed by the vertices withand $|S|\geq 2$ . Finally,in the case $0\leq|A|\leq 1$ and $2\leq|B|\leq n-1,$
is formed by the vertices
withand $|S|\geq 2$ and the vertex .
$Gale^{*}(\gamma_{n})$$K_{2^{n-1}}$$\{v^{A}, v^{\overline{A}}, v^{B}, v^{B}\}$$(\gamma_{n})$

$g$

$V$

$g$

$G^{B}$$G^{A}$$g$$v^{S}$$V$$S\not\in\{A,\overline{A}, B,\overline{B}\}$$\{v^{i}, v^{j}\}$$V$$v^{S}$$S\not\in\{\overline{A},\overline{B}\}$$V$$v^{\emptyset}$$S\not\in\{\overline{A}, B,\overline{B}\}$$v^{S}$$\square$.
Property 3.3 The huge facets form a dominating clique in the skeleton of,
PROOF.
Since the pairs
form a partition of all the vertices of Gale
for any facet , at least one huge facet
satisfies $|G^{A}\cap F|=|F|-1$ . This implies
thatis adjacent to ; in other words, the huge facets form a dominating clique.
$Gale^{*}(\gamma_{n})$$\{v^{S}, v^{S}\}$$G^{A}$$\square$$(\gamma_{n})$$G^{A}$

$F$

$F$

118

Corollary 3.4 The diameter of$Gale^{*}(\gamma_{n})$is at most 3. Moreover, it is 2 for $n=3,4$ .

Conjecture 3.5 For $n\geq 4$ , the diameters of the Gale polytope of the n-cube and ofits dual are 1 and 2, respectively.

4Complete bipartite subgraphs polytope

partitions
is the graph whose vertices are the
We recall that the folded n-cubeof $N=\{1, \ldots, n\}$ into two subsets, and ; two partitions being adjacent when their,andcommon refinement contains a singleton. In particular,
also called the Clebsch graph.
The complete bipartite subgraphs polytope , which is also called the cut polytopeof the complete graph, is a relative of the folded n-cube. More precisely, the vertices
in ffiof the partitions of $N$ , that is,ofincidence vectors
are the$\delta(S)_{ij}=1$ if exactly one ofis in and otherwise for $1\leq i<j\leq n$ . It is easy tocheck that the squared Euclidian distance between two partitions, seen as vertices of, is $d(n-d)$ , where is their path distance, in the graph. Now,
andis combinatorially equivalent to the simplicia16-dimensional cyclic polytope
with 8 vertices. The symmetry group of is isomorphic to the automorphism groupof , see [10]. See [11] for a detailed treatment of .
, see $[1].The$ determination of all the facets
The skeleton of is the cliqueoffor large seems to be hopeless, but a wide range of facets has been alreadyfound (including all for $n\leq 7$ ). It seems that the huge majority of them are simplices. In [7] it wasfor large , that is,
is asymptotically simplicial, as well as$n\leq7$; moreover,) thatandconjectured (and proved for. Actually, the skeleton of is the line graph of the folded 4-cube.
$2^{n-1}$$\square _{n}$$S$$\overline{S}$$\square _{5}-=\frac{1}{2}H(5,2)$$\square _{4}=K_{4,4}$$c_{n}$$(n2)$$2^{n-1}$$c_{n}$$\delta(S)$

$i,$

$j$

$S$

$0$

$d$

$c_{n}$$c_{3}=h\gamma_{3}=\alpha_{3}$$\square _{n}$$c_{4}$$c_{n}$$\square _{n}$$c_{n}$$c_{n}$$K_{2^{n-1}}$$n$$c_{n}$$n$$h\gamma_{n},$$c_{n}$$\delta(c_{4}^{*})=\delta(c_{5}^{*})=2$$\delta(c_{n}^{*})\leq 4$$\delta(c_{6}^{*})=3$$c_{4}^{*}$

Remark 4.1 Using the basis of the space of affine dependencies on given in [8],; recall that
. Clearly,
we found by computer that Gale; more generally, for odd, Gale
can beand GaleGale$2^{n-1}-n-1$
obtained from the following basis ofaffine dependencies:$c_{5}$$\square _{5}-=\frac{1}{2}H(5,2)$$(c_{5})\simeq h\gamma_{5}$$(h\gamma_{4})\simeq\alpha_{3}$$(h\gamma_{5})\simeq c_{5}$$(n-1) \sum_{i\in X}x_{N\backslash \{i\}}-|A|\sum_{i\in N}x_{N\backslash \{i\}}+(n-1)x_{A}=0$

$n$

for

$|A|$

$(h\gamma_{n})$even, $2\leq|A|\leq n-2$ .

119Finally, we mention $cont_{m}$ , the contact polytope of the lattice $Z(V_{m})$ in $1B(2m)$studied in [9], where
denotes the set of vertices of , that is, $cont_{m}$ is the convex
hull of all vectors of this lattice having the minimal length $\mu=\min(4, m-1)$ . Clearly,
it comes from the construction given in Chapters 5, 7 of [5] withseen as a linear$M=2^{m-1}$ and $d=m-1$ . We have,binary code with
$V_{m}$$c_{m}$$A$$V_{m}$$n=(\begin{array}{l}m2\end{array}),$$\bullet$$\bullet$$cont_{2}=conv\{\pm e_{1}\}=\beta_{1}$and $\mathbb{Z}(V_{2})=Z=A_{1}$ ,is the cubo-octahedron (the vertices ofis thethis Archimedean solid are the midpoints of the edges of ) and,face-centered cube lattice$cont_{3}=conv\{\pm e_{i}\pm e_{j}:1\leq i\neq j\leq 3\}$$\gamma_{3}$$\mathbb{Z}(V_{3})$$A_{3}\cong D_{3}$$\bullet$$cont_{4}=conv\{\pm\delta(i), \pm\delta(i)-2e_{ij}:1\leq i\neq j\leq 4\}\simeq h\gamma_{6}$$\bullet$$cont_{5}$,is a 10-polytope with the following 100 vertices: $\{\pm 2e_{ij}:1\leq i\leq j\leq 5\}$$\cup\{\delta(i)-2\Sigma_{\{jk\}\in X}e_{jk}:1\leq i\leq 5,$. So, $cont_{5}$ is the unionofand five 4-cubes , this polytope has 4624 facets divided into 4 orbitsof its symmetry group $2^{5}Sym(5)$ , moreover, the orbit formed by the 384 facets
forms aequivalent to the one induced by the inequality,
dominating set in the skeleton of$X\subset E(K_{i_{2}\{1,2,3_{\dagger}4,5\}-i})$$2\beta_{10}$$\gamma_{4}$$\sum_{\{ij\}\in C_{1,2,3,4,5}}x_{ij}\leq 2$$cont_{5}^{*}$$\bullet$for $m\geq 6,$ $cont_{m}=conv\{\pm 2e_{ij}:1\leq i\leq j\leq m\}\simeq\beta_{()}m2^{\cdot}$

So, the kissing number of the lattice, that is the number of vertices of $cont_{m}$ , is$\tau=2,12,32,100,$ $m(m-1)$ for $m=2,3,4,5,$.
$\geq 6$

Figure 4.1: The contact polytope of$\mathbb{Z}(V_{3})$is a cubo-octahedron

120

References
1. F. Barahona and R. Mahjoub, “On the cut polytope”, Mathematical Progmmming 36 (1986) 157-173.
2. M. Bayer and C. Lee, “Combinatorial aspects of convex polytopes”, in P. Gruber
and J. Wills (eds.) Handbook on Convex Geometry, North Holland (1994) 485-

534.
3. L. Billera, P. Filliman and B. Sturmfels, t‘Constructions and complexity of secondary polytopes”, Advances in Mathematics 83 (1990) 155-179.
4. A. Brouwer, A. Cohen and A. Neumaier, Distance-Regular Graphs, SpringerVerlag, Berlin, 1989.
5. J. Conway and N. Sloane, Sphere $Packing_{2}$ Lattices and Groups 290 Grundlehrender Mathematischen Wissenschaften, Springer-Verlag, Berlin, 1987.
6. H. Coxeter, Regular Polytopes, Second edition, McMillan 1963, corrected reprint,
Dover, New York, 1973.
7. A. Deza and M. Deza, “On the skeleton of the dual cut polytope”, Proceedingsof Jerusalem Combinatorics 93, to appear in H. Barcelo and G. Kalai (eds.)
Contemporary Mathematics (1994).
8. M. Deza, “Isometries of hypergraphs”, Proceedings of the International Conference on the Theory of Graphs, in A. Rao (ed.), McMillan, Calcutta (1979)
174-189.
9. M. Deza and V. Grishukhin, “Cut polytopes and its lattices”, Rapport deRecherche du LIENS 94-18, Ecole Normale Sup\’erieure, Paris (1994).
10. M. Deza, V. Grishukhin and M. Laurent, (The symmetries of the cut polytope
and of some relatives”, in P. Gritzmann and B. Sturmfels (eds.) Applied Geometry and Discrete Mathematics, the Victor Klee Festschrift” DIMA CS Series in
Discrete Mathematics and Theoretical Computer Science 4 (1991) 205-220.
11. M. Deza, M. Gr\"otschel and M. Laurent, Cuts and Metrics (book in preparation).
12. G. M. Ziegler, Lectures on Polytopes, Graduate Texts in Mathematics 152,
Springer-Verlag New York Berlin Heidelberg, 1995.
“

ANTOINE DEZA
Tokyo Institute of Technology, department of information sciences, Meguro-ku, Ookayama,
Tokyo, Japan. E-mail: deza@is.titech.ac.jp
MICHEL DEZA

CNRS, Ecole Normale Superieure, departement math\’ematiques et informatique, 45
rue $d’ Ulm$ , Paris, France. E-mail: deza@dmi. $ens.fr$