“K-THEORETIC” ANALOG OF POSTNIKOV-SHAPIRO
ALGEBRA DISTINGUISHES GRAPHS

arXiv:1603.04654v1 [math.CO] 15 Mar 2016

GLEB NENASHEV AND BORIS SHAPIRO

Izvestnomu ponskomu matematiku Tole Kirillovu posvwaets
Abstract. In this paper we study a filtered “K-theoretical” analog of a
graded algebra associated to any loopless graph G which was introduced in
[4]. We show that two such filtered algebras are isomorphic if and only if their
graphs are isomorphic. We also study a large family of filtered generalizations
of the latter graded algebra which includes the above “K-theoretical” analog.

1. Introduction
The following square-free algebra CG associated to an arbitrary vertex labeled
graph G was defined in [4], see also [1]. Let G be a graph without loops on the vertex
set {0, ..., n}. (Below we always assume that all graphs might have multiple edges,
but no loops). Throughout the whole paper, we fix a field K of zero characteristic.
Let ΦG be the graded commutative algebra over K generated by the variables
φe , e ∈ G, with the defining relations:
(φe )2 = 0,

for any edge e ∈ G.

Let CG be the subalgebra of ΦG generated by the elements
X
Xi =
ci,e φe ,
e∈G

for i = 1, ..., n, where
ci,e



 1 if e = (i, j), i < j;
= −1 if e = (i, j), i > j;


0 otherwise.

(1)

For the reasons which will be clear soon, we call CG the spanning forests counting
algebra of G. Its Hilbert series and the set of defining relations were calculated in
[5] following the initial paper [6]. Namely, let JG be the ideal in K[x1 , . . . , xn ]
generated by the polynomials
!DI +1
X
pI =
xi
,
(2)
i∈I

P
where I ranges over all nonempty subsets in {1, . . . , n} and DI = i∈I dI (i), where
dI (i) is the total number of edges connecting a given vertex i ∈ I with all vertices
outside I. Thus, DI is the total number of edges between I and the complementary
¯ Set BG := K[x1 , . . . , xn ]/JG .
set of vertices I.
Date: January 23, 2018.
2000 Mathematics Subject Classification. Primary 05E40, Secondary 05C31.
Key words and phrases. spanning forests and trees, commutative algebras, filtered algebras.
1

2

G. NENASHEV AND B. SHAPIRO

Pn
Remark 1. Observe that since i=0 Xi = 0, we can define CG as the subalgebra
of ΦG generated by X0 , X1 , . . . , Xn .
We can also define BG as the quotient algebra of K[x0 , . . . , xn ] by the ideal
generated by pI , where I runs over all subsets of {x0 , x1 , · · · , xn }. This follows
from the relation
DI +1
!DI +1 
X
X
.
pI =
= p{0,1,...,n} −
xi
xi 
i∈I

i∈I

To describe the Hilbert polynomial of CG , we need the following classical notion
going back to W. T. Tutte. Given a simple graph G, fix an arbitrary linear order
of its edges. Now, given a spanning forest F in G (i.e., a subgraph without cycles
which includes all vertices of G) and an edge e ∈ G \ F in its complement, we say
that e is externally active for F, if there exists a cycle C in G such that all edges in
C \ {e} belong to F and e is minimal in C with respect to the chosen linear order.
The total number of external edges is called the external activity of F . Although
the external activity of a given forest/tree in G depends on the choice of a linear
ordering of edges, the total number of forests/trees with a given external activity is
independent of this ordering. Now we are ready to formulate the main result of [5].
Theorem 1. [Theorems 3 and 4 of [5]] For any simple graph G, algebras BG and
CG are isomorphic. The total dimension of these algebras (as vector spaces over
K) is equal to the number of spanning subforests in G. The dimension of the k-th
graded component of these algebras equals the number of subforests F in G with
external activity |G| − |F | − k. Here |G| (resp. |F |) stands for the number of edges
in G (resp. F ).
In the above notation, our main object will be the filtered subalgebra KG ⊂ ΦG
defined by the generators:
Y
Yi = exp(Xi ) =
(1 + ci,e φe ), i = 0, . . . , n.
e∈G

(Notice that we have one more generator here than in the previous case.)

Remark 2. Since Yi is obtained by exponentiation of Xi , we call KG the “Ktheoretic” analog of CG .
Our first result is as follows. Define the ideal IG in K[y0 , y1 , . . . , yn ] as generated
by the polynomials
!DI +1
Y
qI =
yi − 1
,
(3)
i∈I

where I ranges over all nonempty subsets in {0, 1, . . . , n} and the number DI is the
same as in (2). Set DG := K[y0 , . . . , yn ]/IG .

