POSTNIKOV-SHAPIRO ALGEBRAS, GRAPHICAL
MATROIDS AND THEIR GENERALIZATIONS

arXiv:1509.08736v4 [math.CO] 5 Mar 2017

GLEB NENASHEV
Abstract. A.Postnikov and B.Shapiro introduced a class of commutative algebras which enumerate forests and trees of graphs.
Our main result is that the algebra counting forests depends only
on graphical matroid and the converse.
By these algebras we motivate generalization of the definition of
spanning forests and trees for hypergraphs and the corresponding
"hypergraphical" matroid. We present 3 different equivalent definitions, which can be read independently from other parts of the
paper.

Contents
1. Introduction
1
2. Algebras and Matroids
4
3. Algebras associated with t-labelled forests
10
4. Vector configurations and Hypergraphs
13
5. Algebras corresponding to spanning trees, Problems 18
References
20

1. Introduction
There are a lot of results about enumeration of spanning trees and
forests of graphs. The famous matrix-tree theorem of Kirchhoff (see [16]
and p. 138 in [26]) claims that the number of spanning trees of a given
graph G equals the determinant of the Laplacian matrix of G. Many
generalizations of the classical matrix-tree theorem were constructed
in a long period, e.g. for directed graphs, matrix-forest theorems, etc
(see e.g. [8], see [6] and references therein). It is also well known that
the number of maximal spanning forests of G (or equivalently trees for
connected G) equals TG (1, 1) while the number of all spanning forests
of G equals TG (2, 1), where TG is the Tutte polynomial of G (see p. 237
in [26]).
We focus here on algebras introduced by A. Postnikov and B. Shapiro
in [22] and on graphical matroids, both objects enumerate spanning
Key words and phrases. Commutative algebra, Graph, Hypergraph, Matroid,
Spanning trees and forests, Tutte polynomial.
1

2

G. NENASHEV

trees and forests. Before our paper there was no direct relation between them, only across the Tutte polynomial, Critical group (Sandpile
model). Also with the motivation given by these algebras we introduce
3 equivalent definitions of spanning trees (forests) of a hypergraph and
present corresponding "hypergraphical" matroid. If you are interested
only in the latter, scroll to section 4.2.
The field K of zero characteristic is fixed throughout this paper, for
example C or R. By a graph we always mean an undirected graph
without loops (multiple edges are allowed). We use the standard notation: E(G) and e(G) are the set and the number of edges of graph
G; V (G) and v(G) are the set and the number of vertices of G; c(G)
is the number of connected components of G and TG (x, y) is the Tutte
polynomial of G.
At first, we present two definitions of Postnikov-Shapiro algebras
counting spanning forests.
Notation 1.1. Take an undirected graph G on n vertices.
(I) Let ΦFG be the commutative algebra over K generated by {φe : e ∈
E(G)} satisfying the relations φ2e = 0, for any e ∈ E(G).
Fix any linear order of vertices of G. For i = 1, . . . , n, set
X
Xi =
ci,e φe ,
e∈G

where

ci,e

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

Denote by CGF the subalgebra of ΦFG generated by X1 , . . . , Xn .
(II) Consider the ideal JGF in the ring K[x1 , · · · , xn ] generated by
!DI +1
X
pFI =
xi
,
i∈I

where I ranges over all nonempty subsets of vertices, and DI is the total
number of edges between vertices in I and vertices outside I. Define
F
the algebra BG
as the quotient K[x1 , . . . , xn ]/JGF .
Remark 1.1. In the first definition, the order of vertices is not important. Easy to see that all such algebras are isomorphic to the above
definition of CGF , even though we can separately choose the "smallest"
vertex for each edge. For an orientation G of graph G, we denote by CGF
the subalgebra of {φe : e ∈ E(G)}, where ci,e = 1 for the end of e and
−1 for the beginning of e.
The original motivation of these algebras is that, for the complete
graph Kn , the algebra is isomorphic to the cohomology ring of the flag

POSTNIKOV-SHAPIRO ALGEBRAS AND MATROIDS

3

manifold F ln , see [23] and [24]. Algebras of complete graphs are also
related to Fomin-Kirillov and Orlik-Terao algebras, see their definition
in [11], [20] and relations between the last two in [18]. In paper [4] a big
class of algebras was considered, which includes our case, Orlik-Terao
and others. Postnikov-Shapiro algebras have direct connections with
G-parking functions (see [22], [9]), whose are stable configurations of
the sandpile model introduced in [10].
F
T
There are a few generalizations of BG
and BG
in the literature (the
latter algebra counts trees in G instead of forests, see notation in section 5), see the most important generalizations in papers [2] and [13].
In both papers the main object of the generalizations is the algebra
of the second definition (quotient algebra), they defined the so called
Zonotopal algebras, where dimensions of algebras are numbers of lat∆
tice points of corresponding zonotops. In [14] the definitions of BG
and
∆
CG were given in terms of some simplex complex ∆ on the set of verF
T
tices of G. With this definition algebras BG
and BG
become particular
cases corresponding to different simplexes.
We need the following classic notation, which was constructed by
Tutte for his original definition of the polynomial.
Notation 1.2. Fix some linear order on the set E(G) of edges of G.
Let F be any spanning forest in G. By actG (F ) denote the number of
all externally active edges of F , i.e. the number of edges e ∈ E(G) \ F
such that (i) subgraph F + e has a cycle; (ii) e is the minimal edge in
this cycle in the above linear order.
Denote by F + the set of edges of the forest F together with all externally active edges, and denote by F − = E(G) \ F + the set of externally
nonactive edges.
The following theorem is the main result of [22], which shows that
both definitions are equivalent and why it is called algebra counting
spanning forests.
F
Theorem 1.1 (cf. [22]). For any graph G, algebras BG
and CGF are
isomorphic, their total dimension over K is equal to the number of
spanning forests in G.
Moreover, the dimension of the k-th graded component of these algebras equals the number of spanning forests F of G with external activity
e(G) − e(F ) − k.

In fact, the second part of Theorem 1.1 claims that the above Hilbert
polynomial is a specialization of the Tutte polynomial of G.
Corollary 1.1. Given a graph G, the Hilbert series of the algebra CGF
is given by


1
HCGF (t) = TG 1 + t,
· te(G)−v(G)+c(G) ,
t

4

G. NENASHEV

