The Colin de Verdière number
and graphs of polytopes
Ivan Izmestiev ∗
Institut für Mathematik
Technische Universität Berlin
Str. des 17. Juni 136
10623 Berlin, Germany
izmestiev@math.tu-berlin.de
July 25, 2008
Abstract
The Colin de Verdière number µ(G) of a graph G is the maximum
corank of a Colin de Verdière matrix for G (that is, of a Schrödinger
operator on G with a single negative eigenvalue). In 2001, Lovász gave
a construction that associated to every convex 3-polytope a Colin de
Verdière matrix of corank 3 for its 1-skeleton.
We generalize the Lovász construction to higher dimensions by in-
terpreting it as minus the Hessian matrix of the volume of the polar
dual. As a corollary, µ(G) ≥ d if G is the 1-skeleton of a convex
d-polytope.
Determination of the signature of the Hessian of the volume is based
on the second Minkowski inequality for mixed volumes and on Bol’s
condition for equality.
1 Introduction
1.1 The Colin de Verdière number
At the end of 80’s, Yves Colin de Verdière introduced a graph parameter
µ(G) based on spectral properties of certain matrices associated with the
graph G.
Definition 1.1 Let G be a graph with n vertices. A Colin de Verdière
matrix for G is a symmetric n × n matrix M = (Mij) with the following
properties.
Research for this article was supported by the DFG Research Unit 565 “Polyhedral
Surfaces”.
http://arxiv.org/abs/0704.0349v3
(M1) M is a Schrödinger operator on G, that is
< 0, if ij is an edge of G;
= 0, if ij is not an edge of G and i 6= j.
(M2) M has exactly one negative eigenvalue, and this eigenvalue is simple.
(M3) If X is a symmetric n × n matrix such that MX = 0 and Xij = 0
whenever i = j or ij is an edge of G, then X = 0.
The set of all Colin de Verdière matrices for graph G is denoted by MG.
The Colin de Verdière number µ(G) is defined as the maximum corank of
matrices from MG:
µ(G) := max
dimkerM.
A Colin de Verdière matrix of maximum corank is called optimal.
Basically, the Colin de Verdière number is the maximum multiplicity of
the second least eigenvalue λ2 of a discrete Schrödinger operator M satis-
fying a certain stability assumption (M3). By replacing M with M − λ2Id,
we can make the second eigenvalue zero (M2), so that multiplicity be-
comes corank. Definition 1.1 was motivated by the study of Schrödinger
and Laplace operators associated with degenerating families of Riemannian
metrics on surfaces.
The parameter µ(G) turned out to be interesting on its own. In partic-
ular, it posesses the minor monotonicity property: if a graph H is a minor
of G, then µ(H) ≤ µ(G). By the Robertson-Seymour theorem this implies
that graphs with µ(G) ≤ n can be characterized by a finite set of forbidden
minors. For n up to four such characterizations are known and allow nice
topological reformulations: e. g. µ(G) ≤ 3 iff G is planar (that is doesn’t
have K5 or K3,3 as minors), and µ(G) ≤ 4 iff G is linklessly embeddable in
3 (that is doesn’t have any graph of the Petersen family as a minor). An
overview of results and open problems on the Colin de Verdière number can
be found in [4], [14], and [5]. The book [4] deals also with other spectral
invariants arising from discrete Schrödinger and Laplace operators.
1.2 Nullspace representations and Steinitz representations
Let M be a Colin de Verdière matrix for graph G with dimkerM = d.
Choose a basis (u1, . . . , ud) for kerM ⊂ R
n, fix a coordinate system in Rn,
and read off the coordinates of (uα):
(u1, . . . , ud) = (v1, . . . , vn)
The map that associates to every vertex i of G the vector vi ∈ R
d is called
a nullspace representation of the graph G.
Nullspace representations were studied in [11]. In a subsequent paper
[10] Lovász showed that, for a 3-connected planar G, the nullspace repre-
sentation with properly scaled vectors (vi) realizes G as the skeleton of a
convex 3-polytope. Lovász provided also an inverse construction that as-
sociated to every convex 3-polytope with 1-skeleton G a Colin de Verdère
matrix of corank 3. The proof that the constructed matrix had an appro-
priate signature was indirect, and a more geometric approach was desirable.
1.3 Hessian matrix of the volume as a Colin de Verdière
matrix
In this paper we relate the Lovász construction (that of a matrix from a poly-
tope) to the mixed volumes. Our approach allows a straightforward gener-
alization to higher dimensions. That is, we associate to every d-dimensional
convex polytope with 1-skeleton G a Colin de Verdière matrix for G of
corank d.
As a consequence, the graph of a convex d-dimensional polytope has
Colin de Verdière number at least d. This result is not really new, since it
follows from the minor monotonicity of µ, from the fact that the graph of a
d-polytope has Kd+1 as a minor [8], and from µ(Kd+1) = d.
Our result is based on the following observation. Take a convex d-
polytope P and deform it by shifting every facet parallelly to itself. Then
the Hessian matrix of the volume of P , where partial derivatives are taken
with respect to the distances of the shifts, has corank d and exactly one
positive eigenvalue. Besides, the mixed partial derivative
∂2vol(P )
∂xi∂xj
is positive
if the ith and the jth facets are adjacent, and vanishes otherwise. Thus
the negative of the Hessian matrix satisfies conditions (M1) and (M2) from
Definition 1.1. The condition (M3) follows quite easily, too.
The signature of the Hessian of the volume is encoded in the second
Minkowski inequality for mixed volumes together with Bol’s characteriza-
tion of the case of equality. For simple polytopes, the determination of the
signature of the Hessian is an essential part in the proof of the Alexandrov-
Fenchel inequality.
1.4 Plan of the paper
In Section 2.1 we recall the Lovász construction of a Colin de Verdière matrix
for the skeleton of a convex 3-polytope Q.
After inroducing some terminology and notation in Section 2.2, we show
in Section 2.3 that the Lovász matrix is minus the Hessian matrix of the
volume of the polar dual polytope Q∗.
In Section 2.4, dealing with 3-polytopes, we point out an interesting
identity (first found and used elsewhere [2]) between the Hessian matrix of
vol(Q∗) and the Hessian matrix of another geometric quantity associated
with Q. This gives another interpretation of the Lovász matrix M and
relates the equality dimkerM = 3 with the infinitesimal rigidity of the
polytope Q.
In Section 3.1 we discuss the (im)possibility of inverting the construction,
that is of finding a convex polytope whose Hessian matrix of the volume
equals to a given Colin de Verdière matrix.
In Section 3.2 we give an estimate of the negative eigenvalue (and thus
of the spectral gap) for the Hessian matrices of the volume.
Finally, in the Appendix we derive the signature of the Hessian from the
second Minkowski inequality and Bol’s condition. Although this seems to
be a folklore knowledge in narrow circles, we failed to find a written account
on this subject.
1.5 Acknowledgements
I am grateful to the organizers of the 2006 Oberwolfach conference “Discrete
Differential Geometry”, where the idea of this paper was born. I also thank
Ronald Wotzlaw for pointing me out a mistake in a preliminary version.
2 From a convex polytope to a Colin de Verdière
matrix
2.1 Lovász construction
Let us recall the Lovász construction of an optimal Colin de Verdière matrix
associated with a polytopal representation of a graph in R3.
Let Q ⊂ R3 be a convex polytope containing the coordinate origin in
its interior. Let G be the 1-skeleton of Q. We denote the vertices of G
by i, j, . . ., and the corresponding vertices of Q by vi, vj , . . .. Let Q
∗ be the
polar dual of Q. The vertices of Q∗ are denoted by wf , wg, . . ., where f, g, . . .
are faces of Q.
For ij ∈ G, consider the edge vivj of Q and the dual edge wfwg of Q
see Figure 1. It is easy to show that the vector wf − wg is orthogonal to
both vectors vi and vj, hence parallel to their cross product vi × vj. Thus
we have
wf − wg = Mij(vi × vj), (1)
with Mij < 0 (we agree to choose the labeling of wf and wg so that we get
the correct sign).
Further, consider the vector
v′i =
Mijvj,
vi × vj
Figure 1: To the definition of the matrix M .
where the sum extends over all vertices of G adjacent to i. From (1) it is
easy to see that vi × v
i = 0. Thus there exists a real number Mii such that
v′i = −Miivi. (2)
Putting Mij = 0 for distinct non-adjacent vertices i and j of G, we complete
the construction of the matrix M .
Theorem 2.1 (Lovász, [10]) The matrix M is a Colin de Verdière matrix
for the graph G.
The equation (2) can be rewritten as
Mijvj = 0. (3)
Thus M has corank at least 3. Since µ(G) ≤ 3 for planar graphs, M is an
optimal Colin de Verdière matrix for G.
The proof of Theorem 2.1 goes through a deformation argument, using
the fact that the space of convex 3-polytopes with a given graph is connected.
2.2 Polytopes with a given set of normals
Here we fix some terminology and notation needed in the subsequent sec-
tions.
All polytopes in this paper are assumed to be convex. A facet of a
d-dimensional polytope is a (d− 1)-dimensional face of it.
We will study families of polytopes with fixed facet normals. Let v1, . . . , vn
be vectors in Rd such that the coordinate origin lies in the interior of their
convex hull. Consider a d× n matrix formed by row vectors v⊤i :
V = (v1, . . . , vn)
Definition 2.2 Denote by P(V ) the set of all convex polytopes with the
outer facet normals v1, . . . , vn.
Every polytope in P(V ) is the solution set of a system of linear inequal-
ities:
P (x) = {p ∈ Rd |V p ≤ x},
where x = (xi)
i=1 ∈ R
n. Denote by Fi(x) the facet of P (x) with the outer
normal vi. We have
Fi(x) = {p ∈ P (x) | v
i p = xi}.
The numbers xi are called the support parameters of the polytope P (x).
The map P (x) 7→ x embeds P(V ) into Rn as an open convex subset. The
support parameter xi is proportional to the signed distance from 0 to the
affine hull of the facet Fi(x):
xi = ‖vi‖ · hi.
By vold we denote the volume of a d-dimensional polytope. We use the
subscript because both vold(P ) and vold−1(Fi) will occur in our formulas.
We omit the subscript at vol, when it seems reasonable to do so.
2.3 Interpreting and generalizing the Lovász construction
By definition of the polar dual, we have
Q∗ = {p ∈ R3 | v⊤i p ≤ 1 for all i}.
Thus Q∗ can be viewed as an element of the set P(V ) of polytopes with
facet normals (vi)i∈G. In terms of Section 2.2, Q
∗ = P (1, . . . , 1). Let’s vary
the support parameters of Q∗ and look how does this change its volume.
Lemma 2.3 Let M be the matrix constructed in Section 2.1. Then we have
Mij = −
∂2vol(P (x))
∂xi∂xj
x=(1,...,1)
where P (x) is as in Section 2.2.
Proof . Let Fi(x) be the facet of P (x) with the normal vi. It is not hard to
show that
∂vol3(P (x))
vol2(Fi(x))
Further, for i 6= j we have
∂vol2(Fi(x))
vol1(Fij(x))
‖vj‖ sin θij
∆vol1(Fj)
∆vol2(P )
Figure 2: Partial derivatives of the volume with respect to the support
parameters.
if faces Fi(x) and Fj(x) are adjacent; otherwise this derivative is zero. Here
Fij(x) is the common edge of Fi(x) and Fj(x), and θij is the angle between
the vectors vi and vj (i. e. the outer dihedral angle at the edge Fij). The
equations are illustrated in Figure 2 in one dimension lower and for ‖vi‖ = 1.
Thus at x = (1, . . . , 1) we have
∂2vol(P (x))
∂xi∂xj
vol1(Fij(x))
‖vi‖‖vj‖ sin θij
‖wf − wg‖
‖vi × vj‖
= −Mij (4)
for all i 6= j.
To deal with the case i = j, differentiate the well-known identity
vol2(Fj(x))
with respect to xi. This gives
∂2vol(P (x))
j 6=i
∂2vol(P (x))
∂xi∂xj
vj = 0. (5)
In view of (3) and (4), we have
∂2vol(P (x))
|x=(1,...,1) = −Mii. �
Lemma 2.3 suggests the following generalization of the Lovász construc-
tion.
Theorem 2.4 Let
P (x0) = {p ∈ Rn | v⊤i p ≤ x
i for all i}
be a convex polytope with outer facet normals vi and support parameters
x0i , i = 1, . . . , n. Let G be the dual 1-skeleton of P (x
0). Then the matrix M
defined by
Mij = −
∂2vol(P (x))
∂xi∂xj
is a Colin de Verdiére matrix for the graph G.
The corank of M is equal to d. In particular, µ(G) ≥ d for every graph
G that can be realized as the 1-skeleton of a d-dimensional polytope.
Proof . Similarly to Lemma 2.3, for adjacent facets Fi and Fj we have
∂2vold(P (x))
∂xi∂xj
vold−2(Fij(x))
‖vi‖‖vj‖ sin θij
where Fij is their common (d− 2)-face, and θij is the angle between vi and
vj. For non-adjacent Fi and Fj this derivative is zero. Therefore matrix M
satisfies property (M1) from Definition 1.1.
The proof of property (M2) is the most interesting part of the theo-
rem. The signature of the Hessian of the volume is encoded in the second
Minkowski inequality for mixed volumes enhanced by Bol’s condition for
equality.
Theorem A.10 in Section A states in particular that the matrix M has
corank d. The kernel of M is easy to identify: due to the equation (5) it
consists of the vectors ξ ∈ Rn such that ξi = v
i p for some vector p ∈ R
Assuming this description of kerM , let us prove that the matrix M
satisfies property (M3). If MX = 0, then there are vectors p1, . . . , pn ∈ R
such that Xij = v
i pj for all i, j. Fix j. Then by assumption on X we have
pj ⊥ vj and pj ⊥ vi for all ij ∈ G. But the normal vj to the face Fj and the
normals to the neighboring faces span the space Rd. Thus we have pj = 0
for all j, which implies X = 0.
As for the last sentence of the theorem, if G is the dual 1-skeleton of a
convex polytope P , then G is the skeleton of the polar (P − p)∗, where p is
any interior point of P . �
2.4 Case d = 3 and infinitesimal rigidity of convex polytopes
In the case d = 3 there is another interpretation of the matrix M . As in
Section 2.1, let Q be a convex polytope that has skeleton G and contains
0 in the interior. Triangulate the faces of Q by diagonals and cut Q into
pyramids with apices at 0 and triangles of the triangulation as bases. De-
note by ri the length of the edge that joins 0 to the vertex vi of Q. Now
deform the pyramids by changing the lengths ri and leaving the lengths of
boundary edges constant. During such deformation, the dihedral angles of
the pyramids change, and the total angle ωi around the i-th edge can be-
come different from 2π. By computing the derivatives of ωi explicitly, we
obtain ([2], Theorem 3.11)
vol1(Fij)
sin θij
= ‖vi‖‖vj‖ ·Mij, (7)
where we use the notations from Section 2.3. If we change the variables xi to
hi = ‖vi‖ · xi, so that hi is the distance of 0 from aff (Fi), then the equation
(7) takes a particularly nice form
∂vol2(Fi)
By (7), the matrix (∂ωi
) is obtained from the matrix M by multiplying
the i-th row and the i-th column with ‖vi‖, for all i. This implies
Corollary 2.5 The matrix (∂ωi
) is an optimal Colin de Verdière matrix for
graph G.
The fact that the matrix (∂ωi
) has corank 3 is equivalent to the infinitesi-
mal rigidity of the polytope Q. Indeed, every infinitesimal deformation (dri)
such that dωi = 0 for all i gives rise to an infinitesimal isometric deformation
of Q. The resulting deformation is trivial iff it is produced by moving the
apex 0 inside Q.
Another interesting fact is that the matrix (∂ωi
) is the Hessian matrix
of a geometric quantity related to the polytope Q (deformed by varying ri).
Namely, put
S(r) =
riκi +
ℓijθij,
where κi = 2π − ωi is the “curvature” along the i-th radial edge, and ℓij =
vol1(Fij) is the length of the edge vivj. Then the Schläfli formula implies
= κi.
Hence
∂2S(Q)
∂ri∂rj
∂2vol(Q∗)
∂hi∂hj
and both matrices are equal to the negative of the Lovász matrix M , up to
scaling the rows and columns by ‖vi‖.
3 Concluding remarks
3.1 What fails in the inverse construction
Let M be a Colin de Verdère matrix for the graph G. Is there a convex
polytope P such that M arises from P as a result of the construction de-
scribed in Section 2.3? Of course, in general the answer is no, because G
must be the dual skeleton of P , and P must have dimension d = dimkerM .
In particular, all vertices of G must have degrees at least d. But, due to the
minor monotonicity of µ, there exist trivalent graphs with µ(G) arbitrarily
large.
Nevertheless, it is worth looking at what fails when we try to reconstruct
the polytope P from matrix M .
Let u1, . . . , ud ∈ R
n be a basis of kerM . Let v⊤i be the i-th row in the
matrix (u1, . . . , ud). Then we have
Mijvj = 0 (8)
for all i. Therefore, the vectors v1, . . . , vn ∈ R
d are good candidates for the
outer normals to the faces of the polytope P . At this point we can already
fail, if the following assumptions aren’t fulfilled:
1. vi 6= 0 for all i, and vi 6= vj for all i 6= j;
2. for every i, the projections vij of vj on v
i for ij ∈ G satisfy the
previous assumption and span v⊥i .
We proceed assuming that these conditions hold. Codimension 2 faces
Fij of P must be in 1-to-1 correspondence with the edges of G, and their
volumes are determined by the matrix M :
vold−2(Fij) = Aij := −Mij‖vi‖‖vj‖ sin θij,
where θij is the angle between vi and vj .
Lemma 3.1 For every i, there exists a convex (d−1)-dimensional polytope
Fi ⊂ v
i with outer facet normals vij and facet volumes Aij , ij ∈ G.
Proof . By projecting the equation (8) on v⊥i , we obtain
Mij · vij = 0. (9)
Due to ‖vij‖ = ‖vj‖ sin θij, it follows that
Aij ·
‖vij‖
By Minkowski’s theorem [13, Section 7.1], this implies the existence of a
polytope Fi as stated in the lemma. �
The polytopes Fi in Lemma 3.1 should become facets of the polytope
P . But here is the second point where the reconstruction can fail: the j-th
facet Fij of Fi might be different from the i-th facet Fji of Fj ; the only thing
we know is vold−2(Fij) = Aij = vold−2(Fji).
In the case d = 3, however, this suffices: Fi are convex polygons and
fit together along their edges to form a polytope P . Conditions 1. and 2.
above hold if we assume that G is a 3-connected planar graph [11]. Thus for
3-connected planar graphs every Colin de Verdière matrix corresponds to a
polytope. This is one of the results of [10].
The following example shows that even for highly connected graphs the
number µ(G) can be bigger than the maximum dimension of a polytope
with 1-skeleton G.
Example Let Gn = K2,2,...,2 be the multipartite graph on 2n vertices (the
graph of an n-dimensional cross-polytope). By [9], µ(Gn) = 2n − 3 for
n ≥ 3. For n = 3, 4 the graph Gn can also be represented as the skeleton of
a (2n − 3)-dimensional convex polytope: for n = 3 this is the octahedron,
for n = 4 the join of two convex quadrilaterals in general position in R5.
For n ≥ 5, however, there is no (2n − 3)-dimensional convex polytope with
skeleton Gn. Indeed, by studying the Gale diagram [16, Lecture 6] of a
d-polytope with d + 3 vertices, one can show that the complement to the
graph of such polytope cannot have more than 4 edges.
Note that the equation (9) is reminiscent of the definition of a (d − 2)-
weight in [12].
3.2 Negative eigenvalue
Theorem 3.2 Let λ1 be the negative eigenvalue of the matrix (6). Then
the following inequality holds:
λ1 ≤ −d(d− 1) ·
vold(P (x
‖x0‖2
The equality takes place iff
x0i = c ·
vold−1(Fi(x
for all i and some constant c.
Proof . By induction on d, it is easy to show that the function vold(P (x)) is a
degree d homogeneous polynomial in x as long as the combinatorics of P (x)
does not change. For different combinatorics, the polynomials have different
coefficients. However, since vold(P (x)) is twice differentiable, we can apply
Euler’s homogeneous function theorem twice at the point x0, independently
on how generic the combinatorics of P (x0) is. This yields
(x0)⊤Mx0 = −d(d− 1) · vold(P (x
Since λ1 = min‖ξ‖=1 ξ
⊤Mξ, the inequality follows.
Since λ1 is the unique negative eigenvalue of M , the inequality turns
into equality iff Mx0 = λx0 for some λ. We have
j = −
∂vold−1(Fi(x
x0j = −(d− 1) ·
vold−1(Fi(x
Thus Mx0 = λx0 is equivalent to x0i = c ·
vold−1(Fi(x
, and the theorem is
proved. �
The number λ2 − λ1 is called the spectral gap. In our case λ2 = 0 by
definition. Thus Theorem 3.2 provides an estimate on the spectral gap of
the matrix M .
Usually, one seeks to make the spectral gap as large as possible, but in
order this to make sense for Colin de Verdère matices, one has to choose a
matrix norm, [4, Chapter 5.7]. The norm of the matrix (6) is a function of
its coefficients, which have a geometric meaning. Thus, as soon as the choice
of a matrix norm is made, one can try to solve the problem of the spectral
gap by geometric means (at least for 3-connected planar graphs, for which
every optimal Colin de Verdière matrix can be realized through a polytope).
A The second Minkowski inequality for mixed vol-
umes and the signature of the matrix
∂2vol
∂xi∂xj
The goal of this appendix is to prove Theorem A.10 that describes the sig-
nature of the matrix (6). The theorem is derived from the second Minkowski
inequality for mixed volumes and Bol’s condition for equality.
The relation between the theory of mixed volumes and infinitesimal rigid-
ity (as we know, the rank of matrix (6) accounts for the infinitesimal rigidity
of the dual polytope, see Section 2.4) was noticed long ago [1, 15]. In the
decades thereafter this phenomenon seemed to be forgotten. Quite recently,
Carl Lee and Paul Filliman [7] discovered it again.
A.1 The second Minkowski inequality and Bol’s condition
Definition A.1 Let P,Q ⊂ Rd be convex bodies. A mixed volume of P and
Q is a coefficient in the expansion
vol(λP + µQ) =
vol(Q, . . . , Q
︸ ︷︷ ︸
, P, . . . , P
︸ ︷︷ ︸
)λd−kµk (10)
with λ, µ > 0, where A + B for A,B ⊂ Rd denotes the Minkowski sum. In
particular,
vol(P, . . . , P ) = vol(P ).
In a similar way one defines the mixed volume of more than two convex
bodies. It turns out that the mixed volume is polylinear with respect to the
Minkowski addition and multiplication with positive scalars. A proof that
the expansion (10) takes place and more information on mixed volumes can
be found in [6, 13].
Theorem A.2 Let P,Q ⊂ Rd be convex bodies. Then the following holds:
1. (The second Minkowski inequality)
vol(Q,P, . . . , P )2 ≥ vol(P ) · vol(Q,Q,P, . . . , P ). (11)
2. (Bol’s condition) Assume that dimQ = d. Then equality holds in (11)
if and only if either dimP < d − 1 or P is homothetic to a (d − 2)-
tangential body of Q.
For a proof see [13, Theorem 6.2.1, Theorem 6.6.18]. Bol’s condition was
conjectured by Minkowski but proved only decades later by Bol, [3].
Definition A.3 If P ⊂ Q ⊂ Rd are d-dimensional convex polytopes, then
Q is called a p-tangential body of P iff P has a non-empty intersection with
every face of Q of dimension at least p.
A.2 Mixed volumes as derivatives of the volume
By substituting in (10) λ = 1 and µ = t, we obtain
vol(P + tQ) = vol(P ) + tdvol(Q,P, . . . , P )
d(d− 1)
vol(Q,Q,P, . . . , P ) + · · · (12)
for all t > 0, which can be seen as the Taylor expansion of vol. We will look
at it in the case when P and Q are polytopes with the same sets of facet
normals.
The space P(V ) of all polytopes with outer facet normals v1, . . . , vn is
defined in Section 2.2. We want to study the partial derivatives of the volume
of P (x) ∈ P(V ) with respect to the support parameters x. For brevity, let’s
use the notation
vol(x) := vol(P (x)).
Similarly, the mixed volume of polytopes from P(V ) will be written as a
function of the support parameters:
vol(x1, . . . , xd) := vol(P (x1), . . . , P (xd)).
Now we would like to compute vol(x+ ty) with the help of (12). This is
not as straightforward as it seems, because the support parameters behave
not quite linearly under the Minkowski addition. We have P (ty) = tP (y)
for t > 0. Also we have P (x) + P (y) ⊂ P (x + y), but the equality doesn’t
always hold. To describe the cases in which we do have the equality, we
need a new definition.
Definition A.4 The normal cone N(F,P ) of the face F of a polytope P ⊂
d is the set of vectors w ∈ Rd such that
(w⊤x) = max
(w⊤x).
The normal fan N(P ) is the decomposition of Rd into the normal cones of
the faces of P . If the normal fan N(Q) subdivides the normal fan N(P ),
then we write N(Q) > N(P ).
Note that the normal fan of a polytope P ∈ P(V ) has the rays R+vi as
1-dimensional cones. The higher-dimensional cones of the normal fan deter-
mine the combinatorics of P . Therefore polytopes with equal normal fans
are sometimes called strongly isomorphic.
We denote the normal fans of the polytopes from P(V ) by N(x) :=
N(P (x)). The following lemma is classical.
Lemma A.5 If N(y) > N(x), then P (x) + P (y) = P (x+ y).
Now we are ready to prove
Lemma A.6 Let y ∈ P(V ) be such that N(y) > N(x). Then
∇yvol(x) = d · vol(y, x, . . . , x),
∇2yvol(x) = d(d− 1) · vol(y, y, x, . . . , x),
where ∇y denotes the directional derivative along y.
Proof . Due to Lemma A.5 we have P (x + ty) = P (x) + tP (y). By substi-
tuting P = P (x) and Q = P (y) in (12), we obtain
vol(x+ ty) = vol(x) + tdvol(y, x, . . . , x)
d(d− 1)
vol(y, y, x, . . . , x) + · · · ,
which implies the lemma. �
Remark. For polytopes with the same normal fan (“strongly isomorphic
polytopes”), there is the following description of mixed volumes. Denote
P∆(V ) = {P (x) ∈ P(V ) |N(x) = ∆}.
By induction on d, it is easy to show that there exists a homogeneous poly-
nomial V∆ of degree d in n variables such that
vol(P (x)) = V∆(x),
for all x ∈ P∆(U). If we use the same symbol V∆ to denote the associated
symmetric polylinear form, then we have
vol(P (x(1)), . . . , P (x(d))) = V∆(x
(1), . . . , x(d))
for all x(1), . . . , x(d) ∈ P∆(V ).
A.3 From the second Minkowski inequality to the signature
of the Hessian of the volume
By geometric arguments similar to those in the proof of Lemma 2.3, the
function vol is twice continuously differentiable on P(V ). Therefore the
following definition makes sense.
Definition A.7 Let x ∈ P(V ). Define a symmetric bilinear form Φ on Rn
Φ(ξ, η) = ∇η∇ξvol(x).
Let y ∈ P(V ) be such that N(y) > N(x). By combining Euler’s homo-
geneous function theorem and Lemma A.6, we obtain
Φ(x, x) = d(d− 1) vol(x, . . . , x),
Φ(x, y) = d(d− 1) vol(y, x, . . . , x),
Φ(y, y) = d(d− 1) vol(y, y, x, . . . , x).
Lemma A.8 Let L ⊂ Rn be a 2-dimensional vector subspace such that
x ∈ L. Then the restriction of the form Φ to L has signature (+,−) or
(+, 0).
Proof . Let y ∈ P(V ) be such that N(y) > N(x). The second Minkowski
inequality (11) applied to P = P (x) and Q = P (y) can be rewritten as
Φ(x, x) Φ(x, y)
Φ(x, y) Φ(y, y)
≤ 0. (13)
Since, moreover, Φ(x, x) = d(d−1) vol(P ) > 0, it follows that the restriction
of Φ to span {x, y} has signature (+, 0) or (+,−).
It remains to show that every 2-subspace L ∋ x can be represented as
span {x, y} with N(y) > N(x). This is true since x is an interior point of
the set {y ∈ P(V ) |N(y) > N(x)}. (When we perturb x, we can create new
faces, but cannot destroy old ones.) �
Lemma A.9 The form Φ has corank d.
Proof . Let us exhibit a d-dimensional subspace of ker Φ. Associate with
every point p ∈ Rd a vector p ∈ Rn with coordinates
pi = 〈vi, p〉.
The polytope P (x+p) is the translate of P (x) by p. Therefore the directional
derivative ∇pvol(x) vanishes for all x, which implies Φ(p, η) = 0 for all η.
Thus we have
p ∈ kerΦ
for all p ∈ Rd.
Let ξ ∈ ker Φ. We need to show that ξ = p for some p ∈ Rd. Denote
the span of x and ξ by L. Then, by Lemma A.8, the restriction Φ|L has
signature (+, 0) and hence
Rξ = L ∩ ker Φ. (14)
Choose y ∈ L such that N(y) > N(x), and x and y are linearly independent.
Then the degeneracy of Φ|L means that we have an equality in (13) and
thus also in the Minkowski inequality for P = P (x) and Q = P (y). By
Bol’s condition, see Theorem A.2, this happens if and only if the polytope
P (x) is homothetic to a (d − 2)-tangential body of the polytope P (y). By
studying Definition A.3, we see that in P(V ) it is equivalent to P (x) being
homothetic to P (y). If P (x) is homothetic to P (y), then x = λy + p for
some p ∈ Rd, thus p ∈ L. Since p ∈ kerΦ, it follows that
Rp = L ∩ ker Φ.
By comparing this to (14), we conclude that ξ = µp = µp for some µ ∈ R.
Thus the kernel of Φ is confined to the vectors of the form p. �
Theorem A.10 The form Φ has corank d and exactly one positive eigen-
value, which is simple.
Proof . The corank of Φ is computed in Lemma A.9.
The form Φ has at least one positive eigenvector since Φ(x, x) > 0.
Assume that it has more than one. Then there exists a 2-subspace of Rn
on which Φ is positively definite. The subgroup of GL(Rn) that preserves Φ
acts transitively on the cone of positive directions. Thus there is a positive
2-subspace L that passes through x. This contradicts Lemma A.8. Theorem
is proved. �
References
[1] W. Blaschke. Ein Beweis für die Unverbiegbarkeit geschlossener kon-
vexer Flächen. Gött. Nachr., pages 607–610, 1912.
[2] A. Bobenko and I. Izmestiev. Alexandrov’s theorem, weighted Delau-
nay triangulations, and mixed volumes. Ann. Inst. Fourier (Grenoble),
58(2):447–505, 2008.
[3] G. Bol. Beweis einer Vermutung von H. Minkowski. Abh. Math. Sem.
Hansischen Univ., 15:37–56, 1943.
[4] Y. Colin de Verdière. Spectres de graphes, volume 4 of Cours Spécialisés.
Société Mathématique de France, Paris, 1998.
[5] Y. Colin de Verdière. Sur le spectre des opérateurs de type Schrödinger
sur les graphes. In Graphes, pages 25–52. Ed. Éc. Polytech., Palaiseau,
2004.
[6] G. Ewald. Combinatorial convexity and algebraic geometry, volume 168
of Graduate Texts in Mathematics. Springer-Verlag, New York, 1996.
[7] P. Filliman. Rigidity and the Alexandrov-Fenchel inequality. Monatsh.
Math., 113(1):1–22, 1992.
[8] B. Grünbaum. Convex polytopes, volume 221 of Graduate Texts in
Mathematics. Springer-Verlag, New York, second edition, 2003. Pre-
pared and with a preface by Volker Kaibel, Victor Klee and Günter M.
Ziegler.
[9] A. Kotlov, L. Lovász, and S. Vempala. The Colin de Verdière number
and sphere representations of a graph. Combinatorica, 17(4):483–521,
1997.
[10] L. Lovász. Steinitz representations of polyhedra and the Colin de
Verdière number. J. Combin. Theory Ser. B, 82(2):223–236, 2001.
[11] L. Lovász and A. Schrijver. On the null space of a Colin de Verdière
matrix. Ann. Inst. Fourier (Grenoble), 49(3):1017–1026, 1999. Sympo-
sium à la Mémoire de François Jaeger (Grenoble, 1998).
[12] P. McMullen. Weights on polytopes. Discrete Comput. Geom.,
15(4):363–388, 1996.
[13] R. Schneider. Convex bodies: the Brunn-Minkowski theory, volume 44
of Encyclopedia of Mathematics and its Applications. Cambridge Uni-
versity Press, Cambridge, 1993.
[14] H. van der Holst, L. Lovász, and A. Schrijver. The Colin de Verdière
graph parameter. In Graph theory and combinatorial biology (Balaton-
lelle, 1996), volume 7 of Bolyai Soc. Math. Stud., pages 29–85. János
Bolyai Math. Soc., Budapest, 1999.
[15] H. Weyl. Über die Bestimmung einer geschlossenen konvexen Fläche
durch ihr Linienelement. Zürich. Naturf. Ges., 61:40–72, 1916.
[16] G. M. Ziegler. Lectures on polytopes, volume 152 of Graduate Texts in
Mathematics. Springer-Verlag, New York, 1995.
	Introduction
	The Colin de Verdière number
	Nullspace representations and Steinitz representations
	Hessian matrix of the volume as a Colin de Verdière matrix
	Plan of the paper
	Acknowledgements
	From a convex polytope to a Colin de Verdière matrix
	Lovász construction
	Polytopes with a given set of normals
	Interpreting and generalizing the Lovász construction
	Case d=3 and infinitesimal rigidity of convex polytopes
	Concluding remarks
	What fails in the inverse construction
	Negative eigenvalue
	The second Minkowski inequality for mixed volumes and the signature of the matrix (2 volxi xj)
	The second Minkowski inequality and Bol's condition
	Mixed volumes as derivatives of the volume
	From the second Minkowski inequality to the signature of the Hessian of the volume

  The Colin de Verdi\`ere number $\mu(G)$ of a graph $G$ is the maximum corank
of a Colin de Verdi\`ere matrix for $G$ (that is, of a Schr\"odinger operator
on $G$ with a single negative eigenvalue). In 2001, Lov\'asz gave a
construction that associated to every convex 3-polytope a Colin de Verdi\`ere
matrix of corank 3 for its 1-skeleton.
  We generalize the Lov\'asz construction to higher dimensions by interpreting
it as minus the Hessian matrix of the volume of the polar dual. As a corollary,
$\mu(G) \ge d$ if $G$ is the 1-skeleton of a convex $d$-polytope.
  Determination of the signature of the Hessian of the volume is based on the
second Minkowski inequality for mixed volumes and on Bol's condition for
equality.

Introduction
1.1 The Colin de Verdière number
At the end of 80’s, Yves Colin de Verdière introduced a graph parameter
µ(G) based on spectral properties of certain matrices associated with the
graph G.
Definition 1.1 Let G be a graph with n vertices. A Colin de Verdière
matrix for G is a symmetric n × n matrix M = (Mij) with the following
properties.
Research for this article was supported by the DFG Research Unit 565 “Polyhedral
Surfaces”.
http://arxiv.org/abs/0704.0349v3
(M1) M is a Schrödinger operator on G, that is
< 0, if ij is an edge of G;
= 0, if ij is not an edge of G and i 6= j.
(M2) M has exactly one negative eigenvalue, and this eigenvalue is simple.
(M3) If X is a symmetric n × n matrix such that MX = 0 and Xij = 0
whenever i = j or ij is an edge of G, then X = 0.
The set of all Colin de Verdière matrices for graph G is denoted by MG.
The Colin de Verdière number µ(G) is defined as the maximum corank of
matrices from MG:
µ(G) := max
dimkerM.
A Colin de Verdière matrix of maximum corank is called optimal.
Basically, the Colin de Verdière number is the maximum multiplicity of
the second least eigenvalue λ2 of a discrete Schrödinger operator M satis-
fying a certain stability assumption (M3). By replacing M with M − λ2Id,
we can make the second eigenvalue zero (M2), so that multiplicity be-
comes corank. Definition 1.1 was motivated by the study of Schrödinger
and Laplace operators associated with degenerating families of Riemannian
metrics on surfaces.
The parameter µ(G) turned out to be interesting on its own. In partic-
ular, it posesses the minor monotonicity property: if a graph H is a minor
of G, then µ(H) ≤ µ(G). By the Robertson-Seymour theorem this implies
that graphs with µ(G) ≤ n can be characterized by a finite set of forbidden
minors. For n up to four such characterizations are known and allow nice
topological reformulations: e. g. µ(G) ≤ 3 iff G is planar (that is doesn’t
have K5 or K3,3 as minors), and µ(G) ≤ 4 iff G is linklessly embeddable in
3 (that is doesn’t have any graph of the Petersen family as a minor). An
overview of results and open problems on the Colin de Verdière number can
be found in [4], [14], and [5]. The book [4] deals also with other spectral
invariants arising from discrete Schrödinger and Laplace operators.
1.2 Nullspace representations and Steinitz representations
Let M be a Colin de Verdière matrix for graph G with dimkerM = d.
Choose a basis (u1, . . . , ud) for kerM ⊂ R
n, fix a coordinate system in Rn,
and read off the coordinates of (uα):
(u1, . . . , ud) = (v1, . . . , vn)
The map that associates to every vertex i of G the vector vi ∈ R
d is called
a nullspace representation of the graph G.
Nullspace representations were studied in [11]. In a subsequent paper
[10] Lovász showed that, for a 3-connected planar G, the nullspace repre-
sentation with properly scaled vectors (vi) realizes G as the skeleton of a
convex 3-polytope. Lovász provided also an inverse construction that as-
sociated to every convex 3-polytope with 1-skeleton G a Colin de Verdère
matrix of corank 3. The proof that the constructed matrix had an appro-
priate signature was indirect, and a more geometric approach was desirable.
1.3 Hessian matrix of the volume as a Colin de Verdière
matrix
In this paper we relate the Lovász construction (that of a matrix from a poly-
tope) to the mixed volumes. Our approach allows a straightforward gener-
alization to higher dimensions. That is, we associate to every d-dimensional
convex polytope with 1-skeleton G a Colin de Verdière matrix for G of
corank d.
As a consequence, the graph of a convex d-dimensional polytope has
Colin de Verdière number at least d. This result is not really new, since it
follows from the minor monotonicity of µ, from the fact that the graph of a
d-polytope has Kd+1 as a minor [8], and from µ(Kd+1) = d.
Our result is based on the following observation. Take a convex d-
polytope P and deform it by shifting every facet parallelly to itself. Then
the Hessian matrix of the volume of P , where partial derivatives are taken
with respect to the distances of the shifts, has corank d and exactly one
positive eigenvalue. Besides, the mixed partial derivative
∂2vol(P )
∂xi∂xj
is positive
if the ith and the jth facets are adjacent, and vanishes otherwise. Thus
the negative of the Hessian matrix satisfies conditions (M1) and (M2) from
Definition 1.1. The condition (M3) follows quite easily, too.
The signature of the Hessian of the volume is encoded in the second
Minkowski inequality for mixed volumes together with Bol’s characteriza-
tion of the case of equality. For simple polytopes, the determination of the
signature of the Hessian is an essential part in the proof of the Alexandrov-
Fenchel inequality.
1.4 Plan of the paper
In Section 2.1 we recall the Lovász construction of a Colin de Verdière matrix
for the skeleton of a convex 3-polytope Q.
After inroducing some terminology and notation in Section 2.2, we show
in Section 2.3 that the Lovász matrix is minus the Hessian matrix of the
volume of the polar dual polytope Q∗.
In Section 2.4, dealing with 3-polytopes, we point out an interesting
identity (first found and used elsewhere [2]) between the Hessian matrix of
vol(Q∗) and the Hessian matrix of another geometric quantity associated
with Q. This gives another interpretation of the Lovász matrix M and
relates the equality dimkerM = 3 with the infinitesimal rigidity of the
polytope Q.
In Section 3.1 we discuss the (im)possibility of inverting the construction,
that is of finding a convex polytope whose Hessian matrix of the volume
equals to a given Colin de Verdière matrix.
In Section 3.2 we give an estimate of the negative eigenvalue (and thus
of the spectral gap) for the Hessian matrices of the volume.
Finally, in the Appendix we derive the signature of the Hessian from the
second Minkowski inequality and Bol’s condition. Although this seems to
be a folklore knowledge in narrow circles, we failed to find a written account
on this subject.
1.5 Acknowledgements
I am grateful to the organizers of the 2006 Oberwolfach conference “Discrete
Differential Geometry”, where the idea of this paper was born. I also thank
Ronald Wotzlaw for pointing me out a mistake in a preliminary version.
2 From a convex polytope to a Colin de Verdière
matrix
2.1 Lovász construction
Let us recall the Lovász construction of an optimal Colin de Verdière matrix
associated with a polytopal representation of a graph in R3.
Let Q ⊂ R3 be a convex polytope containing the coordinate origin in
its interior. Let G be the 1-skeleton of Q. We denote the vertices of G
by i, j, . . ., and the corresponding vertices of Q by vi, vj , . . .. Let Q
∗ be the
polar dual of Q. The vertices of Q∗ are denoted by wf , wg, . . ., where f, g, . . .
are faces of Q.
For ij ∈ G, consider the edge vivj of Q and the dual edge wfwg of Q
see Figure 1. It is easy to show that the vector wf − wg is orthogonal to
both vectors vi and vj, hence parallel to their cross product vi × vj. Thus
we have
wf − wg = Mij(vi × vj), (1)
with Mij < 0 (we agree to choose the labeling of wf and wg so that we get
the correct sign).
Further, consider the vector
v′i =
Mijvj,
vi × vj
Figure 1: To the definition of the matrix M .
where the sum extends over all vertices of G adjacent to i. From (1) it is
easy to see that vi × v
i = 0. Thus there exists a real number Mii such that
v′i = −Miivi. (2)
Putting Mij = 0 for distinct non-adjacent vertices i and j of G, we complete
the construction of the matrix M .
Theorem 2.1 (Lovász, [10]) The matrix M is a Colin de Verdière matrix
for the graph G.
The equation (2) can be rewritten as
Mijvj = 0. (3)
Thus M has corank at least 3. Since µ(G) ≤ 3 for planar graphs, M is an
optimal Colin de Verdière matrix for G.
The proof of Theorem 2.1 goes through a deformation argument, using
the fact that the space of convex 3-polytopes with a given graph is connected.
2.2 Polytopes with a given set of normals
Here we fix some terminology and notation needed in the subsequent sec-
tions.
All polytopes in this paper are assumed to be convex. A facet of a
d-dimensional polytope is a (d− 1)-dimensional face of it.
We will study families of polytopes with fixed facet normals. Let v1, . . . , vn
be vectors in Rd such that the coordinate origin lies in the interior of their
convex hull. Consider a d× n matrix formed by row vectors v⊤i :
V = (v1, . . . , vn)
Definition 2.2 Denote by P(V ) the set of all convex polytopes with the
outer facet normals v1, . . . , vn.
Every polytope in P(V ) is the solution set of a system of linear inequal-
ities:
P (x) = {p ∈ Rd |V p ≤ x},
where x = (xi)
i=1 ∈ R
n. Denote by Fi(x) the facet of P (x) with the outer
normal vi. We have
Fi(x) = {p ∈ P (x) | v
i p = xi}.
The numbers xi are called the support parameters of the polytope P (x).
The map P (x) 7→ x embeds P(V ) into Rn as an open convex subset. The
support parameter xi is proportional to the signed distance from 0 to the
affine hull of the facet Fi(x):
xi = ‖vi‖ · hi.
By vold we denote the volume of a d-dimensional polytope. We use the
subscript because both vold(P ) and vold−1(Fi) will occur in our formulas.
We omit the subscript at vol, when it seems reasonable to do so.
2.3 Interpreting and generalizing the Lovász construction
By definition of the polar dual, we have
Q∗ = {p ∈ R3 | v⊤i p ≤ 1 for all i}.
Thus Q∗ can be viewed as an element of the set P(V ) of polytopes with
facet normals (vi)i∈G. In terms of Section 2.2, Q
∗ = P (1, . . . , 1). Let’s vary
the support parameters of Q∗ and look how does this change its volume.
Lemma 2.3 Let M be the matrix constructed in Section 2.1. Then we have
Mij = −
∂2vol(P (x))
∂xi∂xj
x=(1,...,1)
where P (x) is as in Section 2.2.
Proof . Let Fi(x) be the facet of P (x) with the normal vi. It is not hard to
show that
∂vol3(P (x))
vol2(Fi(x))
Further, for i 6= j we have
∂vol2(Fi(x))
vol1(Fij(x))
‖vj‖ sin θij
∆vol1(Fj)
∆vol2(P )
Figure 2: Partial derivatives of the volume with respect to the support
parameters.
if faces Fi(x) and Fj(x) are adjacent; otherwise this derivative is zero. Here
Fij(x) is the common edge of Fi(x) and Fj(x), and θij is the angle between
the vectors vi and vj (i. e. the outer dihedral angle at the edge Fij). The
equations are illustrated in Figure 2 in one dimension lower and for ‖vi‖ = 1.
Thus at x = (1, . . . , 1) we have
∂2vol(P (x))
∂xi∂xj
vol1(Fij(x))
‖vi‖‖vj‖ sin θij
‖wf − wg‖
‖vi × vj‖
= −Mij (4)
for all i 6= j.
To deal with the case i = j, differentiate the well-known identity
vol2(Fj(x))
with respect to xi. This gives
∂2vol(P (x))
j 6=i
∂2vol(P (x))
∂xi∂xj
vj = 0. (5)
In view of (3) and (4), we have
∂2vol(P (x))
|x=(1,...,1) = −Mii. �
Lemma 2.3 suggests the following generalization of the Lovász construc-
tion.
Theorem 2.4 Let
P (x0) = {p ∈ Rn | v⊤i p ≤ x
i for all i}
be a convex polytope with outer facet normals vi and support parameters
x0i , i = 1, . . . , n. Let G be the dual 1-skeleton of P (x
0). Then the matrix M
defined by
Mij = −
∂2vol(P (x))
∂xi∂xj
is a Colin de Verdiére matrix for the graph G.
The corank of M is equal to d. In particular, µ(G) ≥ d for every graph
G that can be realized as the 1-skeleton of a d-dimensional polytope.
Proof . Similarly to Lemma 2.3, for adjacent facets Fi and Fj we have
∂2vold(P (x))
∂xi∂xj
vold−2(Fij(x))
‖vi‖‖vj‖ sin θij
where Fij is their common (d− 2)-face, and θij is the angle between vi and
vj. For non-adjacent Fi and Fj this derivative is zero. Therefore matrix M
satisfies property (M1) from Definition 1.1.
The proof of property (M2) is the most interesting part of the theo-
rem. The signature of the Hessian of the volume is encoded in the second
Minkowski inequality for mixed volumes enhanced by Bol’s condition for
equality.
Theorem A.10 in Section A states in particular that the matrix M has
corank d. The kernel of M is easy to identify: due to the equation (5) it
consists of the vectors ξ ∈ Rn such that ξi = v
i p for some vector p ∈ R
Assuming this description of kerM , let us prove that the matrix M
satisfies property (M3). If MX = 0, then there are vectors p1, . . . , pn ∈ R
such that Xij = v
i pj for all i, j. Fix j. Then by assumption on X we have
pj ⊥ vj and pj ⊥ vi for all ij ∈ G. But the normal vj to the face Fj and the
normals to the neighboring faces span the space Rd. Thus we have pj = 0
for all j, which implies X = 0.
As for the last sentence of the theorem, if G is the dual 1-skeleton of a
convex polytope P , then G is the skeleton of the polar (P − p)∗, where p is
any interior point of P . �
2.4 Case d = 3 and infinitesimal rigidity of convex polytopes
In the case d = 3 there is another interpretation of the matrix M . As in
Section 2.1, let Q be a convex polytope that has skeleton G and contains
0 in the interior. Triangulate the faces of Q by diagonals and cut Q into
pyramids with apices at 0 and triangles of the triangulation as bases. De-
note by ri the length of the edge that joins 0 to the vertex vi of Q. Now
deform the pyramids by changing the lengths ri and leaving the lengths of
boundary edges constant. During such deformation, the dihedral angles of
the pyramids change, and the total angle ωi around the i-th edge can be-
come different from 2π. By computing the derivatives of ωi explicitly, we
obtain ([2], Theorem 3.11)
vol1(Fij)
sin θij
= ‖vi‖‖vj‖ ·Mij, (7)
where we use the notations from Section 2.3. If we change the variables xi to
hi = ‖vi‖ · xi, so that hi is the distance of 0 from aff (Fi), then the equation
(7) takes a particularly nice form
∂vol2(Fi)
By (7), the matrix (∂ωi
) is obtained from the matrix M by multiplying
the i-th row and the i-th column with ‖vi‖, for all i. This implies
Corollary 2.5 The matrix (∂ωi
) is an optimal Colin de Verdière matrix for
graph G.
The fact that the matrix (∂ωi
) has corank 3 is equivalent to the infinitesi-
mal rigidity of the polytope Q. Indeed, every infinitesimal deformation (dri)
such that dωi = 0 for all i gives rise to an infinitesimal isometric deformation
of Q. The resulting deformation is trivial iff it is produced by moving the
apex 0 inside Q.
Another interesting fact is that the matrix (∂ωi
) is the Hessian matrix
of a geometric quantity related to the polytope Q (deformed by varying ri).
Namely, put
S(r) =
riκi +
ℓijθij,
where κi = 2π − ωi is the “curvature” along the i-th radial edge, and ℓij =
vol1(Fij) is the length of the edge vivj. Then the Schläfli formula implies
= κi.
Hence
∂2S(Q)
∂ri∂rj
∂2vol(Q∗)
∂hi∂hj
and both matrices are equal to the negative of the Lovász matrix M , up to
scaling the rows and columns by ‖vi‖.
3 Concluding remarks
3.1 What fails in the inverse construction
Let M be a Colin de Verdère matrix for the graph G. Is there a convex
polytope P such that M arises from P as a result of the construction de-
scribed in Section 2.3? Of course, in general the answer is no, because G
must be the dual skeleton of P , and P must have dimension d = dimkerM .
In particular, all vertices of G must have degrees at least d. But, due to the
minor monotonicity of µ, there exist trivalent graphs with µ(G) arbitrarily
large.
Nevertheless, it is worth looking at what fails when we try to reconstruct
the polytope P from matrix M .
Let u1, . . . , ud ∈ R
n be a basis of kerM . Let v⊤i be the i-th row in the
matrix (u1, . . . , ud). Then we have
Mijvj = 0 (8)
for all i. Therefore, the vectors v1, . . . , vn ∈ R
d are good candidates for the
outer normals to the faces of the polytope P . At this point we can already
fail, if the following assumptions aren’t fulfilled:
1. vi 6= 0 for all i, and vi 6= vj for all i 6= j;
2. for every i, the projections vij of vj on v
i for ij ∈ G satisfy the
previous assumption and span v⊥i .
We proceed assuming that these conditions hold. Codimension 2 faces
Fij of P must be in 1-to-1 correspondence with the edges of G, and their
volumes are determined by the matrix M :
vold−2(Fij) = Aij := −Mij‖vi‖‖vj‖ sin θij,
where θij is the angle between vi and vj .
Lemma 3.1 For every i, there exists a convex (d−1)-dimensional polytope
Fi ⊂ v
i with outer facet normals vij and facet volumes Aij , ij ∈ G.
Proof . By projecting the equation (8) on v⊥i , we obtain
Mij · vij = 0. (9)
Due to ‖vij‖ = ‖vj‖ sin θij, it follows that
Aij ·
‖vij‖
By Minkowski’s theorem [13, Section 7.1], this implies the existence of a
polytope Fi as stated in the lemma. �
The polytopes Fi in Lemma 3.1 should become facets of the polytope
P . But here is the second point where the reconstruction can fail: the j-th
facet Fij of Fi might be different from the i-th facet Fji of Fj ; the only thing
we know is vold−2(Fij) = Aij = vold−2(Fji).
In the case d = 3, however, this suffices: Fi are convex polygons and
fit together along their edges to form a polytope P . Conditions 1. and 2.
above hold if we assume that G is a 3-connected planar graph [11]. Thus for
3-connected planar graphs every Colin de Verdière matrix corresponds to a
polytope. This is one of the results of [10].
The following example shows that even for highly connected graphs the
number µ(G) can be bigger than the maximum dimension of a polytope
with 1-skeleton G.
Example Let Gn = K2,2,...,2 be the multipartite graph on 2n vertices (the
graph of an n-dimensional cross-polytope). By [9], µ(Gn) = 2n − 3 for
n ≥ 3. For n = 3, 4 the graph Gn can also be represented as the skeleton of
a (2n − 3)-dimensional convex polytope: for n = 3 this is the octahedron,
for n = 4 the join of two convex quadrilaterals in general position in R5.
For n ≥ 5, however, there is no (2n − 3)-dimensional convex polytope with
skeleton Gn. Indeed, by studying the Gale diagram [16, Lecture 6] of a
d-polytope with d + 3 vertices, one can show that the complement to the
graph of such polytope cannot have more than 4 edges.
Note that the equation (9) is reminiscent of the definition of a (d − 2)-
weight in [12].
3.2 Negative eigenvalue
Theorem 3.2 Let λ1 be the negative eigenvalue of the matrix (6). Then
the following inequality holds:
λ1 ≤ −d(d− 1) ·
vold(P (x
‖x0‖2
The equality takes place iff
x0i = c ·
vold−1(Fi(x
for all i and some constant c.
Proof . By induction on d, it is easy to show that the function vold(P (x)) is a
degree d homogeneous polynomial in x as long as the combinatorics of P (x)
does not change. For different combinatorics, the polynomials have different
coefficients. However, since vold(P (x)) is twice differentiable, we can apply
Euler’s homogeneous function theorem twice at the point x0, independently
on how generic the combinatorics of P (x0) is. This yields
(x0)⊤Mx0 = −d(d− 1) · vold(P (x
Since λ1 = min‖ξ‖=1 ξ
⊤Mξ, the inequality follows.
Since λ1 is the unique negative eigenvalue of M , the inequality turns
into equality iff Mx0 = λx0 for some λ. We have
j = −
∂vold−1(Fi(x
x0j = −(d− 1) ·
vold−1(Fi(x
Thus Mx0 = λx0 is equivalent to x0i = c ·
vold−1(Fi(x
, and the theorem is
proved. �
The number λ2 − λ1 is called the spectral gap. In our case λ2 = 0 by
definition. Thus Theorem 3.2 provides an estimate on the spectral gap of
the matrix M .
Usually, one seeks to make the spectral gap as large as possible, but in
order this to make sense for Colin de Verdère matices, one has to choose a
matrix norm, [4, Chapter 5.7]. The norm of the matrix (6) is a function of
its coefficients, which have a geometric meaning. Thus, as soon as the choice
of a matrix norm is made, one can try to solve the problem of the spectral
gap by geometric means (at least for 3-connected planar graphs, for which
every optimal Colin de Verdière matrix can be realized through a polytope).
A The second Minkowski inequality for mixed vol-
umes and the signature of the matrix
∂2vol
∂xi∂xj
The goal of this appendix is to prove Theorem A.10 that describes the sig-
nature of the matrix (6). The theorem is derived from the second Minkowski
inequality for mixed volumes and Bol’s condition for equality.
The relation between the theory of mixed volumes and infinitesimal rigid-
ity (as we know, the rank of matrix (6) accounts for the infinitesimal rigidity
of the dual polytope, see Section 2.4) was noticed long ago [1, 15]. In the
decades thereafter this phenomenon seemed to be forgotten. Quite recently,
Carl Lee and Paul Filliman [7] discovered it again.
A.1 The second Minkowski inequality and Bol’s condition
Definition A.1 Let P,Q ⊂ Rd be convex bodies. A mixed volume of P and
Q is a coefficient in the expansion
vol(λP + µQ) =
vol(Q, . . . , Q
︸ ︷︷ ︸
, P, . . . , P
︸ ︷︷ ︸
)λd−kµk (10)
with λ, µ > 0, where A + B for A,B ⊂ Rd denotes the Minkowski sum. In
particular,
vol(P, . . . , P ) = vol(P ).
In a similar way one defines the mixed volume of more than two convex
bodies. It turns out that the mixed volume is polylinear with respect to the
Minkowski addition and multiplication with positive scalars. A proof that
the expansion (10) takes place and more information on mixed volumes can
be found in [6, 13].
Theorem A.2 Let P,Q ⊂ Rd be convex bodies. Then the following holds:
1. (The second Minkowski inequality)
vol(Q,P, . . . , P )2 ≥ vol(P ) · vol(Q,Q,P, . . . , P ). (11)
2. (Bol’s condition) Assume that dimQ = d. Then equality holds in (11)
if and only if either dimP < d − 1 or P is homothetic to a (d − 2)-
tangential body of Q.
For a proof see [13, Theorem 6.2.1, Theorem 6.6.18]. Bol’s condition was
conjectured by Minkowski but proved only decades later by Bol, [3].
Definition A.3 If P ⊂ Q ⊂ Rd are d-dimensional convex polytopes, then
Q is called a p-tangential body of P iff P has a non-empty intersection with
every face of Q of dimension at least p.
A.2 Mixed volumes as derivatives of the volume
By substituting in (10) λ = 1 and µ = t, we obtain
vol(P + tQ) = vol(P ) + tdvol(Q,P, . . . , P )
d(d− 1)
vol(Q,Q,P, . . . , P ) + · · · (12)
for all t > 0, which can be seen as the Taylor expansion of vol. We will look
at it in the case when P and Q are polytopes with the same sets of facet
normals.
The space P(V ) of all polytopes with outer facet normals v1, . . . , vn is
defined in Section 2.2. We want to study the partial derivatives of the volume
of P (x) ∈ P(V ) with respect to the support parameters x. For brevity, let’s
use the notation
vol(x) := vol(P (x)).
Similarly, the mixed volume of polytopes from P(V ) will be written as a
function of the support parameters:
vol(x1, . . . , xd) := vol(P (x1), . . . , P (xd)).
Now we would like to compute vol(x+ ty) with the help of (12). This is
not as straightforward as it seems, because the support parameters behave
not quite linearly under the Minkowski addition. We have P (ty) = tP (y)
for t > 0. Also we have P (x) + P (y) ⊂ P (x + y), but the equality doesn’t
always hold. To describe the cases in which we do have the equality, we
need a new definition.
Definition A.4 The normal cone N(F,P ) of the face F of a polytope P ⊂
d is the set of vectors w ∈ Rd such that
(w⊤x) = max
(w⊤x).
The normal fan N(P ) is the decomposition of Rd into the normal cones of
the faces of P . If the normal fan N(Q) subdivides the normal fan N(P ),
then we write N(Q) > N(P ).
Note that the normal fan of a polytope P ∈ P(V ) has the rays R+vi as
1-dimensional cones. The higher-dimensional cones of the normal fan deter-
mine the combinatorics of P . Therefore polytopes with equal normal fans
are sometimes called strongly isomorphic.
We denote the normal fans of the polytopes from P(V ) by N(x) :=
N(P (x)). The following lemma is classical.
Lemma A.5 If N(y) > N(x), then P (x) + P (y) = P (x+ y).
Now we are ready to prove
Lemma A.6 Let y ∈ P(V ) be such that N(y) > N(x). Then
∇yvol(x) = d · vol(y, x, . . . , x),
∇2yvol(x) = d(d− 1) · vol(y, y, x, . . . , x),
where ∇y denotes the directional derivative along y.
Proof . Due to Lemma A.5 we have P (x + ty) = P (x) + tP (y). By substi-
tuting P = P (x) and Q = P (y) in (12), we obtain
vol(x+ ty) = vol(x) + tdvol(y, x, . . . , x)
d(d− 1)
vol(y, y, x, . . . , x) + · · · ,
which implies the lemma. �
Remark. For polytopes with the same normal fan (“strongly isomorphic
polytopes”), there is the following description of mixed volumes. Denote
P∆(V ) = {P (x) ∈ P(V ) |N(x) = ∆}.
By induction on d, it is easy to show that there exists a homogeneous poly-
nomial V∆ of degree d in n variables such that
vol(P (x)) = V∆(x),
for all x ∈ P∆(U). If we use the same symbol V∆ to denote the associated
symmetric polylinear form, then we have
vol(P (x(1)), . . . , P (x(d))) = V∆(x
(1), . . . , x(d))
for all x(1), . . . , x(d) ∈ P∆(V ).
A.3 From the second Minkowski inequality to the signature
of the Hessian of the volume
By geometric arguments similar to those in the proof of Lemma 2.3, the
function vol is twice continuously differentiable on P(V ). Therefore the
following definition makes sense.
Definition A.7 Let x ∈ P(V ). Define a symmetric bilinear form Φ on Rn
Φ(ξ, η) = ∇η∇ξvol(x).
Let y ∈ P(V ) be such that N(y) > N(x). By combining Euler’s homo-
geneous function theorem and Lemma A.6, we obtain
Φ(x, x) = d(d− 1) vol(x, . . . , x),
Φ(x, y) = d(d− 1) vol(y, x, . . . , x),
Φ(y, y) = d(d− 1) vol(y, y, x, . . . , x).
Lemma A.8 Let L ⊂ Rn be a 2-dimensional vector subspace such that
x ∈ L. Then the restriction of the form Φ to L has signature (+,−) or
(+, 0).
Proof . Let y ∈ P(V ) be such that N(y) > N(x). The second Minkowski
inequality (11) applied to P = P (x) and Q = P (y) can be rewritten as
Φ(x, x) Φ(x, y)
Φ(x, y) Φ(y, y)
≤ 0. (13)
Since, moreover, Φ(x, x) = d(d−1) vol(P ) > 0, it follows that the restriction
of Φ to span {x, y} has signature (+, 0) or (+,−).
It remains to show that every 2-subspace L ∋ x can be represented as
span {x, y} with N(y) > N(x). This is true since x is an interior point of
the set {y ∈ P(V ) |N(y) > N(x)}. (When we perturb x, we can create new
faces, but cannot destroy old ones.) �
Lemma A.9 The form Φ has corank d.
Proof . Let us exhibit a d-dimensional subspace of ker Φ. Associate with
every point p ∈ Rd a vector p ∈ Rn with coordinates
pi = 〈vi, p〉.
The polytope P (x+p) is the translate of P (x) by p. Therefore the directional
derivative ∇pvol(x) vanishes for all x, which implies Φ(p, η) = 0 for all η.
Thus we have
p ∈ kerΦ
for all p ∈ Rd.
Let ξ ∈ ker Φ. We need to show that ξ = p for some p ∈ Rd. Denote
the span of x and ξ by L. Then, by Lemma A.8, the restriction Φ|L has
signature (+, 0) and hence
Rξ = L ∩ ker Φ. (14)
Choose y ∈ L such that N(y) > N(x), and x and y are linearly independent.
Then the degeneracy of Φ|L means that we have an equality in (13) and
thus also in the Minkowski inequality for P = P (x) and Q = P (y). By
Bol’s condition, see Theorem A.2, this happens if and only if the polytope
P (x) is homothetic to a (d − 2)-tangential body of the polytope P (y). By
studying Definition A.3, we see that in P(V ) it is equivalent to P (x) being
homothetic to P (y). If P (x) is homothetic to P (y), then x = λy + p for
some p ∈ Rd, thus p ∈ L. Since p ∈ kerΦ, it follows that
Rp = L ∩ ker Φ.
By comparing this to (14), we conclude that ξ = µp = µp for some µ ∈ R.
Thus the kernel of Φ is confined to the vectors of the form p. �
Theorem A.10 The form Φ has corank d and exactly one positive eigen-
value, which is simple.
Proof . The corank of Φ is computed in Lemma A.9.
The form Φ has at least one positive eigenvector since Φ(x, x) > 0.
Assume that it has more than one. Then there exists a 2-subspace of Rn
on which Φ is positively definite. The subgroup of GL(Rn) that preserves Φ
acts transitively on the cone of positive directions. Thus there is a positive
2-subspace L that passes through x. This contradicts Lemma A.8. Theorem
is proved. �
References
[1] W. Blaschke. Ein Beweis für die Unverbiegbarkeit geschlossener kon-
vexer Flächen. Gött. Nachr., pages 607–610, 1912.
[2] A. Bobenko and I. Izmestiev. Alexandrov’s theorem, weighted Delau-
nay triangulations, and mixed volumes. Ann. Inst. Fourier (Grenoble),
58(2):447–505, 2008.
[3] G. Bol. Beweis einer Vermutung von H. Minkowski. Abh. Math. Sem.
Hansischen Univ., 15:37–56, 1943.
[4] Y. Colin de Verdière. Spectres de graphes, volume 4 of Cours Spécialisés.
Société Mathématique de France, Paris, 1998.
[5] Y. Colin de Verdière. Sur le spectre des opérateurs de type Schrödinger
sur les graphes. In Graphes, pages 25–52. Ed. Éc. Polytech., Palaiseau,
2004.
[6] G. Ewald. Combinatorial convexity and algebraic geometry, volume 168
of Graduate Texts in Mathematics. Springer-Verlag, New York, 1996.
[7] P. Filliman. Rigidity and the Alexandrov-Fenchel inequality. Monatsh.
Math., 113(1):1–22, 1992.
[8] B. Grünbaum. Convex polytopes, volume 221 of Graduate Texts in
Mathematics. Springer-Verlag, New York, second edition, 2003. Pre-
pared and with a preface by Volker Kaibel, Victor Klee and Günter M.
Ziegler.
[9] A. Kotlov, L. Lovász, and S. Vempala. The Colin de Verdière number
and sphere representations of a graph. Combinatorica, 17(4):483–521,
1997.
[10] L. Lovász. Steinitz representations of polyhedra and the Colin de
Verdière number. J. Combin. Theory Ser. B, 82(2):223–236, 2001.
[11] L. Lovász and A. Schrijver. On the null space of a Colin de Verdière
matrix. Ann. Inst. Fourier (Grenoble), 49(3):1017–1026, 1999. Sympo-
sium à la Mémoire de François Jaeger (Grenoble, 1998).
[12] P. McMullen. Weights on polytopes. Discrete Comput. Geom.,
15(4):363–388, 1996.
[13] R. Schneider. Convex bodies: the Brunn-Minkowski theory, volume 44
of Encyclopedia of Mathematics and its Applications. Cambridge Uni-
versity Press, Cambridge, 1993.
[14] H. van der Holst, L. Lovász, and A. Schrijver. The Colin de Verdière
graph parameter. In Graph theory and combinatorial biology (Balaton-
lelle, 1996), volume 7 of Bolyai Soc. Math. Stud., pages 29–85. János
Bolyai Math. Soc., Budapest, 1999.
[15] H. Weyl. Über die Bestimmung einer geschlossenen konvexen Fläche
durch ihr Linienelement. Zürich. Naturf. Ges., 61:40–72, 1916.
[16] G. M. Ziegler. Lectures on polytopes, volume 152 of Graduate Texts in
Mathematics. Springer-Verlag, New York, 1995.
	Introduction
	The Colin de Verdière number
	Nullspace representations and Steinitz representations
	Hessian matrix of the volume as a Colin de Verdière matrix
	Plan of the paper
	Acknowledgements
	From a convex polytope to a Colin de Verdière matrix
	Lovász construction
	Polytopes with a given set of normals
	Interpreting and generalizing the Lovász construction
	Case d=3 and infinitesimal rigidity of convex polytopes
	Concluding remarks
	What fails in the inverse construction
	Negative eigenvalue
	The second Minkowski inequality for mixed volumes and the signature of the matrix (2 volxi xj)
	The second Minkowski inequality and Bol's condition
	Mixed volumes as derivatives of the volume
	From the second Minkowski inequality to the signature of the Hessian of the volume