Theorem 2. For any graph G, algebras BG , CG , DG and KG are isomorphic as
(non-filtered) algebras.
Moreover, the following stronger statement holds.
Theorem 3. For any graph G, algebras DG and KG are isomorphic as filtered
algebras.
Recall that in a recent paper [3] the first author has shown that CG contains all
information about the matroid of G and only it. Namely,

“K-THEORETIC” ANALOG DISTINGUISHES GRAPHS

3

Theorem 4. [Theorem 5 of [3]] Given two graphs G1 and G2 , algebras CG1 and
CG2 are isomorphic if and only if the matroids of G1 and G2 coincide. (The latter
isomorphism can be thought of either as graded or as non-graded, the statement
holds in both cases.)
On the other hand, filtered algebras DG and KG contain complete information
about G.
Theorem 5. Given two graphs G1 and G2 without isolated vertices, KG1 and KG2
are isomorphic as filtered algebras if and only if G1 and G2 are isomorphic.
The structure of this paper is as follows. In § 2 we prove new results formulated
above. In § 3 we discuss Hilbert series of similar algebras defined by other sets of
generators. In § 4 we discuss “K-theoretic” analogs of algebras counting spanning
trees. Finally, in § 5 we present a number of open problems.
Acknowledgements. The study of DG and KG was initiated by the second author
jointly with Professor A. N. Kirillov during his visit to Stockholm in OctoberNovember 2009 supported by the Swedish Royal Academy. The second author is
happy to acknowledge the importance of this visit for the present project and to
dedicate this paper to Professor Kirillov.
2. Proofs
To prove Theorem 2, we need some preliminary results.
Lemma 1. For any simple graph G, algebras CG and KG coincide as subalgebras
of ΦG .
Proof. Since (Xi )di +1 = 0, where di is the degree of vertex i, then
Yi = exp(Xi ) = 1 +

di
X
(Xi )j

j!

j=1

.

Hence Yi ∈ CG which means that KG ⊂ CG ⊂ ΦG .
To prove the opposite inclusion, consider Yei = Yi − 1 = exp(Xi ) − 1. Since Xi |Yei ,
we get
(Yei )di +1 = 0.
Pdi (−1)j−1 (Yei )j
Using the relation Xi = ln(1 + Yei ) =
, we conclude Xi ∈ KG .
j=1

j!

Thus CG ⊂ KG , implying that CG and KG coincide.



Lemma 2. For any simple graph G, algebras BG and DG are isomorphic as (nonfiltered) algebras.

Proof. First we change the variables in DG by using yei = yi − 1, i = 0, 1, . . . , n.
The generators of ideal IG transform as
!DI +1
Y
qeI =
(yei + 1) − 1
,
i∈I

for any subset I ⊂ {0, 1, . . . , n}.
Since for every vertex i = 0, 1, . . . , n,

((yei + 1) − 1)di +1 = yei di +1 ,
e
we can consider DG as the quotient K[[ye0 , . . . , yf
n ]]/IG of the ring of formal power
e
series factored by the ideal IG generated by all qeI .
Similarly we can consider BG as the quotient K[[x0 , . . . , xn ]]/JeG of the ring of
formal power series by the ideal JeG generated by all pI .

4

G. NENASHEV AND B. SHAPIRO

Introduce the homomorphism ψ : K[[e
y0 , . . . , yen ]] 7→ K[[x0 , . . . , xn ]] defined by:
ψ : yei → exi − 1.

In fact, ψ is an isomorphism, because ψ −1 is defined by xi → ln(1 + yei ).
Let us look at what happens with the ideal IeG under the action of ψ. For a
given I ⊂ {0, 1, . . . , n}, consider the generator qeI . Then,
!DI +1
!DI +1
Y
Y
xi
ψ(e
qI ) =
(ψ(yei ) + 1) − 1
=
e −1
=
i∈I

=

exp

X
i∈I

P

xi

!

−1

i∈I

!DI +1

=

X
i∈I

xi

!DI +1

·

exp

!DI +1

P
i∈I xi − 1
P
.
i∈I xi

exp( i∈I xi )−1
P
The factor
is a formal power series starting with the constant term 1.
i∈I xi
Hence the last factor in the right-hand side of the latter expression is an invertible
power series. Thus, the generator qeI is mapped by ψ to the product pI · ∗, where ∗
is an invertible series. This implies ψ(IeG ) = JeG . Hence algebras DG and BG are
isomorphic.


Proof of Theorem 2. By Lemmas 1, 2 and Theorem 1, we get that all four algebras
are isomorphic to each other. Furthermore, by Theorem 1, we know that their total
dimension over K is the number of subforests in G.

Theorem 3 now follows from Theorem 2.
Proof of Theorem 3. Consider the surjective homomorphism h : DG → KG , defined
by:
h(yi ) = Yi , i = 0, 1, . . . , n.
(It is indeed a homomorphism because every relation qI holds for Y0 , . . . , Yn .) By
Theorem 2 we know that these algebras have the same dimension, implying that h
is an isomorphism. It is clear that h preserves the filtration.