where c(G) is the number of the connected components of G.
Both definitions of algebras are important, and sometimes it is easier
to use the first and sometimes the second. For example: if you want
to use computer algebra, then the first is better, because it has less
relations, but in fact, the first definition is subalgebra of the bigger
algebra ΦFG .
The structure of the paper is the following:
In § 2 we show that the Postnikov-Shapiro algebras counting spanning forests and graphical matroids are in one to one correspondence,
see Theorem 2.1. It means that these algebras store almost all information about the graphs.
In § 3 we consider t-labelled analouge of algebras, namely we use the
condition φt+1
= 0 instead φ2e = 0. The similar properties hold and a
e
new property that we can reconstruct the Tutte polynomial from the
Hilbert series of the algebra corresponding to large t, see Theorem 3.3.
In § 4 we construct a family of algebras corresponding to a given
hypergraph, and we present a natural definition of a matroid of a hypergraph such the Hilbert series of algebras is a specialization of the
Tutte polynomial corresponding to this matroid.
In § 5 we discuss similar problems for algebras counting spanning
trees and formulate Conjecture 1.
Acknowledgement. I am grateful to my supervisor Boris Shapiro
for introducing me to this area, for his comments and editorial help
with this text.
2. Algebras and Matroids
Obviously, the original Postnikov-Shapiro algebra corresponding to
a disconnected graph G is the Cartesian product of the algebras corresponding to the connected components of G. In particular, it is also
true for 2-connected components (maximal connected subgraphs such
that they remain connected, after removal of any vertex). The same
fact is also true for matroids. In this section we prove the following
result.
F
F
Theorem 2.1. Algebras BG
and BG
for graphs G1 and G2 are iso1
2
morphic if and only if the graphical matroids of these graphs coincide.
P.S. The algebraic isomorphism can be thought of either as graded or
as non-graded, the statement holds in both cases.

In the subsequent paper [19] filtered algebras are considered, that
distinguish graphs. The proof is based on some ideas from this paper
and on another trick, that makes a proof easier. Here we should proof
both sides and in the proof of Theorem 2.1 we use the following theorem
of H. Whitney.

POSTNIKOV-SHAPIRO ALGEBRAS AND MATROIDS

5

Theorem 2.2 (Whitney’s 2-isomorphism theorem, see [27], [21]). Let
G1 and G2 be two graphs. Then their graphical matroids are isomorphic
if and only if G1 can be transformed to a graph, which is isomorphic
to G2 by a sequence of operations of vertex identification, cleaving and
twisting.
These three operations are defined below.
1a) Identification: Let v and v ′ be vertices from different connected
components of the graph. We modify the graph by identifying v and
v ′ as a new vertex v ′′ .
1b) Cleaving (the inverse of identification): A graph can only be cleft
at a cut-vertex.
2) Twisting: Suppose that the graph G is obtained from two disjoint
graphs G1 and G2 by identifying vertices u1 of G1 and u2 of G2 as the
vertex u of G and additionally identifying vertices v1 of G1 and v2 of
G2 as the vertex v of G. In a twisting of G about {u, v}, we identify
u1 with v2 and u2 with v1 to get a new graph G′ .
We split our proof of Theorem 2.1 in two parts presented in § 2.1 and
in § 2.2.
2.1. Algebras are isomorphic if their matroids are isomorphic.
F
Because algebras BG
and CGF are isomorphic for any graph by Theorem 1.1, it suffices to prove Theorem 2.1 for algebras CGF 1 and CGF 2 .
Lemma 2.1. If graphs G and G′ differ by a sequence of Whitney’s
deformations, then the algebras CGF and CGF ′ are isomorphic.
Proof. It is sufficient to check the claim for each deformation separately.
1◦ Identification and Cleaving. We need to prove our fact only for
cleaving, because identification is the inverse of cleaving.
In this case algebras doesn’t change, because the linear subspace
defined by Xi for vertices doesn’t change. This holds, because if we
split a vertex k into k ′ and k ′′ , then in the new graph, Xk′ equals to
the minus sum of Xi corresponding to the vertices from its component
except k ′ (sum of all X. from one connected component is zero), i.e.
Xk′ belongs to the linear space <X1 , . . . , Xk−1 , Xk+1, . . . , Xn >. Similarly Xk′′ belongs to the linear space <X1 , . . . , Xk−1 , Xk+1, . . . , Xn >.
Hence, <X1 , . . . , Xk′ , Xk′′ , . . . , Xn > is a subspace of the linear space
<X1 , . . . , Xn >. The equation, Xk = Xk′ + Xk′′ implies that these linear spaces coincide.
2◦ Whitney’s deformation of the second kind. Define the digraph
G as the orientation of the graph G, where each arrow goes to the
"smallest" vertex (see Remark 1.1).
Let us make a twist of the vertices u and v. Let G1 and G2 be the
orientations of G1 and G2 corresponding to G. Let G′ be the orientation
of G′ corresponding to the gluing G1 and G2 with reversing each arrow

6

G. NENASHEV

from G2 . Vertex u′ in G′ is obtained by gluing of u1 and v2 ; v ′ is
obtained by gluing of v1 and u2 .
Let Xk , X1,k , X2,k and Xk′ be the sums with signs of edges incident
to vertex k in graphs G, G1 , G2 and G′ .
For a vertex k of G1 except u1 and v1 , we get
Xk = X1,k = Xk′ .
For a vertex k of G2 except u2 and v2 , we get
Xk = X2,k = −Xk′ , because we reverse the orientation in the second
part of twisting.
For other vertices we have:
Xu = X1,u1 + X2,u2 ;
Xv = X1,v1 + X2,v2 ;
Xu′ ′ = X1,u1 − X2,v2 = Xu − (X2,u2 + X2,v2 );
Xv′ ′ = X1,v1 − X2,u2 = Xv − (X2,u2 + X2,v2 ).
We know that the sum of variables corresponding to the vertices of any
graph is zero, because each edge goes with a plus to one vertex and
with a minus to another. We have
X
X2,k = 0,
X

k∈G2

X2,k + X2,u2 + X2,v2 = 0,

k∈G2 \u2 ,v2

X2,u2 + X2,v2 = −

X

X2,k = −

k∈G2 \{u2 ,v2 }

Xu′ ′

Xv′ ′

X

Xk .

k∈G2 \{u2 ,v2 }

belong to the linear space generated by Xk , where
and
Hence,
k ∈ G. In other words, the linear space for G′ is a linear subspace of
the space for G. Similarly we can prove the converse. Then, the linear
spaces coincide, and since we have the same relations (φ2e = 0 for any
edge), the algebras in these bases coincide.

We have proved the first part of Theorem 2.1, because if the corresponding graphical matroids are isomorphic, then there exists such a
sequence of Whitney’s operations.
Corollary 2.1. The algebra corresponding to a graph G is the Cartesian product of the algebras corresponding to the 2-connected components of G.
2.2. Reconstruction of the matroid.
Lemma 2.2. It is possible to reconstruct a matroid of a graph G from
the algebra CGF .
Remark 2.1. We assume that we only know CGF as an algebra. I.e.
we assume that we do not know the basis corresponding to the vertices
of G, and that we have no information about the graded components
of CGF .

