ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 13 (2017) 227-234
Counting faces of graphical zonotopes
Vladimir Grujic *
University of Belgrade, Faculty of Mathematics, Studentski trg 16, Belgrade, Serbia
Received 15 June 2016, accepted 16 January 2017, published online 6 March 2017

Abstract
It is a classical fact that the number of vertices of the graphical zonotope Zr is equal to the number of acyclic orientations of a graph r. We show that the f -polynomial of Zr is obtained as the principal specialization of the q-analog of the chromatic symmetric function of r.
Keywords: Graphical zonotope, f -vector, graphical matroid, symmetric function. Math. Subj. Class.: 05E05, 52B05, 16T05
1 Introduction
The f -polynomial of an n-dimensional polytope P is defined by f (P, q) = ^ "=o fi(P)qi, where fi(P) is the number of ¿-dimensional faces of P. The f-polynomial f (Zr,q) of the graphical zonotope Zr is a combinatorial invariant of a finite, simple graph r. The vertices of Zr are in one-to-one correspondence with regions of the graphical hyperplane arrangement Hr, which are enumerated by acyclic orientations of r.
Stanley's chromatic symmetric function ^(r) = J2 f proper Xf of a graph r = (V, E), introduced in [7], is the enumerator function of proper colorings f: V ^ N, where Xf = xf (!) • • • x f (n) and f is proper if there are no monochromatic edges. The chromatic polynomial x(r, d) of the graph r, which counts proper colorings with a finite number of colors, appears as the principal specialization
The number of acyclic orientations of r is determined by the value of the chromatic polynomial x(r, d) at d = -1, [6]
* Author is supported by Ministry of Education, Science and Technological developments of Republic of Serbia, Project 174034.
E-mail address: vgrujic@matf.bg.ac.rs (Vladimir Grujic)
x(r,d) = ps(*(r))(d) = *(r) |
al
(r) = (-i)|V |x(r,-1).
(1.1)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
227
Ars Math. Contemp. 13 (2017) 107-123
There is a q-analog of the chromatic symmetric function (T) introduced in a wider context of the combinatorial Hopf algebra of simplicial complexes considered in [2]. It is a symmetric function over the field of rational functions in q. The principal specialization of (r) is the q-analog of the chromatic polynomial xq (r, d).
The main result of this paper is the following generalization of formula (1.1):
Theorem 1.1. Let r = (V, E) be a simple connected graph and Zr the corresponding graphical zonotope. Then the f -polynomial of Zr is given by
f (Zr,q) = (-l)|V|x-q(r, -1).
The cancellation-free formula for the antipode in the Hopf algebra of graphs, obtained by Humpert and Martin in [3], reflects the fact that f (Zr, q) depends only on the graphical matroid M(r) associated to r. For instance, for any tree Tn the graphical matroid is the uniform matroid M (Tn) = Un and the corresponding graphical zonotope is the cube ZTn = In-1. Whitney's theorem from 1933 describes how two graphs with the same graphical matroid are related [9]. It can be used to find more interesting nonisomorphic graphs with the same f -polynomials of corresponding graphical zonotopes.
The paper is organized as follows. In Section 2, we review the basic facts about zono-topes. In Section 3, the q-analog of the chromatic symmetric function (r) of a graph r is introduced. Theorem 1.1 is proved in Section 4. We present some examples and calculations in Section 5.
2 Zonotopes
A zonotope Z = Z(v1,..., vm) is a convex polytope determined by a collection of vectors {v1,..., vm} in Rn as the Minkowski sum of line segments
Z = [-Vi,Vi] +-----+ [-Vm,»m].
It is a projection of the m-cube [-1,1]m under the linear map t ^ At, t G [-1,1]m, where A = [v1 • • • vm] is an n x m-matrix whose columns are vectors v1,..., vm. The zonotope Z is symmetric about the origin and all its faces are translations of zonotopes.
To a collection of vectors {v1,..., vm} is associated a central arrangement of hyperplanes H = {HV1,..., HVm}, where Hv denotes the hyperplane perpendicular to a vector v G Rn. The zonotope Z and the corresponding arrangement of hyperplanes H are closely related. In fact the associated fan of the arrangement H is the normal fan N(Z) of the zonotope Z (see [10, Theorem 7.16]). It follows that the face lattice of and the reverse face lattice of Z are isomorphic. In particular, vertices of Z correspond to regions of H and their total numbers coincide
fo(Z )= r(H).	(2.1)
The faces of the zonotope Z are encoded by covectors of the oriented matroid M associated to the collection of vectors {v1,..., vm}. The covectors are sign vectors
V* = {sign(v) G {+, -, 0}m | v G Rn},
( +, (v,vj) > 0
where sign(v)j = < 0, (v, v4) =0 , i = 1,..., m. The face lattice of the zonotope Z [ -, (v,vi) < 0
is isomorphic to the lattice of covectors componentwise induced by +, - < 0 on V *.
V. Grujic: Counting faces of graphical zonotopes
229
A special class of zonotopes is determined by simple graphs. To a connected graph r = (V, E), whose vertices are enumerated by integers V = {1,..., n}, are associated the graphical zonotope
Zr = Z(ei - ej | i < j, {i,j} e E) and the graphical arrangement in Rn
Hr = {Hei-ej | i<j, {i,j}e E}.
There is a bijective correspondence between regions of Hr and acyclic orientations of r, [8, Proposition 2.5], which by (2.1) implies
fo(Zr ) = r(Hr) = a(r).	(2.2)
The arrangement Hr is refined by the braid arrangement An-1 consisting of all hyperplanes Hei-ej, 1 < i < j < n. Thus Zr belongs to a wider class of convex polytopes called generalized permutohedra introduced in [4]. Since arrangements Hr and An-1 are not essential we take their quotients by the line l : x1 = • • • = xn and without confusing retain the same notation. Consequently dimZr = n - 1.
Example 2.1. (i) The permutohedron Pen-1 is represented as the graphical zonotope ZKn corresponding to the complete graph Kn on n vertices (Figure 1).
(ii) The cube In-1 is represented as the graphical zonotope ZTn corresponding to an arbitrary tree Tn on n vertices. This shows that the graph r is not determined by the combinatorial type of the zonotope Zr.
3 q-analog of chromatic symmetric function of graph
Stanley's chromatic symmetric function ^(T) can be obtained in a purely algebraic way. A combinatorial Hopf algebra H is a graded, connected Hopf algebra equipped with the multiplicative linear functional Z: H ^ k to the ground field k. For the theory of combinatorial Hopf algebras see [1]. Consider the combinatorial Hopf algebra of graphs G which is linearly generated over a field k by simple finite graphs with the product defined by disjoint union r1 • r2 = r1 U r2 and the coproduct
A(r) = £ r |i ®r |yu,
ICY
230
Ars Math. Contemp. 13 (2017) 107-123
where r |/ denotes the induced subgraph on I c V. The structure of G is completed by the character Z : G ^ k defined to be Z(r) = 1 for r with no edges and Z(r) = 0 otherwise. Then it turns out that ^(r) is the image of the unique morphism of combinatorial Hopf algebras to symmetric functions ^ : G ^ Sym, ([1, Example 4.5]).
An important part of the structure of the Hopf algebra G is the antipode S : G ^ G. The cancellation-free formula for the antipode in terms of acyclic orientations of a graph r is obtained in [3]. We recall some basic definitions. Terminology comes from matroid theory. Given a graph r = (V, E), for a collection of edges F c E denote by rV,F the graph on V with the edge set F. A flat F of the graph r is a collection of its edges such that components of rV,F are induced subgraphs. The rank rk(F) is the size of spanning forests of rV,F. We have that | V| = rk(F) + c(F), where c(F) is the number of components of rV,F. By contracting edges from a flat F we obtain the graph r/F. Finally, let a(r) be the number of acyclic orientations of r. The formula of Humpert and Martin is as follows
s(r) = £ (-i)c(F>a(r/F)rv,F,	(3.1)
F eF (r)
where the sum is over the set of flats F(r).
The following modification of the character Z is considered in [2] in a wider context of the combinatorial Hopf algebra of simplicial complexes. Define Zq (r) = qrk(r), which determines the algebra morphism Zq : G ^ k(q), where k(q) is the field of rational functions in q. This character produces the unique morphism : G ^ QSym to quasisymmetric functions over k(q). The expansion of (r) in the monomial basis of quasisymmetric functions is determined by the universal formula [1, Theorem 4.1]
(r) = £ (Zq )a(r)Ma.
a=n
The sum above is over all compositions of the integer n = |V | and the coefficient of the expansion corresponding to the composition a = (a^..., ak ) = n is given by
(Zq)a(r)= £ qrk(r|li ) + -+rk(r|ifc ),
/iu...u/fc=v
where the sum is over all set compositions of V of the type a. The coefficients (Zq)a(r) depend only on the partition corresponding to a composition a, so the function (r) is actually symmetric and it can be expressed in the monomial basis of symmetric functions.
The invariant (r) is more subtle than ^(r). Obviously ^0(r) is the chromatic symmetric function of a graph r. It remains open to find two nonisomorphic graphs r and r2 with the same q-chromatic symmetric functions (ri) = (r2). Let
Xq (r,d)= ps(^q (r))(d)
be the q-analog of the chromatic polynomial x(r, d). It is a consequence of a general fact for combinatorial Hopf algebras (see [1]) that
Xq(r, i) = (Zq ◦ S)(r).
(3.2)
V. Grujic: Counting faces of graphical zonotopes
231
Example 3.1. Consider the graph r on four vertices with the edge set E = {12,13,23,34}. We find that
(r) = 24mMiM + (8q + 4)m2,i,i + (2q2 + 4q)m2i2 + (3q2 + q)ms,i + q3m4.
By principal specialization and taking into account that
, (i1 +-----+ ik)! ( d
ps(m.i! .¿fc )(d) = -—-—- .	.
A1	il ! ••• ik!	\il +-----+ iky
we obtain
Xq(r, d) = d(d - 1)2(d - 2) + qd(d - 1)(4d - 5) + 4q2d(d - 1) + q3d, which by Theorem 1.1 gives
f (Zr,q) = 12 + 18q + 8q2 + q3.
4 Proof of Theorem 1.1
Proof. By applying (3.2) and the formula for antipode (3.1) we obtain
(-1)Vx-q(r, -1) = (-1)|V| E (-1)c(r)a(r/F)(-q)rk(F).
f eF (r)
It follows that the statement of the theorem is equivalent to the following expression of the f-polynomial
f (Zr,q)= E «(r/F )qrk(F).	(4.1)
f eF (r)
Therefore it should be shown that components of f-vectors are determined by
fk(Zr)= E «(r/F), 0 < k < n - 1.	(4.2)
f eF (r)
rk(F )=k
By duality between the face lattice of Zr and the face lattice of the fan FHr we have
fk(Zr) = fn-k-1(FHr ).
Let L(Hr) be the intersection lattice of the graphical arrangement Hr. For a subspace X e L(Hr) there is an arrangement of hyperplanes
HX = {X n H | X £ H, H eHr}
whose intersection lattice L(%X) is isomorphic to the upper cone of X in L(Hr). Since Hr is central and essential we have
/n-*-i(FHr )= E r(HX ),	(4.3)
XeL(Hp)
dim(X)=n-k —1
where r(Hf ) is the number of regions of the arrangement Hf, see [8, Theorem 2.6].
The intersection lattice L(Hr) is isomorphic to the lattice of flats of the graphical ma-troid M(r). By this isomorphism to a flat F of rank k corresponds the intersection subspace XF = i,j}eFHei-ej of dimension n - k - 1. It is easy to see that arrangements
xF
Hf and %r/F coincide, which by (2.2) and comparing formulas (4.2) and (4.3) proves theorem.	□
232
Ars Math. Contemp. 13 (2017) 107-123
5 Examples
By applying Theorem 1.1 we obtain the following interpretation of identities elaborated in [2, Propositions 17, 19].
Example 5.1. (i) For the permutohedron Pen-1 = ZKn, the f -polynomial is given by
f (ZKn ,q) = A„(q +1),
where An(q) = J2qdes(n) is the Euler polynomial. Recall that des(n) is the number of descents of a permutation n G Sn. It recovers the fact that the h-polynomial of the permutohedron Pen-1 is the Euler polynomial An(q).
(ii) For the cube In-1 = ZTn, where Tn is a tree on n vertices, the f -polynomial is given by
f (ZTn ,q) = (q + 2)n-1.
Figure 2: Rhombic dodecahedron ZC4.
Proposition 5.2. The f -polynomial of the graphical zonotope ZCn associated to the cycle graph Cn on n vertices is given by
f (Zc„, q) = qn + qn-1 + (q + 2)n - 2(q + 1)n.
Proof. A flat F G F(Cn) is determined by the complementary set of edges. If rk(F) = n - k, k > 1 then the complementary set has k edges and Cn/F = Ck. Since a(Ck) = 2k - 2, k > 1, by formula (4.2), we obtain
fn-k (Zen ) = (2k - 2)Q, 2 < k < n,
which leads to the required formula.	□
Specially, for n = 4 the resulting zonotope is the rhombic dodecahedron (see Figure 2). We have
f (Ze4, q) = 14 + 24q + 12q2 + q3.
Proposition 5.3. Let r = r1 Vv r2 be the wedge of two connected graphs r1 and r2 at the common vertex v. Then
f (Zr,q) = f (Zn, q)f (Zr2,q).
V. Grujic: Counting faces of graphical zonotopes
233
Proof. The graphical matroids of involving graphs are related by M(T) = M(Ti) © M(T2). For the sets of flats it holds F(T) = {Fi U F2 | Fi e F(r),i = 1, 2}. For F = F1 U F2 we have r/F = r1/F1 V [v] r2/F2, where [v] is the component of the vertex v in rv,F. Obviously a(r/F) = a(ri/Fi)a(r2/F2) and rk(F) = rk(Fi) + rk(F2). The proposition follows from formula (4.1).	□
The formula for cubes in Example 5.1 (ii) follows from Proposition 5.3 since any tree is a consecutive wedge of edges and f (Ii, q) = q + 2. It also allows us to restrict ourselves only to biconnected graphs. For a biconnected graph r with a disconnecting pair of vertices {u, v} Whitney introduced the transformation called the twist around the pair {u, v}. This transformation does not have an affect on the graphical matroid M(r) [9].
Figure 3: Biconnected graphs related by twist transformation.
Example 5.4. Figure 3 shows the pair of biconnected graphs on six vertices obtained one from another by the twist transformation. The corresponding zonotopes have the same f-polynomial
f (Zn , q) = f (Zr2, q) = 126 + 348q + 358q2 + 164q3 + 30 q4 + q5.
On the other hand their q-chromatic symmetric functions are different. One can check that corresponding coefficients by m3 i 3 are different
[ms,i3(ri) = (11q2 +8q + 1) • 3!, [ms,i3(r) = (10q2 + 10q) • 3!.
This shows that the q-analog of the chromatic symmetric function of a graph is not determined by the corresponding graphical matroid. By taking q = 0 we obtain that even the chromatic symmetric functions are different since [m3 i3]^(ri) = 6 and [m3 i3]^(r2) = 0.
Let us now consider Stanley's example of nonisomorphic graphs with the same chromatic symmetric functions, see [7]. We find that the f -polynomials of the corresponding graphical zonotopes differ for those graphs. From these examples we conclude that chromatic properties of a graph and the f-vector of the corresponding graphical zonotope are not related.
We have already noted that graphical zonotopes are generalized permutohedra. The h-polynomials of simple generalized permutohedra are determined in [5, Theorem 4.2]. The only simple graphical zonotopes are products of permutohedra [5, Proposition 5.2]. They are characterized by graphs whose biconnected components are complete subgraphs. Therefore Proposition 5.3 together with Example 5.1 (i) prove that the h-polynomial of a
234
Ars Math. Contemp. 13 (2017) 107-123
simple graphical zonotope is the product of Eulerian polynomials, the fact obtained in [5, Corollary 5.4]. Example 3.1 is of this sort and represents the hexagonal prism which is the product ZK3 x ZK2.
References
[1]	M. Aguiar, N. Bergeron and F. Sottile, Combinatorial Hopf algebras and generalized Dehn-Sommerville relations, Compos. Math. 142 (2006), 1-30, doi:10.1112/s0010437x0500165x.
[2]	C. Benedetti, J. Hallam and J. Machacek, Combinatorial Hopf algebras of simplicial complexes, SIAMJ. Discrete Math. 30 (2016), 1737-1757, doi:10.1137/15m1038281.
[3]	B. Humpert and J. L. Martin, The incidence Hopf algebra of graphs, SIAM J. Discrete Math. 26 (2012), 555-570, doi:10.1137/110820075.
[4]	A. Postnikov, Permutohedra, associahedra, and beyond, Int. Math. Res. Not. 2009 (2009), 1026-1106, doi:10.1093/imrn/rnn153.
[5]	A. Postnikov, V. Reiner and L. Williams, Faces of generalized permutohedra, Doc. Math. 13 (2008), 207-273, http://www.math.uiuc.edu/documenta/vol-13/10.html.
[6]	R. P. Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973), 171-178, doi:10.1016/ 0012-365x(73)90108-8.
[7]	R. P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Adv. Math. 111 (1995), 166-194, doi:10.1006/aima.1995.1020.
[8]	R. P. Stanley, An introduction to hyperplane arrangements, in: E. Miller, V. Reiner and B. Sturmfels (eds.), Geometric Combinatorics, American Mathematical Society, Providence, Rhode Island, volume 13 of IAS/Park City Mathematics Series, pp. 389-496, 2007.
[9]	H. Whitney, 2-isomorphic graphs, Amer. J. Math. 55 (1933), 245-254, doi:10.2307/2371127.
[10] G. M. Ziegler, Lectures on Polytopes, volume 152 of Graduate Texts in Mathematics, SpringerVerlag, New York, 1995, doi:10.1007/978-1-4613-8431-1.