2.1. Proving Theorem 5. We start with a few definitions.
Given a commutative algebra A, its element
P t ∈ A is called reducible nilpotent if
and only if there exists a presentation t = ui vi , where all ui , vi are nilpotents.
For a nilpotent element t ∈ A, define its degree d(t) as the minimal non-negative
integer for which there exists a reducible nilpotent element h ∈ A such that
(t − h)d+1 = 0.
Given an element R ∈ ΦG , we say that an edge-element φe belongs to R, if
monomial φe has a non-zero coefficient in the expansion of R as the sum of squarefree monomials in ΦG .
Lemma 3. For any nilpotent element R ∈ KG ⊂ ΦG , the degree d(R) of R equals
the number of edges of G belonging to R.

“K-THEORETIC” ANALOG DISTINGUISHES GRAPHS

5

Proof. We can write R in terms of {X0 , . . . , Xn }. (Observe that KG and CG coincide as subsets of ΦG , but have different graded/filtered structures). Now we can
concentrate on the graded structure of CG . Select the part of R which lies in the
first graded component of CG . Thus
R = R1 + R′ =

n
X

ai X i + R ′ ,

i=0

where R′ is reducible nilpotent because it belongs to the linear span of other graded
components. Thus d(R) = d(R1 ). The statement of Lemma 3 is obvious for R1 .
Additionally by construction, an edge-element φe belongs to R if and only if it
belongs to R1 .