POSTNIKOV-SHAPIRO ALGEBRAS AND MATROIDS

7

Proof. For an element Y ∈ CGF , we define its length ℓ(Y ) as the minimal
number such that Y ℓ+1 is zero (the length can be infinite).
WePcall an element Y ∈ CGF irreducible if there is no representation
Y = i Z2i−1 Z2i such that ℓ(Zj ) is finite for any j.
Consider a basis {Y1 , ..., Ym } of the algebra CGF with the following
conditions:
• Each Yj is irreducible;
• For any k 6 m, different nonzero numbers r1 , . . . , rk ∈ K, any
r1′ , . . . , rk′ ∈ K and different i1 , . . . , ik ∈ [m], we have
ℓ(r1 Yi1 + · · · + rk Yik ) > ℓ(r1′ Yi1 + · · · + rk′ Yik );
• For any linear combination Y of {Y1 , ..., Ym } and a reducible Z,
P

ℓ(Y ) 6 ℓ(Y + Z);

• i ℓ(Yi ) is minimal.
Such a basis of CGF always exists. For example, the basis X1 , . . . , Xn
(corresponding to the vertices) satisfies the first three conditions. However, the sum of lengths of Xi is not minimal.
For an element Y ∈ CGF , we define its linear part as Y and its remainder as Yb , where Y = Y + Yb , Y belongs to the 1-graded component of
CGF and Yb belongs to the linear span of the other graded components.
Observe that we do not know this decomposition explicitly, because we
do not know the 1-graded component. We say that an edge e belongs
to Y if Y includes the variable φe corresponding to the edge e with a
nonzero coefficient.
Proposition 2.3. A basis {Y1 , ..., Ym } as above satisfies additionally
the following conditions:
(1) The set {Y 1 , ..., Y m } is a basis;
(2) For any linear combination Y of {Y1 , ..., Ym },
ℓ(Y ) = ℓ(Y );
(3) Each edge belongs to one or two Y i and Y j . If it belongs to two,
then with the opposite coefficients;
(4) Each Y i has edges only from one 2-connected component.
Proof. (1). We know that {Y1 , ..., Ym } is a basis. Hence, the 1-graded
component of CGF coincides with a linear span of <Y 1 , ..., Y m >. Then,
<Y 1 , ..., Y m > is also a basis.
(2). For any i ∈ [m], the part Ybi is reducible, otherwise ℓ(Yi ) is
infinite, and the sum in the last condition is infinite. However for
the basis corresponding to the vertices this sum is finite. Then for
any linear combination Y of {Y1 , ..., Ym }, we have ℓ(Y ) 6 ℓ(Y ) < ∞
(by third condition of choice). However, it is clear that ℓ(Y ) > ℓ(Y ).
Hence, ℓ(Y ) = ℓ(Y ) for any Y from the linear space <Y1 , ..., Ym >.

8

G. NENASHEV

(3). Obviously, each edge belongs to at least one Y j , because
any edge belongs to some Xi and this Xi is a linear combination of
Y 1 , ..., Y m .
Assume that there is an edge e, which belongs to Y i1 , Y i2 and Y i3 .
Then there are different nonzero numbers r1 , r2 and r3 such that, for
Y = r1 Y1 + r2 Y2 + r3 Y3 , Y without e. Then ℓ(Y ) is at most the number
of all edges in Y i1 , Y i2 and Y i3 minus one.
Consider r1′ , r2′ and r3′ in general position, then, for Y ′ = r1′ Y1 +
r2′ Y2 + r3′ Y3 , ℓ(Y ′ ) is the number of all edges in Y i1 , Y i2 and Y i3 . We
have
ℓ(r1 Y1 + r2 Y2 + r3 Y3 ) < ℓ(r1′ Y1 + r2′ Y2 + r3′ Y3 ).
Using (2) we also have
ℓ(r1 Y1 + r2 Y2 + r3 Y3 ) < ℓ(r1′ Y1 + r2′ Y2 + r3′ Y3 ),
which contradicts our choice of the basis.
We proved the first part of condition (3); the proof of the second
part is the same, but only for two different r1 and r2 .
(4). Assume the opposite, i.e. that there is Y i which has edges
belonging to two different 2-connected components.
We know that the algebra is the Cartesian product of the subalgebras corresponding to 2-connected components. Then there are Z1
and Z2 from the 1-graded component, such that Y i = Z1 + Z2 and
ℓ(Z1 ), ℓ(Z2 ) < ℓ(Y i ).(For example, Z1 is a part corresponding to some
2-connected component and Z2 is another part).
Because Z1 and Z2 belong to the linear space <Y 1 , ..., Y m >, we
can change Y i to Z1 or Z2 in the basis {Y 1 , ..., Y m }. (Indeed if we
can not do it, then Z1 and Z2 belong to <Y 1 , . . . Y i−1 , Y i−1 , . . . Y m >.
Therefore Y i = Z1 + Z2 also belongs to the latter space). Let us
{Y 1 , . . . Y i−1 , Z1 , Y i−1 , . . . Y m } is also a basis.
We have a new basis {Y 1 , . . . Y i−1 , Z1 , Y i−1 , . . . Y m }, whose sum of
lengths is less than the sum of lengths of {Y 1 , . . . , Y m }, which is equal
to the sum of lengths of {Y1 , . . . , Ym }. And for this basis, the first three
conditions of a choice of basis hold, and the sum of lengths is smaller.
Then we should choose the basis {Y 1 , . . . Y i−1 , Z1 , Y i−1 , . . . Y m } instead
of {Y1 , . . . , Ym }. Contradiction.

Let us now construct the cut space of G. This will finish the proof,
because we can define the graphical matroid in terms of the cut space
of a graph. By a cut we mean a set C of edges such that the subgraph
G \ C has more connected components than G. By an elementary cut
we mean a minimal cut, i.e. a cut, whose arbitrary subset is not a cut.

POSTNIKOV-SHAPIRO ALGEBRAS AND MATROIDS

9

P i
P i
The sum
2 Yi =
2 Yi has each edge with a nonzero coefficient
by (2) of Proposition 2.3. Hence,
!
!
m
m
X
X
e(G) = ℓ
2i Y i = ℓ
2i Y i .
i=1

i=1

Therefore we know the number of edges in the graph.
Consider the set τ = {ψ1 , . . . , ψe(G) } consisting of e(G) elements and
a family of subsets K1 , . . . , Km constructed by the following rules.
ℓ(Y )+ℓ(Y )−ℓ(Y +Y )

j
i
j
own ele• For each pair i and j, we prescribe i
2
ments from τ and add them to both Zi and Zj ;
P
ℓ(Y )+ℓ(Yj )−ℓ(Yi +Yj )
• For every i, we choose ℓ(Yi ) − j6=i ( i
) own el2
ements from τ and add them to Zi .

In fact, for any edge e from G, we choose the corresponding element
ψk(e) and add it to Zi if and only if e belongs to Y i .
Consider the space Γ of subsets in τ with the operation ∆ (symmetric difference) generated by Z1 , . . . , Zm . We want to prove that Γ is
isomorphic to the cut space of G.
Let C be an elementary cut of G. Let XC be the sum of Xi corresponding to the vertices, which belong to some new component
of G \ C (hence, XC is in 1-graded component). Then XC has
an edge with a nonzero coefficient if and only if the edge belongs
to C. Consider the minimal t such that there is a linear combination XC = a1 Y i1 + . . . + at Y it ; consider the sum XC′ = Y i1 + . . . + Y it .
Obviously, XC′ is nonzero and has edges only from the cut C, because
an edge belongs to the sum XC′ if and only if it is exactly in one of
Y i1 , . . . , Y it .
Assume that XC′ has not all edges from XC . Let C ′ be a subset of
the edges of C belonging to XC′ . The set of edges C ′ is not a cut of
G, because C is an elementary cut. Hence, for any edge e ∈ C ′ , there
is a path e1 , . . . , ek in G \ C ′ , such that e, e1 , . . . , ek is a simple cycle.
Let the edge e connect vertices bk and b0 , and the edge ei connect bi−1
and bi P
for any i ∈ [k]. Because XC′ belongs to the 1-graded component,
′
XC = ni=1 abi Xi , where abi ∈ K and Xi are the elements corresponding
to the vertices of G. For i ∈ [k], the edge ei does not belong to XC′ ,
however variable φei belongs only to Xbi−1 and Xbi from {X1 , . . . , Xn }.
Furthermore it belongs to one of {Xbi−1 , Xbi } with coefficient 1 and to
another with −1, hence, b
abi−1 = b
abi . Then, we also have b
ab0 = b
abk .
′
Hence the variable φe belongs to XC with a zero coefficient. Contradiction.
We concluded that a subset of τ corresponding to an elementary cut
belongs to the space Γ. To finish the proof, we need to show, that if a
subset of τ belongs to Γ, then it either corresponds to a cut or to the
empty set.

10

G. NENASHEV

Assume the contrary, i.e. assume that there is Zi1 ∆Zi2 ∆ · · · Zis is
not a cut. Let C be a set of edges from Y i1 + Y i2 + · · · + Y is , then C is
not a cut in G. By Proposition 2.3 we can split the summation into the
summations inside individual connected components (and even inside
2-connected component). Then, for any connected component it is not
a cut.
Let Y ij1 + Y ij2 + · · · + Y ijr corresponds to a connected component
′
G , and has the set of edges C ′ . Then
X
av Xv .
Y ij1 + Y ij2 + · · · + Y ijr =
v∈V (G′ )

We know that G′ \ C ′ is connected. Therefore there is a spanning tree
T in G′ \ C ′ . For any edge P
vi vj from T , we have avi = avj ; otherwise the edge vi vj belongs to v∈V (G′ ) av Xv with a nonzero coefficient.
′
Since
P T is a spanningPtree of G , all coefficients av are the same. Thus
v∈V (G′ ) av Xv = a(
v∈V (G′ ) Xv ) = 0; the last sum is zero, because
the sum of variables corresponding to vertices from a connected component is zero. Then we also have Y i1 + Y i2 + · · · + Y is = 0, hence,
Zi1 ∆Zi2 ∆ · · · Zis is the empty set.
Therefore the space Γ is isomorphic to the cut space of G, i.e. there
is a unique graphical matroid corresponding to CGF .


3. Algebras associated with t-labelled forests
In this section we substitute the square-free algebra ΦFG for the (t+1)free algebra ΦFGt .
Notation 3.1. Take an undirected graph G on n vertices. Let t > 0
be a positive integer.
(I) Let ΦFGt be a commutative algebra over K generated by {φe : e ∈
E(G)} satisfying the relations φt+1
= 0, for any e ∈ E(G).
e
Fix any linear order on the vertices of G. For i = 1, . . . , n, set
X
Xi =
ci,e φe ,
e∈G

where ci,e as in the notation 1.1. Denote by CGFt the subalgebra of ΦFGt
generated by X1 , . . . , Xn .
(II) Consider the ideal JGFt in the ring K[x1 , · · · , xn ] generated by
!tDI +1
X
xi
pFI t =
,
i∈I

where I ranges over all nonempty subsets of vertices, and DI is the total
number of edges between vertices in I and vertices outside I. Define
Ft
as the quotient K[x1 , . . . , xn ]/JGFt .
the algebra BG

POSTNIKOV-SHAPIRO ALGEBRAS AND MATROIDS

11

It enumerates the so-called t-labelled spanning forests.
Consider a finite labelling set {1, 2, . . . , t} containing t different labels.
Definition 3.2. A spanning forest of a graph G with a label from
{1, 2, . . . , t} on each edge is called a t-labelled forest. The weight of
a t-labelled forest F , denoted by ω(F ), is the sum of the labels of all its
edges.
Ft
Theorem 3.1. For any graph G and a positive integer t, algebras BG
and CGFt are isomorphic. Their total dimension over K is equal to the
number of t-labelled forests in G.
Ft
is
The dimension of the k-th graded component of the algebra BG
equal to the number of t-labelled forests F of G with the weight t ·
(e(G) − actG (F )) − k.