Lemma 4. Given a graph G, let {Ye0 , . . . , Yen } be the set of generators of KG corresponding to the vertices (i.e., Yei = exp(Xi ) − 1). Then
(1) {Ye0 , . . . , Yen } are nilpotents;
Pn
e
(2)
i=0 ln(1 + Yi ) = 0;
(3) for any subset I ⊂ [0, n] and any set of pairwise distinct non-zero numbers
P
ai ∈ K (i ∈ I), the degree d( i∈I ai Yei ) is equal to the number of edges
incident to the vertices belonging to I;
ei )+d(Y
ej )−d(Y
ei +Y
ej )
d(Y
(4) the number of edges between vertices i and j equals to
.
2
Proof. Item (1) is obvious.
To settle (2), observe that ln(1 + Yei ) = Xi which implies
n
X
i=0

ln(1 + Yei ) =

n
X

Xi = 0.

i=0

P
To prove (3), notice that, by Lemma 3, the degree d( i∈I ai Yei ) is equal to the
P
number of edges belonging to the sum i∈I ai Yei . Each edge belongs either to zero,
to one or to two generators Yei from the latter sum. Moreover, if an edge belongs to
two generators, then it has coefficients of opposite signs. Since all ai are different,
P
an edge-element φe belongs to i∈I ai Yei if and only if it belongs to at least one
P
Yei , for i ∈ I. Thus the degree d( i∈I ai Yei ) is the number of edges incident to all
vertices from I.
To settle (4), notice that if e is an edge between vertices i and j, then φe belongs
to Yei and to Yej with the opposite coefficients. Therefore φe does not belong to
(Yei + Yej ). Using Lemma 3, we get that d(Yei ) + d(Yej ) − d(Yei + Yej ) equals twice the
number of edges between i and j.

Our proof of Theorem 5 uses the following technical lemma which should be
obvious to the specialists.
Lemma 5 (Folklore). Let E be the set of edges of some graph G without isolated
vertices. If we know the following information:
(1) which pairs ei , ej ∈ E of edges are multiple, i.e., connect the same pair of
vertices;
(2) which pairs ei , ej ∈ E of edges have exactly one common vertex;
(3) which triples ei , ej , ek ∈ E of edges form a triangle,
then we can reconstruct G up to an isomorphism.

6

G. NENASHEV AND B. SHAPIRO

Proof. Assume the contrary, i.e., that there exist two non-isomorphic graphs G and
G′ such that there exists a bijection ψ of their edge sets E and E ′ preserving (1)
- (3). Assume that under this bijection an edge e ∈ E corresponds to the edge
e′ ∈ E ′ . Additionally assume that |V (G′ )| ≥ |V (G)|.
Now we construct an isomorphism between G and G′ . Let us split the vertices
of G into two subsets: V (G) = Vb (G) ∪ Ṽ (G), where Vb (G) are all vertices which
are incident to some pair of non-multiple edges.
Let us construct a bijection ψ between the vertices of G and G′ , which extends
the given bijection ψ of edges, i.e., for any e = uv =∈ E, e′ = ψ(e) = ψ(u)ψ(v).
At first we define it on Vb (G). Namely, given a vertex v ∈ Vb (G), choose two
non-multiple edges ei and ej incident to it, and define ψ(v) as a common vertex of
e′i and e′j . We need to show that ψ(v) does not depend on the choice of ei and ej . It
is enough to check it for a pair ei and ek 6= ej , where ek is another edge incident to
v. Indeed, if e′k has no common vertex with both e′i and e′j , then e′i , e′j and e′k form
a triangle in G′ (because e′k has a common vertex with e′i and with e′j ). Hence, ei ,
ej and ek form a triangle in G, but they have a common vertex v. Contradiction.
Now we need to extend ψ to vertices belonging to Ṽ (G1 ). Note that each vertex
v ∈ Ṽ (G1 ) has exactly one adjacent vertex. There are two possibilities.
1◦ Adjacent vertex u of v belongs to Vb (G). Consider the edge euv ∈ E. (There
might be several such edges, but this is not important, because in G′ they are also
multiple.) Knowing the image ψ(euv ) and the vertex ψ(u), we define ψ(v) as the
vertex of ψ(euv ) different from ψ(u).
2◦ Adjacent vertex u of v belongs to Ṽ (G). Consider edge euv ∈ E Knowing
ψ(euv ), we define ψ(u) and ψ(v) as the vertices of edge ψ(euv ) (not important
which is mapped to which).
Since G′ has no isolated vertices and each edge e′ has exactly two incident vertices
from ψ(V ), we get that ψ : G → G′ is surjective. Hence, ψ : G → G′ is an
isomorphism (otherwise it must be non-injective on vertices and, hence, |V (G)| >
|V (G′ )|). Therefore G and G′ are isomorphic.

Proof of Theorem 5. Let G and G′ be a pair of graphs such that their filtered
algebras KG and KG′ are isomorphic. Without loss of generality, we can assume
that |E(G)| ≤ |E(G′ )|. Denote the numbers of vertices in G and G′ by n + 1 and
n′ + 1 resp.
We consider KG as a subalgebra in ΦG . The elements Yei = exp(Xi )−1, i ∈ [0, n]
form a set of generators of KG . Denote by Zei ∈ KG , i ∈ [0, n′ ] the elements
corresponding to the vertices of G′ under the isomorphism of filtered algebras. The
ei , i ∈ [0, n′ ]} is also a generating set for KG which gives the same filtered
set {Z
structure and satisfies the assumptions of Lemma 4. In order to avoid confusion,
ej the j-th vertex of graph G′ .
we call Yei the i-th vertex of graph G, and we call Z
ei , i ∈ [0, n′ ] determine the same graded structure, then,
Since Yei , i ∈ [0, n] and Z
in particular,
e0 , . . . , Z
en′ }.
span{1, Ye0 , . . . , Yen } = span{1, Z
Additionally, by Lemma 4, Yei , i ∈ [0, n] and Zei , i ∈ [0, n′ ] are nilpotents, implying
that
e0 , . . . , Z
en′ }.
span{Ye0 , . . . , Yen } = span{Z

Firstly, we need to show that each edge-element φe belongs to at most two
ei ’s. Assume the contrary, i.e., that φe belongs to Z
ei , Z
ej and Z
ek . Then
different Z
there exist three distinct non-zero coefficients r1 , r2 , r3 ∈ K such that φe does not
ej + r3 Zek . Moreover, for generic distinct non-zero coefficients
ei + r2 Z
belong to r1 Z
′
′
′
ek if and only if
ei + r2′ Zej + r3′ Z
r1 , r2 , r3 ∈ K, element φe′ (e′ ∈ E(G)) belongs to r1′ Z

“K-THEORETIC” ANALOG DISTINGUISHES GRAPHS

7

ei , Z
ej and Z
ek . Hence by Lemma 3,
φe′ belongs to at least one of Z

′ e
′ e
ek ) < d(r′ Z
e
ej + r3 Z
ei + r2 Z
d(r1 Z
1 i + r2 Zj + r3 Zk ).

But at the same time, by Lemma 4 (3), they should coincide, contradiction.
ei .
By Lemma 4, for any i ∈ [0, n′ ], the degree d(Zei ) equals to the valency of Z
Therefore,
n′
X
′
d(Zei ) ≤ 2|E(G)|,
2|E(G )| =
i

because each edge-element is included in at most two Zei . Since |E(G)| ≤ |E(G′ )|,
we conclude that |E(G)| = |E(G′ )|. Furthermore, by Lemma 4 (2), each element
ei , i ∈ [0, n′ ] with the opposite
φe , e ∈ E(G) belongs exactly to two vertices from Z
′
coefficients. Since |E(G)| = |E(G )|, we can additionally assume that the number
of pairs of non-multiple edges which have a common vertex in G′ is bigger than
that in G.
So far we have constructed a bijection between the edges of G and the edges of
G′ . We want to prove that this bijection provides a graph isomorphism. We will
achieve this as a result of the 5 claims collected in the following proposition which
is closely related to Lemma 5.
Proposition 1. The following facts hold.
(1) If φe1 and φe2 have no common vertex in G, then they have no common
vertex in G′ as well.
(2) If φe1 and φe2 are multiple edges in G, then they are multiple edges in G′
as well.
(3) If φe1 and φe2 have exactly one common vertex in G, then they have exactly
one common vertex in G′ as well.
(4) If φe1 , φe2 and φe3 form a star in G, then they form a star in G′ as well.
(Three edges form a star if they have one common vertex and their three
other ends are distinct.)
(5) If φe1 , φe2 and φe3 form a triangle in G, then they form a triangle in G′
as well.
Proof. To prove (1), assume the contrary, i.e., assume that φe1 and φe2 belong to
ej (and denote the corresponding coefficients by a and b resp.). Since elements
Z
e0 , . . . , Z
en′ have no monomial φe1 φe2 as
e
Y0 , . . . , Yen have no monomial φe1 φe2 , then Z
well (since their spans coincide). Then ln(1 + Zej ) contains the monomial φe1 φe2
with the coefficient −ab.
Pn′
ei), then there exists k ∈ [0, n′ ], k 6= i such
By Lemma 4 (2), we have i=0 ln(1+ Z
ek
e
that ln(1 + Zk ) contains the monomial φe1 φe2 with a non-zero coefficient. Then Z
ek does not contains φe1 φe2 ). Hence, Zek has φe1
must contain φe1 and φe2 (since Z
ek ) contains monomial
and φe2 with coefficients −a and −b resp. Therefore ln(1 + Z
Pn′
e
φe1 φe2 with the coefficient −(−a)(−b) = −ab. Thus the sum
j=0 ln(1 + Zj )
contains φe1 φe2 with coefficient −2ab, contradiction.
To prove (2), consider the map from span{Ye0 , . . . , Yen } to K2 , sending an element
from the span to the pair of coefficients of φe1 and φe2 resp. Since edges e1 and e2 are
multiple in G, the image of this map has dimension 1. If φe1 and φe2 are not multiple
e0 , . . . , Z
en′ } = span{Ye0 , . . . , Yen } has
in G′ , then the image of the map from span{Z
dimension 2.
To prove (3), observe that we have already settled Claims 1 and 2, and also
we additionally assumed that the number of pairs of edges which have a common

8

G. NENASHEV AND B. SHAPIRO

vertex in G′ is bigger than that in G. Then each such pair of edges from G is
mapped to the pair of edges from G′ with the same property.
To prove (4), consider the map from span{Ye0 , . . . , Yen } to K3 , sending an element
in the span to the triple of coefficients of φe1 , φe2 and φe3 resp. The image of this
map has dimension 3. However if φe1 , φe2 and φe3 form a triangle in G′ , then the
e0 , . . . , Z
en′ } has dimension 2.
image of the map from span{Z
Proof of (5) is similar to that of (4).

Now applying Lemma 5 we finish our proof of Theorem 5.



3. Further generalizations
In this section we will consider the Hilbert series of other filtered algebras similar
to KG . (Recall that the Hilbert series of a filtered algebra is, by definition, the
Hilbert series of its associated graded algebra.)
Let f be a univariate polynomial or a formal power series over K. We define the
subalgebra F [f ]G ⊂ ΦG as generated by 1 together with
X

ci,e φe , i = 0, . . . , n.
f (Xi ) = f
Example 1. For f (x) = x, F [f ]G coincides with CG . For f (x) = exp(x), F [f ]G
coincides with KG .

Obviously, the filtered algebra F [f ]G does not depend on the constant term of f.
From now on, we assume that f (x) has no constant term, since for any g such that
f − g is constant, the filtered algebras F [f ]G and F [g]G are the same.
Proposition 2. Let f be any polynomial with a non-vanishing linear term. Then
algebras CG and F [f ]G coincide as subalgebras of ΦG .
Proof. The argument is the same as in the proof of Lemma 1. We only need to
change exp(x) − 1 to f (x) and ln(1 + y) to f −1 (y).

Theorem 6. Let f be any polynomial with non-vanishing linear and quadratic
terms. Then given two simple graphs G1 and G2 , F [f ]G1 and F [f ]G2 are isomorphic
as filtered algebras if and only if G1 and G2 are isomorphic graphs.
Proof. Repeat the proof of Theorem 5.



3.1. Generic functions f and their Hilbert series. Since Xidi +1 = 0 for any i,
we can always truncate any polynomial (or a formal power series) f at degree |G|+1
without changing F [f ]G . Therefore, for a given graph G, it suffices to consider f
as a polynomial of degrees less than or equal to |G|. To simplify our notation, let
us write HSf,G instead of HSF [f ]G .
Given a graph G, consider the space of polynomials of degree less than or equal
to |G| and the corresponding Hilbert series.
Proposition 3. In the above notation, for generic polynomials f of degree at most
|G|, the Hilbert series HSf,G is the same. This generic Hilbert series (denoted by
HSG below) is maximal in the majorization partial order among all HSg,G , where
g runs over the set of all formal power series with non-vanishing linear term.
Recall that, by definition, a sequence (a0 , a1 , . . .) is bigger than (b0 , b1 , . . .) in the
majorization partial order if and only if, for any k ≥ 0,
k
X
i=0

ai ≥

k
X

bi .

i=0

More information about the majorization partial order can be found in e.g. [2].

“K-THEORETIC” ANALOG DISTINGUISHES GRAPHS

9

Proof. Note that, for a function f, the sum of the first k + 1 entries of its P
Hilbert sen
ries HSf,G equals the dimension of span{f α0 (X0 )f α1 (X1 ) · · · f αn (Xn ) :
i=0 αi ≤
k}. It is obvious that, for a generic f, this dimension is maximal. Since all Hilbert
series HSf,G are polynomials of degree at most |G| + 1, then the required property
has to be checked only for k ≤ [G|. Therefore it is obvious that, for generic f , their
Hilbert series is maximal in the majorization order.

Remark 3. We know that the Hilbert series of the graded algebra CG is a specialization of the Tutte polynomial of G. However we can not calculate the Hilbert
series of KG from the Tutte polynomial of G, because there exists a pair of graphs
(G, G′ ) with the same Tutte polynomial and different HSKG and HSKG′ , see Example 2.
Additionally, notice that, in general, HSexp,G := HSKG 6= HSG . Analogously
we can not calculate generic Hilbert series HSG from the Tutte polynomial of G,
see Example 2.
b

b

b

b

b
b

b
b

G1

G2

Figure 1. Graphs with the same matroid and different
“K-theoretic” and generic Hilbert series.
Example 2. Consider two graphs G1 and G2 presented in Fig. 1. It is well-known
that G1 and G2 have isomorphic matroids and hence, the same Tutte polynomial.
Therefore, the Hilbert series of CG1 and CG2 coincide. Namely,
HSCG1 (t) = HSCG2 (t) = 1 + 3t + 6t2 + 9t3 + 8t4 + 4t5 + t6 .
However, the Hilbert series of “K-theoretic” algebras are distinct. Namely
HSKG1 (t) = 1 + 4t + 10t2 + 14t3 + 3t4 ,
HSKG2 (t) = 1 + 4t + 10t2 + 15t3 + 2t4 .
Moreover their generic Hilbert series are also distinct and different from their “Ktheoretic” Hilbert series. Namely,
HSG1 (t) = 1 + 4t + 10t2 + 15t3 + 2t4 ,
HSG2 (t) = 1 + 4t + 10t2 + 16t3 + t4 .
Putting our information together we get,
HSCG1 = HSCG2 ≺ HSKG1 ≺ HSKG2 = HSG1 ≺ HSG2 ,
where ≺ denotes the majorization partial order.

10

G. NENASHEV AND B. SHAPIRO

4. “K-theoretical” analog for spanning trees
For an arbitrary loopless graph G on the vertex set {0, ..., n}, let ΦTG be the graded
commutative algebra over a given field K generated by the variables φe , e ∈ G, with
the defining relations:
(φe )2 = 0,
Y

φe = 0,

for any edge e ∈ G;

for any non-slim subgraph H ⊂ G,

e∈H

where a subgraph H is called slim if its complement G \ H is connected.
T
Let CG
be the subalgebra of ΦTG generated by the elements
X
XiT =
ci,e φe ,
e∈G

for i = 1, ..., n, where ci,e is given by (1). (Notice that XiT and Xi are defined by
exactly the same formula but in different ambient algebras.)
T
Algebra CG
will be called the spanning trees counting
Q algebra of G and is, obviously, the quotient of CG modulo the set of relations e∈H φe = 0 over all non-slim
subgraphs H. Its defining set of relations is very natural and resembles that of (2).
Namely, define the ideal JGT in K[x1 , . . . , xn ] as generated by the polynomials:
!DI
X
T
pI =
,
(4)
xi
i∈I

where I ranges over all nonempty subsets in {1, . . . , n} and the number DI is the
T
same as in (2). Set BG
:= K[x1 , . . . , xn ]/JGT . One of the results of [4] claims the
following.
Theorem 7. [Theorems 9.1 and Corollary 10.5 of [4]] For any simple graph G
T
T
on the set of vertices {0, 1, . . . , n}, algebras BG
and CG
are isomorphic. Their total
T
dimension is equal to the number of spanning trees in G. The dimension dim BG
(k)
T
of the k-th graded component of BG equals the number of spanning trees T in G
with external activity |G| − n − k.
T
Similarly to the above, we can define the filtered algebra KG
⊂ ΦTG which is
T
T
isomorphic to CG as a non-filtered algebra. Namely, KG is defined by the generators:
Y
YiT = exp(XiT ) =
(1 + ci,e φe ), i = 0, . . . , n.
e∈G

T
The first result of this section is as follows. Define the ideal IG
⊆ K[y0 , y1 , . . . , yn ]
as generated by the polynomials:
!DI
Y
T
qI =
,
(5)
yi − 1
i∈I

where I ranges over all nonempty proper subsets in {0, 1, . . . , n} and the number
DI is the same as in (2), together with the generator
T
q{0,1,...,n}

=

n
Y

yi − 1.

i=0
T
T
.
:= K[y0 , . . . , yn ]/IG
Set DG

We present two results similar to the case of spanning forests.

(6)

“K-THEORETIC” ANALOG DISTINGUISHES GRAPHS

11

T
T
T
T
Theorem 8. For any simple graph G, algebras BG
, CG
, DG
and KG
are isomorphic
as (non-filtered) algebras. Their total dimension is equal to the number of spanning
trees in G.
T
T
Proof. The proof is similar to that of Theorem 2. Algebras CG
and KG
coincide
T
T
T
as subalgebras of ΦG (but they have different filtrations); algebras CG and BG
are
T
T
isomorphic by Theorem 7. The proof of the isomorphism between
D
and
B
G
G is
Pn
T
the same as above; we only need to add the variable x0 = −( i=1 xi ) to BG
. 
T
T
Theorem 9. For any simple graph G, algebras DG
and KG
are isomorphic as
filtered algebras.

Proof. Similar to the above proof of Theorem 3.



To move further, we need to give a definition.
b ⊆ G as
Definition 1. Let G be a connected graph. We define its ∆-subgraph G
the subgraph with following edges and vertices:
b if e is not a bridge (i.e., G \ e is still connected),
• e ∈ E(G),
b if there is an edge e ∈ E(G)
b incident to v.
• v ∈ V (G),

b contains more information about G than its matroid, because
In general, G
there exist graphs with isomorphic matroids and non-isomorphic ∆-subgraphs, see
Figure 2.
T
Recall that in a recent paper [3], the first author has shown that CG
depends
only on the bridge-free matroid of G. Namely,

Proposition 4. [Proposition 12 of [3]] For any two connected graphs G1 and G2
T
with isomorphic bridge-free matroids (matroids of their ∆-subgraphs), algebras CG
1
T
and CG2 are isomorphic.
Unfortunately, we can not prove the converse implication at present although we
conjecture that is should hold as well, see Conjecture 6 in § 5. In case of filtered
T
T
algebra KG
and KG
we can also prove an appropriate result only in one direction,
1
2
see Proposition 5.
Similarly to § 3 we can to define F [f ]TG ⊂ ΦG . Let f be a univariate polynomial
or a formal power series over K. We define the subalgebra F [f ]TG ⊂ ΦG as generated
by 1 and by

X
f (XiT ) = f
ci,e φe , i = 0, . . . , n.
Proposition 5. For univariate polynomial f and any two connected graphs G1 and
b1 and G
b 2 , algebras F [f ]T and F [f ]T are isoG2 with isomorphic ∆-subgraphs G
G1
G2
T
T
morphic as filtered algebras. Additionally, KG
and
K
are
isomorphic
as filtered
G2
1
algebras.

Proof. Note that if G has a bridge e, then filtered algebra F [f ]TG is the Cartesian
product of filtered algebras F [f ]TG′ and F [f ]TG′′ , where G′ and G′′ are connected
component of G \ e.
Thus filtered algebra F [f ]TG is the Cartesian product of such filtered algebras
corresponding to the connected components of the ∆-subgraph of G.
Therefore if connected graphs G1 and G2 have isomorphic ∆-subgraphs, then

their filtered algebras F [f ]TG1 and F [f ]TG2 are isomorphic.
Remark 4. In general case we can not prove that these algebras distinguish graphs
with different ∆-subgraphs. The proof of Theorem 5 does not work for two reasons.
Firstly, d(Yei ) is not the degree of the i-th vertex in G. Secondly, even if we can

12

G. NENASHEV AND B. SHAPIRO

construct a similar bijection between edges, we do not have an analog of Proposition 1. Since in the proof we consider coefficients of monomial φe1 φe2 , in case when
e1 and e2 are not bridges and when {e1 , e2 } is a cut, this monomial can still lie in
the ideal.
It is possible to construct such a bijection in a smaller set of graphs, namely
for graphs such that, for any edge e in the graph, there is another edge e′ which
is multiple to e. For such graphs we do not have the second problem, because
if {e1 , e2 } is a cut, then e1 and e2 are multiple edges. So, instead of the actual
converse of Proposition 5, we can prove the converse in the latter situation, but we
do not present this result here.
Proposition 6. In the above notation, for generic polynomials f of degree at most
|G|, the Hilbert series HSF [f ]TG is the same. This generic Hilbert series (denoted
by HSGT below) is maximal in the majorization partial order among HSF [g]TG for
g running over the set of power series with non-vanishing linear term.
Proof. See the proof of Proposition 3.



Example 3. Consider two graphs G1 and G2 , see Fig. 2. It is easy to check that
b 1 and G
b 2 have isomorphic matroids, implying that algebras C T and
subgraphs G
G1
T
CG2 are isomorphic.
b
b

b

b

b

b
b

b

b
b

b
b

b
b
b

b
b

b

b
b

b

b
b

d

G2

G2

G1

b

b
b

d

G1

b
b

Figure 2. Graphs and their ∆-subgraphs.

HSCGT (t) = HSCGT (t) = 1 + 4t + 4t2 .
1

2

The Hilbert series of “K-theoretic” algebras are distinct, namely
HSKTG (t) = 1 + 5t + 3t2 ,
1

HSKTG (t) = 1 + 6t + 2t2 .
2

These graphs are “small”, so their generic Hilbert series coincides with the “Ktheoretic” one. Putting our information together, we get
HSCGT = HSCGT ≺ HSKTG = HSG1 T ≺ HSKTG = HSG2 T .
1

2

1

2

5. Related problems.
At first, we formulate several problems in case of spanning forests; their analogs
for spanning trees are straight-forward.
Problem 1. For which functions f besides a + bx and a + bex , one can present
relations in F [f ]G for any graph G in a simple way? In other words, for which f,
one can define an algebra similar to BG and DG ?

“K-THEORETIC” ANALOG DISTINGUISHES GRAPHS

13

Since the Hilbert series HSKG and HSG are not expressible in terms of the Tutte
polynomial of G, they contain some other information about G.
Problem 2. Find combinatorial description of HSKG and HSG ?
Problem 3. For which graphs G, Hilbert series HSKG and HSG coincide? In
other words, for which G, exp is a generic function?
Problem 4. Describe combinatorial properties of HSf,G when f is a function
starting with a monomial of degree bigger than 1, i.e. f (x) = xk + · · · , k > 1? In
particular, calculate the total dimension of F [f ]G .
The most delicate and intriguing question is as follows.
Problem 5. Do there exist non-isomorphic graphs G1 and G2 such that, for any
polynomial f (x), the Hilbert series HSf,G1 and HSf,G2 coincide? In other words,
does the collection of Hilbert series HSf,G taken over all formal series f determine
G up to isomorphism?
The following problems deal with the case of spanning trees only.
T
T
Conjecture 6. [comp. [3]] Algebras CG
and CG
for graphs G1 and G2 are isomor1
2
phic if and only if their bridge-free matroids are isomorphic, where the bridge-free
matroid is the graphical matroid of ∆-subgraph.

Problem 7. Which class of graphs satisfies the property that if two graphs G1
T
T
and G2 from this class have isomorphic KG
and KG
, then their ∆-subgraphs are
1
2
isomorphic. In other words, can one classify all pairs (G1 , G2 ) of connected graphs,
T
T
which has isomorphic filtered algebras KG
and KG
? (The same problem for F [f ]TG1
1
2
and F [f ]TG2 , where f (x) = x + ax2 + · · · )
References
[1] F. Ardila, A. Postnikov, Combinatorics and geometry of power ideals, Trans. of the AMS,
362(8), (2010), 4357–4384.
[2] A. W. Marshall, I. Olkin, B. Arnold, Inequalities: Theory of Majorization and Its Applications, Second edition. Springer Series in Statistics. Springer, New York, 2011.
[3] G. Nenashev, On Postnikov-Shapiro Algebras and their generalizations, arXiv:1509.08736.
[4] A. Postnikov, B. Shapiro, Trees, parking functions, syzygies, and deformations of monomial
ideals. Trans. Amer. Math. Soc. 356(8) (2004), 3109–3142
[5] A. Postnikov, B. Shapiro, M. Shapiro, Algebras of curvature forms on homogeneous manifolds.
Differential topology, infinite-dimensional Lie algebras, and applications, 227–235, Amer.
Math. Soc. Transl. Ser. 2, 194, Amer. Math. Soc., Providence, RI, 1999
[6] B. Shapiro, M. Shapiro, On ring generated by Chern 2-forms on SLn /B. C. R. Acad. Sci.
Paris Sr. I Math. 326(1) (1998), 75–80.
Department of Mathematics, Stockholm University, SE-106 91, Stockholm, Sweden
E-mail address: nenashev@math.su.se
Department of Mathematics, Stockholm University, SE-106 91, Stockholm, Sweden
E-mail address: shapiro@math.su.se