b the graph on n vertices and with t · e(G) edges
Proof. Denote by G
b In
such that each edge of G corresponds to its t clones in the graph G.
other words, each edge of G is substituted by its t copies with labels
b are
1, 2, . . . , t. For each edge e ∈ E(G), its clones e1 , . . . , et ∈ E(G)
ordered according to their numbers; clones of different edges have the
same linear order as the original edges. Thus we obtain a linear order
b
of the edges of G.
Consider the following bijection between t-labelled forests in G and
b each t-labelled forest F ⊂ G corresponds to the
usual forests in G:
′
b such that for each edge e ∈ E(F ), the forest F ′ has the
forest F ⊂ G,
clone of the edge e whose number is identical to the label of the edge
e in the forest F .
Obviously,
actGb (F ′ ) = t · actG (F ) + ω(F ) − e(F ),
b = t · e(G). Since BFt and BF are the same, the Hilbert series
and e(G)
G
b
G
Ft
F
of the algebra BG coincides with the Hilbert series of the algebra BG
b,
which settles the second part of Theorem 3.1.
Ft
F
and BG
To prove the first part of this Theorem, observe that BG
b are
F
F
isomorphic, and algebras CGb and BGb are isomorphic. Thus we must
show that algebras CGFb and CGFt are isomorphic. This is indeed true,
because for every edge e ∈ E(G), the elements φe , . . . , φte are linearly
independent in the algebra ΦFGt with coefficients containing no φe . Also
elements (φe1 + · · · + φet ), . . . , (φe1 + · · · + φet )t are linearly independent
in the algebra ΦFGb with coefficients containing no φe1 , . . . , φet , and (φe1 +
· · · + φet )t+1 = 0. Moreover elements φei only occur in the sum (φe1 +

· · · + φet ) in the algebra ΦFGb .

12

G. NENASHEV

Ft
was calculated in papers [2] and [17].
In fact Hilbert Series of BG
b where each edge
Furthermore, the Hilbert Series was computed for G,
is replaced by its own number of edges. The Hilbert series is a specialization of the multivariate Tutte polynomial (see definition in [25]).
When "t" is the same for every edge, the multivariate Tutte polynomial is calculated from the usual Tutte polynomial. So in our case the
Ft
Hilbert Series of BG
is a specialization of the Tutte polynomial of G.
Ft
is
Theorem 3.2. The dimension of the k-th graded component of BG
equal to the coefficient of the monomial y t·e(G)−v(G)+c(G)−k in the polynomial
 t
v(G)−c(G)

 t+1
y −1
y −1 t
,y .
· TG
y−1
y t+1 − y
b constructed in the proof of Theorem 3.1. We
Consider the graph G
need the following technical lemma which was proved in [5].

Lemma 3.1 (Lemma 6.3.24 in [5]).
v(G)−c(G)

 t
 t
y − y + x(y − 1) t
y −1
,y .
· TG
TGb (x, y) =
y−1
yt − 1

After the substitution x → 1 + y1 , we get the following equality.

Corollary 3.1.
v(G)−c(G)

  t
 t+1

y −1
y −1 t
1
,y .
· TG
TGb 1 + , y =
y
y−1
y t+1 − y

Ft
F
is isomorphic to the algebra BG
Proof of Theorem 3.2. Algebra BG
b
(which was shown in the proof of Theorem 3.1), furthermore they are
isomorphic as graded algebras. So it is enough to show that dimenF
sion of the k-th graded component of BG
b is equal to the coefficient of
b

b

b

the monomial y t·e(G)−v(G)+c(G)−k = y e(G)−v(G)+c(G)−k in the polynomial
TGb (1 + y1 , y). This fact is true by Corollary 1.1.

Theorem 3.3. For any positive integer t > n, it is possible to restore
the Tutte polynomial of any connected graph G on n vertices knowing
Ft
.
only the dimensions of each graded component of the algebra BG
Proof. By Theorem 3.1 we know that the degree of the maximal
Ft
nonempty graded component of BG
is equal to the maximum of
t · (e(G) − actG (F )) − ω(F ) taken over F . It attains its maximal value
for the empty forest (i.e. F = ∅). Then we know the value of t · e(G),
and hence, we know the number of edges of the graph G.
Since we know that t · e(G) − v(G) + c(G) = t · e(G) − n + 1 (G
is connected, i.e., c(G) = 1), by Theorem 3.2 we can calculate the
polynomial
 t
v(G)−c(G)

 t+1
y −1
y −1 t
,y
· TG
y−1
y t+1 − y

POSTNIKOV-SHAPIRO ALGEBRAS AND MATROIDS

13

 t+1

−1
from the Hilbert series. Then we can also calculate TG yyt+1 −y
, yt .
It is well P
known that for any graph G, its Tutte polynomial TG (x, y)
is equal to F (x − 1)c(F )−c(G) y actG (F ) , where the summation is taken
over all spanning forests of G. Then we obtain
TG



y t+1 − 1 t
,y
y t+1 − y
=

X
F



=

X  y t+1 − 1
F

y t+1 − y

1
t−1
y(y + · · · + 1)

−1

n−1−e(F )

n−1−e(F )

y t·actG (F ) =

y t·actG (F ) .

Hence, we can restore the polynomial
X
e(F ) t·act (F )+e(F )
y t−1 + · · · + 1
y G
.

(∗)

F

Since e(F ) < t, we can compute the number of usual spanning forests
with a fixed pair of parameters e(F ) and actG (F ). Indeed, consider the
monomial of the minimal degree in the polynomial (∗), and represent
it in the form s · y m . Observe that s is the number
  of spanning forests
F such that F ≡ m (mod t) and actG (F ) = mt . Remove from the
polynomial (∗) all summands for these spanning forests, and repeat
this operation until we get 0. P
Note again that TG (x, y) = a,b #{F : e(F ) = a, act(F ) = b} · (x −
n−1−a
1)
· y b. Therefore we know the whole Tutte polynomial of G, since
we know the number of usual spanning forests with any fixed number
of edges and any fixed external activity.


4. Vector configurations and Hypergraphs
4.1. Algebra corresponding to vector configuration. The following algebra was introduced by A. Postnikov, B. Shapiro and M. Shapiro
in [23].
Notation 4.1. Given a finite set A = {a1 , . . . , am } of vectors in Kn ,
let ΦFm be the commutative algebra over K generated by {φi : i ∈ [m]}
with relations φ2i = 0, for each
P i ∈ [m].
For i = 1, . . . , n, set Xi = k∈[m] ak,i φk . Denote by CA the subalgebra
of ΦFm generated by X1 , . . . , Xn .
The Hilbert series of CA also corresponds to a specialization of the
Tutte polynomial of the corresponding vector matroid, see Theorem 3
in [23].
Theorem 4.1 (cf. [23]). The dimension of algebra CA is equal to the
number of independent subsets in V . Moreover, the dimension of the

14

G. NENASHEV

k-th graded component is equal to the number of independent subsets
S ⊂ A such that k = m − |S| − act(S).
Corollary 4.1. Given a vector configuration A in Kn , the Hilbert series
of algebra CA is


1
HCA (t) = TA 1 + t,
· t|A|−rk(A),
t
where TA is the Tutte polynomial corresponding to A, |A| is the number
of vectors in the configuration and rk(A) is the dimension of the linear
span of these vectors.
The set of different vector configurations depends on continuous parameters. Additionally, there are uncountably many non-isomorphic
algebras each corresponding to its vector configuration. At the same
time the number of matroids is countable, and it is finite for a fixed
number of vectors. It means that there are many different vector configurations with the same corresponding matroid. In other words, it
is in principle impossible to reconstruct a vector configuration and its
algebra from the corresponding matroid.
4.2. Hypergraphs. In this subsection we present a family of algebras
corresponding to a hypergraph. Almost all algebras from this family
(generic algebras) have the same Hilbert series and this generic Hilbert
series counts forests of this hypergraph. There are many definitions of
spanning trees of a hypergraph, for example: a spanning cacti in [1]; a
hypertree in [7] (also known as an arboreal hypergraph in [3]). However all these definitions allow trees to have different number of edges,
whence spanning tree of a usual graph should have the same number
of edges. We define spanning trees such that this property holds and
also other natural properties hold. Also we define the hypergraphical
matroid and the corresponding Tutte polynomial, whose points T (2, 1)
and T (1, 1) calculate the numbers of spanning forests and of spanning
trees, resp. Similar definition of spanning trees and forests was presented in [15], for that definition there is also Tutte polynomial for a
hypergraph, however, there is no matroid.
First we define the family of algebras.
Given a hypergraph H on n vertices, let us associate commuting
variables φe , e ∈ H to all edges of H.
Set ΦH be the algebra generated by {φe : e ∈ H} with relations
2
φe = 0, for any e ∈ H.
Define C = {ci,e ∈ K : i ∈ [n], e ∈ H} as a set of parameters of
H, for any edge e ∈ H, ci,e = 0 for vertices non-incident to e, and
P
n
i=1 ci,e = 0.

POSTNIKOV-SHAPIRO ALGEBRAS AND MATROIDS

For i = 1, . . . , n, set
Xi =

X

15

ci,e φe ,

e∈H

F
CH(C)

Denote by
the subalgebra of ΦH generated by X1 , . . . , Xn , and
F
b
denote by CH the family of such subalgebras.
The following trivial properties hold for this family of algebras.

Proposition 4.2.
P(I) For a hypergraph H, the dimension of the space
of parameters is e∈E (|e| − 1).
(II) Given a set of parameters C and non-zero numbers ae , e ∈ E,
let C ′ be the set of parameters such that c′i,e = ae ci,e for any i ∈ [n] and
e ∈ E. Then the subalgebras for C and for C ′ are isomorphic.
Corollary 4.2. For a usual graph G, almost all algebras from CbG are
isomorphic to CG .
We define a hypergraphical matroid using the definition of an independent set of edges of a hypergraph.

Definition 4.2. Let H be a hypergraph on n vertices. A set F of
edges is called independent if there is a set of parameters C of H, such
that vectors corresponding to edges from F are linearly independent. In
other words, F is independent if, for a generic set of parameters of H,
vectors are linearly independent. Define the hypergraphical matroid of
H as the matroid with the ground set E(H).
There is a combinatorial definition of an independent set of edges.
First we need to define a cycle of H.
Definition 4.3. A subset of edges C ⊂ E is called a cycle if
• |C| = | ∪e∈C e|
• There is no subset |C ′ ⊂ C|, such that the first property holds
for C ′ .
Definitions of dependence and of a cycle are similar.
Theorem 4.3. A subset of edges X ⊂ E is dependent if and only if
there is a cycle C ⊂ X.
We present a proof of this theorem after Theorem 4.6.
Definition 4.4. A set of edges F is called a spanning forest if F has
no cycles, in other words, F is forest if and only if F is an independent
set (by Theorem 4.3). A set of edges T ⊂ H is called a spanning tree
if it is a forest and T has exactly v(H) − 1 edges.
A hypergraph H is called strongly connected if it has at least one
spanning tree.
Proposition 4.4. Maximal spanning forests of a hypergraph have the
same number of edges. In fact, if H = (V, E) is a strongly connected

16

G. NENASHEV

hypergraph, then for any spanning forest F ⊂ E there is a spanning
tree T which contains F (i.e. F ⊂ T ⊂ E).
Proof. By Theorem 4.3 we know that a spanning forest is the same as
an independent set of edges. Then we can add edges to a forest until the
number of edges is less than the dimension of the linear space. Then all
maximal spanning forests have the same size. Hence, if a hypergraph
is strongly connected, then any spanning forest is contained in some
spanning tree.

F
The Hilbert series of algebras in CbH
are also counting forests of H.

F
Theorem 4.5. For a hypergraph H, generic algebras from CbH
have the
same Hilbert series. The dimension of the k-th graded component of a
generic algebra equals the number of spanning forests F in H with the
external activity e(H) − e(F ) − k.

Proof. By Theorem 4.3 we can change the definition of spanning forests
to independent sets. Consider a generic set of parameters C. By TheF
and it is the same for all
orem 4.1 we know the Hilbert series of CH(C)
generic sets of parameters.

We define the Tutte polynomial of H as the Tutte polynomial of
the corresponding hypergraphical matroid. By the theorems above we
know that
• TH (2, 1) is the number of spanning forests;
• TH (1, 1) is the number of maximal spanning forests. In fact,
TH (1, 1) is the number of spanning trees if H is srongly connected.
By Theorem 4.5, we get that a generic Hilbert series is a specialization of the Tutte polynomial of H.
Corollary 4.3. Given a hypergraph H and its generic set of parameters
F
C, the Hilbert series of the algebra CH(C)
is given by


1
HCH (C)F (t) = TG 1 + t,
· te(H)−rkH ,
t
where rkH is the size of a maximal spanning forest of H.
There is another definition of forests/trees of H, which again shows
that it is a generalization of forests/trees of a usual graph.
Theorem 4.6. A subset of edges X ⊂ E is a forest (tree) if and only
if there is map from edges to pairs: ek → (i, j), where vi , vj ∈ ek , such
that these pairs form a forest (tree) in the complete graph Kn .
Proof. Consider our forest F and the hypergraph H, add to them n −
1 − e(F ) full edges, i.e. edges of type V . We get a new hypergraph H ′
and a subset of edges F ′ . It is clear that F ′ is a tree, because there is

POSTNIKOV-SHAPIRO ALGEBRAS AND MATROIDS

17

no cycle without new edges, and with at least one new edge we need
to cover all vertices and their number is bigger than number of edges.
So let F ′ = T and we will prove our Theorem for a spanning tree.
Consider the bipartite graph B with two sets of vertices: the first
set are edges of T and the second are vertices V \ v1 , where there is an
edge between ei and vj if and only if vj ∈ ei .
There is a perfect matching in B, because we can use Hall’s marriage
theorem (see [12] or any classical book). We know that e(T ) = |V \
v1 | and, for any X ⊂ T , they cover at least e(X) vertices (otherwise
these edges cover these vertices and may be v1 and then X has cycle).
Consider a bijection f from T to V \ v1 constructed by this perfect
matching. Now we construct by recursion a map g from T to pairs of
vertices:
(1) A := {v1 } and B := T
(2) repeat until A 6= V :
• choose the minimal edge ei from B such that ei ∩ A 6= ∅
• g(ei ) = (u, f (ei )), where u ∈ ei ∩ A
• A := A ∪ {f (ei )} and B := B \ {ei }
It works, otherwise we can not chose such an edge ei , then either B = ∅
or B 6= ∅ at this moment. We know that |A| + |B| = n, then in the
first case we already have A = V ; in the second case edges from B have
vertices only from V \ A, then there is a cycle on these edges, i.e. T is
not a tree. Then this algorithm gives some usual tree.

Proof of Theorem 4.3. Assume the contrary, then there is a subset X ⊂
E, which is dependent and without cycles, i.e. X is a spanning forest.
By Theorem 4.6 we know that there is map g from X to the pairs of
vertices, which gives a usual forest. Consider the vector set
{ae := zg1 (e) − zg2 (e) , e ∈ X},
where zv = (0, . . . , 0, 1, 0, . . . , 0) is the unit vertex correspinding to the
vertex v. Since g gives the usual forest, these vectors are independent.
Hence, generic vectors {be , e ∈ X} are also linear independent. We
get that the edges are independent, contradiction.

By the induced subgraph on vertices V ′ ⊂ V , we assume a hypergraph (V ′ , E ′ ), where E ′ are all edges of E, which have vertices only
from V ′ (i.e. e ∈ E ′ if e ⊂ V ′ ). This definition works well with colorings of hypergraphs, because if we want to color a hypergraph such
a way that there are no monochromatic edges, then it is the same as
splitting vertices into sets with empty induced subgraphs. Also this
definition works well with standard sense of connectivity.
Proposition 4.7. Let V1 and V2 be the subsets of vertices such that the
induced subgraphs of H on Vj are strongly connected and V1 ∩ V2 6= ∅.
Then the induced subgraph of H on V1 ∪ V2 is also strongly connected

18

G. NENASHEV

Proof. For any vertex vi ∈ V we will consider the corresponding unit
vector zvi = (0, . . . , 0, 1, 0, . . . , 0). Fix a vertex u, which lie in the intersection V1 ∩ V2 . Let H1 and H2 be induced subgraphs on V1 and V2 ,
resp.
Consider vectors bi corresponding to ei ∈ E1 . We know that there is
a spanning tree of the graph H1 , then the dimension of the linear space
of such vectors is |V1 | − 1, furthermore any sum of coordinates of any
vector is zero. Hence, for any v ∈ V1 , zv − zu ∈ span{bi : ei ∈ E1 }.
Similarly we get the same for H2 and, hence, we have the same for
H1 ∪ H2 .
We get that for any v ∈ V1 ∪ V2 , zv − zu ∈ span{bi : ei ∈ E1 ∪ E2 }.
Hence, the hypergraph H1 ∪ H2 has |V1 ∪ V2 | − 1 independent edges,
then has a spanning tree. We have that the induced subgraph of H
on vertices V1 ∪ V2 is strongly connected, since it has all edges from
H1 ∪ H2 .


5. Algebras corresponding to spanning trees, Problems
In this section we discuss analogous algebras counting spanning trees.
T
Recall the definition of algebras BG
and CGT borrowed from [22].
Notation 5.1. Take an undirected graph G with n vertices.
(I) Let ΦTG be the commutative algebra over Q
K generated by {φe : e ∈
2
G} with relations φe = 0, for any e ∈ G, and e∈H φe = 0, for any cut
H ⊂ E(G).
Fix a linear order of vertices of G. For i = 1, . . . , n, set
X
Xi =
ci,e φe ,
e∈E(G)

where ci,e as in Notation 1.1. Denote by CGT the subalgebra of ΦTG generated by X1 , . . . , Xn .
(II) Consider the ideal JGT in the ring K[x1 , · · · , xn ] generated by
p[n] = x1 + . . . + xn
and by
pTI =

X
i∈I

xi

! DI

,

where I ranges over all nonempty proper subsets of vertices, and DI is
the total number of edges between vertices in I and vertices outside I.
T
Define the algebra BG
as the quotient K[x1 , . . . , xn ]/JGT .
The case of disconnected graphs is not interesting, because both
algebras are trivial. In the paper [22] the following result was proved:

POSTNIKOV-SHAPIRO ALGEBRAS AND MATROIDS

19

T
Theorem 5.1 (cf. [22]). For any connected graph G, algebras BG
and
T
CG are isomorphic; their total dimension over K is equal to the number
of spanning trees in G.
Moreover, the dimension of the k-th graded component of these algebras equals the number of spanning trees of G with external activity
e(G) − v(G) + 1 − k.

Corollary 5.1. Given a connected graph G, the Hilbert series of the
algebra CGT is given by


1
HCGT (t) = TG 1,
· te(G)−v(G)+c(G) ,
t

where c(G) is the number of connected components of G.

5.1. Algebras and matroids. For graph G, we define its bridge-free
matroid as the usual graphical matroid of the graph G′ which is obtained from G after removing all its bridges.
Proposition 5.2. For any pair of connected graphs G1 and G2 with
T
T
isomorphic bridge-free matroids, their algebras BG
and BG
are iso1
2
morphic.
Proof. Notice that, if we add an edge e and a vertex v to G, such that
v is an endpoint of e and another endpoint of e is some vertex of G,
then algebra BT does not change (this is obvious because e is a bridge,
and hence, φe is one of the generators of the ideal). This operation
doesn’t change bridge-free matroid. Therefore it is enough to prove
Proposition 5.2 only for graphs with the same number of edges.
Assume that |E(G1 )| = |E(G2 )|. In this case an isomorphism of
bridge-free matroids is equivalent to an isomorphism of matroids of
graphs G1 and G2 .
In fact, in Lemma 2.1 we construct orientations G1 and G2 of graphs
G1 and G2 on the same set of edges E(G1 ) = E(G2 ) (it was constructed
for graphs differ in one Whitney’s deformation, so we can extend it to
a sequence of deformations), such that they give the same graphical
matroid on edges and with these orientations the algebras CGF 1 and CGF 2
coincide as subalgebras of ΦFGi (ΦFG1 and ΦFG2 are the same, because
graphs have common set of edges).
Let I be the ideal generated by the products of edges from the cuts
of G1 in ΦFG1 . Because the variables on edges in G1 and G2 are the
same and C is a cut in G1 if and only if C is a cut in G2 , then I is also
the ideal generated by the cuts of G2 .
Thus we have ΦTG1 = ΦFG1 /I, hence,
CGT 1 = CGF 1 /I,
similarly
CGT 2 = CGF 2 /I.

20

G. NENASHEV

It means that the algebras CGT 1 and CGT 2 are also the same in orientations
G1 and G2 .

We formulate the following converse conjecture.
T
T
Conjecture 1. Algebras BG
and BG
for the connected graphs G1
1
2
and G2 are isomorphic if and only if their bridge-free matroids are
isomorphic.

5.2. t-labelled trees. It is possible to introduce similar algebras which
Tt
enumerate t-labelled trees, but it is not veryPexciting. Let BG
be an
DI
algebra in which we change the generators ( i∈I xi ) of the ideal by
P
( i∈I xi )tDI . The definition of CGTt will change in a more complicated
way.
However, there is no result about a reconstruction of the Tutte polynomial from the Hilbert series, because all trees have the same number
of edges and then HBTt (x) = (1 + x)n−1 HBGT (xt ). In other words, the
G

Tt
T
and of BG
contain the same information about the
Hilbert series of BG
graph.

5.3. Algebras for hypergraphs. The main problem is to construct
T
a family CbH
of algebras, which count spanning trees of H.
By paper [23], for a hypergraph H and a set of parameters C, we can
F
F
. We can consider the
as a quotient algebra, i.e, as BH(C)
present CH(C)
F
T
algebra BH(C) , which is obtained from BH(C) by changing the powers of
the generators of the ideal (writing always one less). By paper [2] algeT
bra BH(C)
should count spanning trees of H. However at this moment,
T
we can not present ΦTH such that its generic subalgebra CH(C)
counts
spanning trees of H.
Probably, we need to add to ΦFH relations corresponding to cuts,
where a cut is a subset of edges such that without it H has no spanning
trees. However, we need to prove it and if we want to do something
similar to the proof of Theorem 5.1, then we need to define H-parking
functions for a hypergraph.
References
[1] A. Abdesselam, The Grassmann-Berezin calculus and theorems of the matrixtree type, Advances in Applied Mathematics 33(1) (2004), pp. 51-70.
[2] F. Ardila, A. Postnikov, Combinatorics and geometry of power ideals, Trans.
Amer. Math. Soc., 362(8) (2010), pp. 4357-4384.
[3] C. Berge, Hypergraphs, North-Holland Mathematical Library 45, 1989.
[4] A. Berget, Products of linear forms and Tutte polynomials, European J. Combin.
31 no. 7 (2010), pp. 1924-1935.
[5] T. Brylawski, J. Oxley, The Tutte polynomial and its applications, chapter in
Matroid Applications, Encyclopedia of Mathematics and its Applications 40
(1992).

POSTNIKOV-SHAPIRO ALGEBRAS AND MATROIDS

21

[6] Y. Burman, A. Ploskonosov, A. Trofimova, Matrix-tree theorems and discrete
path integration, Linear Algebra and its Applications, 466 (2014), pp. 64-82.
[7] A. Brandstadt, F. Dragan, V. Chepoi, V. Voloshin, Dually chordal graphs, SIAM
Journal on Discrete Mathematics 11(3) (1998), pp. 437-455.
[8] S. Chaiken, D. J. Kleitman, Matrix Tree Theorems, Journal of Combinatorial
Theory, Series A 24 (1978), pp. 377-381.
[9] D. Chebikin, P. Pylyavskyy, A family of bijections between G-parking functions
and spanning trees, Journal of Combinatorial Theory, Series A 110 (2005), pp.
31-41.
[10] D. Dhar, Self-organised critical state of the sandpile automaton models, Physical Review Letters 64 no. 14 (1990), 1613-1616.
[11] S. Fomin, A. N. Kirillov, Quadratic algebras, Dunkl elements, and Schubert calculus, Advances in geometry, volume 172 of Progr. Math. (1999), pp. 147-182.
[12] P. Hall, On Representatives of Subsets, J.London Math. Soc. 10(1) (1935), pp.
26-30.
[13] O. Holtz, A. Ron, Zonotopal algebra, Advances in Mathematics, 227 (2011), pp.
847-894.
[14] B. Huang, Monomization of Power Ideals and Generalized Parking Functions,
https://math.mit.edu/research/highschool/primes/materials/2014/Huang.pdf.
[15] T. Kálmán, A version of Tutte’s polynomial for hypergraphs, Advances in Mathematics 244 (2013), pp. 823-873.
[16] G. Kirchhoff, Uber die Auflösung der Gleichungen, auf welche man bei der
untersuchung der linearen verteilung galvanischer Ströme geführt wird, Ann.
Phys. Chem. 72 (1847), pp. 497-508.
[17] M. Lenz, Hierarchical Zonotopal Power Ideals, European Journal of Combinatorics 33 (2012), pp. 1120-1141.
[18] R. I. Liu, On the commutative quotient of Fomin-Kirillov algebras, European
Journal of Combinatorics Volume 54 (2016), pp. 65-75.
[19] G. Nenashev, B. Shapiro, "K-theoretic" analog of Postnikov-Shapiro algebra
distinguishes graphs, Journal of Combinatorial Theory, Series A, 148 (2017),
pp. 316-332.
[20] P. Orlik, H. Terao, Commutative algebras for arrangements, Nagoya Math. J.
134 (1994), pp. 65-73.
[21] J. G. Oxley, Matroid theory, Oxford University Press, New York (1992).
[22] A. Postnikov, B. Shapiro, Trees, parking functions, syzygies, and deformations
of monomial ideals, Trans. Amer. Math. Soc. 356 (2004), pp. 3109-3142.
[23] A. Postnikov, B. Shapiro, M. Shapiro, Algebra of curvature forms on homogeneous manifolds, AMS Trans. Ser 2, vol. 194 (1999), pp. 227-235.
[24] B. Shapiro, M. Shapiro, On ring generated by Chern 2-forms on SLn /B, C. R.
Acad. Sci. Paris Sér. I Math. 326(1) (1998), pp. 75-80.
[25] A. Sokal, The multivariate Tutte polynomial (alias Potts model) for graphs and
matroids, In Surveys in Combinatorics (2005), pp. 173-226.
[26] W. T. Tutte, Graph Theory, Cambridge University Press (2001).
[27] H. Whitney, 2-isomorphic graphs, American Journal of Mathematics 55 (1933),
pp. 245-254.
Department of Mathematics, Stockholm University, SE-106 91 Stockholm, Sweden,
E-mail address: nenashev@math.su.se

