Parabolic 3-term relations algebras and partial flag varieties

In fact one can construct an analogue of the algebra 3HTnand a commutative subalgebra inside it, for any graph Γ = (V, E) on n vertices, possibly with loops and multiple edges [72]. We denote this algebra by 3T_n(Γ), and denote by 3Tn⁽⁰⁾(Γ) itsnil-quotient, which may be considered as a “classical limit of the algebra 3Tn(Γ)”.

The case of the complete graph Γ =Knreproduces the results of the present paper and those of [72], i.e., the case of the full flag variety Fl_n. The case of the complete multipartite graph Γ = K_n1,...,nr reproduces the analogue of results stated in the present paper for the full flag varietyFln, to the case of the partial flagvariety F_n1,...,nr, see [72] for details.

Weexpect that in the case of the complete graph with all edges having the same multiplic-ity m, denoted by either Γ =Kn^(m), ormK_n in the present paper, the commutative subalgebra generated by the Dunkl elements in the algebra 3Tn⁽⁰⁾(Γ) is related to the algebra of coinvariants of the diagonal action of the symmetric group Snon the ring of polynomialsQ

Xn⁽¹⁾, . . . , Xn^(m)

, where we set Xn⁽ⁱ⁾ =

x⁽ⁱ⁾₁ , . . . , x⁽ⁱ⁾n .

Example 4.9. Take Γ = K2,2. The algebra 3T⁽⁰⁾(Γ) is generated by four elements {a =u13, b=u₁₄, c=u₂₃, d=u₂₄} subject to the following set of (defining) relations

• a²=b²=c²=d² = 0,cb=bc,ad=da,

• aba+bab= 0 =aca+cac,bdb+dbd= 0 =cdc+dcd, abd−bdc−cab+dca= 0 =acd−bac−cdb+dba,

• abca+adbc+badb+bcad+cadc+dbcd= 0.

It is not difficult to see that³¹ Hilb 3T⁽⁰⁾(K_2,2), t

= [3]²_t[4]²_t, Hilb 3T⁽⁰⁾(K_2,2)^ab, t

= (1,4,6,3).

Here for any algebra A we denote byA^ab its abelianization³².

The commutative subalgebra in 3T⁽⁰⁾(K2,2), which corresponds to the intersection 3T⁽⁰⁾(K2,2)

∩Z[θ₁, θ₂, θ₃, θ₄], is generated by the elementsc₁ :=θ₁+θ₂ = (a+b+c+d) andc₂ :=θ₁θ₂ = (ac+ca+bd+db+ad+bc). The elementsc1andc2commute and satisfy the following relations

c³₁−2c₁c₂= 0, c²₂−c²₁c₂ = 0.

The ring of polynomials Z[c1, c2] is isomorphic to the cohomology ring H^∗(Gr(2,4),Z) of the Grassmannian variety Gr(2,4).

To continue exposition, let us take m ≤ n, and consider the complete multipartite graph Kn,m which corresponds to the Grassmannian variety Gr(n, m+n). One can show

Hilb 3T_n+m⁽⁰⁾ (Kn,m)^ab, t

=

n−1

X

k=0

(−1)^k(1 + (n−k)t)^m−1

n−k

Y

j=1

(1 +jt) n

n−k

=t^n+m−1Tutte Kn,m,1 +t⁻¹,0 , where _n

k := S(n, k) denotes the Stirling numbers of the second kind, that is the number of ways to partition a set of n labeled objects into k nonempty unlabeled subsets, and for any graph Γ, Tutte(Γ, x, y) denotes theTutte polynomial³³ corresponding to graph Γ.

It is well-known that the Stirling numbersS(n, k) satisfy the following identities

n−1

X

k=0

(−1)^k S(n, n−k)

n−k

Y

j=1

(1 +jt) = (1 +t)ⁿ, X

n≥k

n k

xⁿ

n! = (e^x−1)^k k! . Let us observe that

dim 3T⁽⁰⁾(K_n,n)^ab

=

n−1

X

k=0

(−1)^k(n+ 1−k)ⁿ⁻¹(n+ 1−k)!

n n−k

=

n+1

X

k=1

((k−1)!)²

n+ 1 k

2

, see, e.g., [131,A048163].

Moreover, ifm≥0, then X

n≥1

dim 3T⁽⁰⁾(Kn,n+m)^ab

tⁿ=X

k≥1

k^k+m−1(k−1)!t^k

k−1

Q

j=1

(1 +kjt) ,

X

n≥1

Hilb 3T⁽⁰⁾(Kn,m)^ab, t

zⁿ⁻¹ =X

k≥0

(1 +kt)^m−1

k

Y

j=1

z(1 +jt) 1 +jz .

31Hereinafter we shell use notation (a0, a1, . . . , ak)t:=a0+a1t+· · ·+akt^k.

32Seehttp://groupprops.subwiki.org/wiki/Abelianization.

33See, e.g.,https://en.wikipedia.org/wiki/Tutte_polynomial. It is well-known that Tutte(Γ,1 +t,0) = (−1)^|Γ|t^−κ(Γ)Chrom(Γ,−t),

where for any graph Γ, |Γ| is equal to the number of vertices and κ(Γ) is equal to the number of connected components of Γ. Finally Chrom(Γ, t) denotes thechromatic polynomialcorresponding to graph Γ, see, e.g., [140], orhttps://en.wikipedia.org/wiki/Chromatic_polynomial.

Comments 4.10(poly-Bernoulli numbers). Based on listed above identities involving the Stir-ling numbers S(n, k), one can prove the followingcombinatorial formula

dim 3T⁽⁰⁾(K_n,m)^ab

=

min(n,m)

X

j=0

(j!)²

n+ 1 j+ 1

m+ 1 j+ 1

=B_n^(−m)=B_m⁽⁻ⁿ⁾, (4.1)

where Bn^(k) denotes thepoly-Bernoulli numberintroduced by M. Kaneko [64].

On the other hand, it is well-known, see, e.g., footnote 33, that for any graph Γ the spe-cialization Tutte(Γ; 2,0) of the Tutte polynomial associated with graph Γ, counts the number of acyclic orientations of Γ. Therefore, the poly-Bernulli number Bn^(−m) counts the number of acyclic orientatations of the complete bipartite graphKn,m.

For example, dim 3T⁽⁰⁾(K_3,3)^ab

= 230 = 1 + 7²+ (2!)²6²+ (3!)², cf. Example4.16(3).

For the reader’s convenient, we recall below a definition ofpoly-Bernoulli numbers. To start with, let kbe an integer, consider the formal power series

Lik(z) :=

∞

X

n=1

zⁿ n^k.

Ifk≥1, Li_k(z) is thek-thpolylogarithm, and ifk≤0, then Li_k(z) is a rational function. Clearly Li1(z) =−ln(1−z). Now definepoly-Bernoulli numbers through the generating function

Li_k(1−e^−z) 1−e^−z =

∞

X

n=0

B^(k)_n zⁿ n!.

Note that a combinatorial formula for the numbersBn^(−k) stated in (4.1) is a consequence of the following identity [64]

∞

X

n=0

∞

X

k=0

B^(−k)_n xⁿ n!

z^k

k! = e^x+z

1−(1−e^x)(1−e^z).

Note that the poly-Bernoulli numbersBn^(−m)(=Bm⁽⁻ⁿ⁾) have the following combinatorial inter-pretation³⁴, namely, the numberBn^(−m), and therefore the dimension of the algebra 3T⁽⁰⁾(Kn,m) is equal to

B^(−m)_n =T(n−1, m) +T(n, m−1), where [26]

T(n, m) :=

min(n,m)

X

j=0

j!(j+ 1)!

n+ 1 j+ 1

m+ 1 j+ 1

is equal to the number of permutationsw∈Sn+m having the excedance set{1,2, . . . , m}.

Exercise 4.11. Show that polynomial Hilb(3T⁽⁰⁾(K_n,m), t) has degreen+m−1, and Coeff_t^n+m−1 Hilb 3T⁽⁰⁾(Kn,m), t

=T(n−1, m−1).

Problem 4.12. To find a bijective proof of the identity (4.1).

34See for example, [131, A136126], [131, A099594] or [26, Theorem 3.1], and the literature quoted therein.

Recall, that theexcedance setof a permutationπ∈Snis the set of indicesi, 1≤i≤n, such thatπ(i)> i.

Final remark, the explicit expression for the chromatic polynomial of the complete tripartite graph K_n,n,n can be found in [131,A212220].

Now letθ_i^(n+m)= P

j6=i

u_ij, 1≤i≤n+m, be the Dunkl elements in the algebra 3T⁽⁰⁾(K_n+m), define the following elements the in the algebra 3T⁽⁰⁾(Kn,m)

c_k:=e_k θ^(n+m)₁ , . . . , θ^(n+m)_n

, 1≤k≤n, cr :=er θ_n+1^(n+m), . . . , θ^(n+m)_n+m

, 1≤r ≤m.

Clearly, 1 +

n

X

k=1

ckt^k

! 1 +

m

X

r=1

crt^r

!

=

n+m

Y

j=1

1 +θ^(n+m)_j

= 1.

Moreover, there exist the natural isomorphisms of algebras H^∗(Gr(n, n+m),Z)∼=Z[c1, . . . , cn]

* 1 +

n

X

k=1

ckt^k

! 1 +

m

X

r=1

crt^r

!

−1 +

, QH^∗(Gr(n, n+m))∼=Z[q][c₁, . . . , c_n]

* 1 +

n

X

k=1

c_kt^k

! 1 +

m

X

r=1

c_rt^r

!

−1−qt^n+m +

. Let us recall, see Section 2, footnote 26, that for a commutative ring R and a polynomial p(t) =

s

P

j=1

g_jt^j ∈R[t], we denote by hp(t)i the ideal in the ringR generated by the coefficients g1, . . . , gs.

These examples are illustrative of the similar results valid for thegeneral complete multipartite graphs K_n1,...,nr, i.e., for the partial flag varieties [72].

To state our results forpartial flag varietieswe need a bit of notation. LetN :=n₁+· · ·+n_r, nj >0,∀j, be a composition of sizeN. We setNj :=n1+· · ·+n_j,j= 1, . . . , r, andN0 = 0. Now, consider the commutative subalgebra in the algebra 3T_N⁽⁰⁾(KN) generated by the set of Dunkl elements

θ₁^(N), . . . , θ^(N)_N , and define elements c^(j,N)_k

j ∈ 3T_N⁽⁰⁾(Kn1,...,nr) to be the degree kj

elementary symmetric polynomials of the Dunkl elements θ_N^(N)_j−1+1, . . . , θ_N^(N)

j , namely, c^(j)_k :=c^(j,N)_k

j =e_k θ_N^(N)

j−1+1, . . . , θ_N^(N)

j

, 1≤k_j ≤n_j, j = 1, . . . , r, c^(j)₀ = 1, ∀j.

Clearly

r

Y

j=1 nj

X

a=0

c^(j)_a t^a

!

=

N

Y

j=1

1 +θ_j^(N)t^j

= 1.

Theorem 4.13. The commutative subalgebra generated by the elements {c^(j)_k

j,1≤kj ≤nj,1≤ j≤r−1}, in the algebra3T_N⁽⁰⁾(Kn1,...,nr) is isomorphic to the cohomology ringH^∗(Fln1,...,nr,Z) of the partial flag variety Fl_n1,...,nr.

In other words, we treat the Dunkl elements θ_N^(N)

j−1+a,1 ≤ a ≤ n_j , j = 1, . . . , r, as the Chern roots of the vector bundles {ξ_j := F_j/Fj−1}, j = 1, . . . , r, over the partial flag variety Fln1,...,nr.

Recall that a pointF of the partial flag variety Fln1,...,nr,n1+· · ·+nr =N, is a sequence of embedded subspaces

F =

0 =F₀ ⊂F₁ ⊂F₂⊂ · · · ⊂F_r =C^N such that

dim(F_i/Fi−1) =n_i, i= 1, . . . , r.

By definition, the fiber of the vector bundleξ_i over a point F ∈ Fl_n1,...,nr is then_i-dimensional vector space Fi/Fi−1.

To conclude, let us describe the set of (defining) relations among the elements

c^(j)a , 1 ≤ a≤nj, 1≤j ≤r−1. To proceed, let us introduce the set of variables

x^(j)a |1 ≤a≤nj,1≤ j ≤ r−1 , and define polynomials b₀ = 1, b_k := b_k

x^(j)_a , k ≥ 1 by the use of generating function

1

r−1

Q

j=1 nj

Q

a=1

1 +x^(j)a

t^a

=X

k≥0

b_kt^k.

Now let us introduce matrix Mm

x^(j)a := (mij), where

mij :=







bi+j−1 if j > i,

1 if j=i−1, i≥2, 0 ifj < i−1.

Claim 4.14. detM_m

c⁽ⁱ⁾a = 0, Nr−1 < m≤N. Moreover, H^∗(Fl_n1,...,nr,Z)∼=Z[{x^j_a}]/hM_Nr−1+1, . . . , M_Ni.

A meaning of the algebra 3Tn⁽⁰⁾(Γ) and the corresponding commutative subalgebra inside it for a general graph Γ is still unclear.

Conjecture 4.15. ³⁵

(1) Let Γ = (V, E) be a connected subgraph of the complete graph Kn on nvertices. Then Hilb 3T_n⁽⁰⁾(Γ)^ab, t

=t^|V|−1Tutte Γ; 1 +t⁻¹,0 .

(2) Let Γ = (V, E,{m_ij,(ij) ∈E}) be a connected subgraph of the complete graph Kn^(m) with multiple edges such that an edge (ij) ∈Kn has the multiplicity mij. Let 3Tn⁽⁰⁾(Γ,m) de-notes the subalgebra in the algebra3Tn⁽⁰⁾(m) generated by elements{u^(α_ij^(ij)),(ij)∈E,1≤ α_(ij)≤mij}, see Section2.2. LetA(Γ,{m_ij}) denotes the graphic arrangement correspon-ding to the graph (Γ,{m_ij}), that is the set of hyperplanes {H_(ij),a = (x_i−x_j = a),0 ≤ a≤m_ij −1,(ij)∈E}. Then

3T_n⁽⁰⁾(Γ,m)^ab = OS⁺(A(Γ,{m_ij})),

where for any arrangements of hyperplanes A, OS⁺(A) denotes the even Orlik–Solomon algebra of the arrangement A [113]. In the case when m_ij = 1, ∀1 ≤ i < j ≤ n, 3Tn⁽⁰⁾(Γ)^anti= OS(A(Γ)).

35Part (1) of this conjecture has been proved in [89]. In [89] the author has used notation OT(Γ) for the Orlik–

Terao algebra associated with (simple) graph Γ. In our paper we prefer to denote the corresponding Orlik–Terao algebra by OS⁺(Γ).

Examples 4.16.

(1) LetG=K2,2 be complete bipartite graph of type (2,2). Then Hilb 3T₄⁰(2,2)^ab, t

= (1,4,6,3) =t²(1 +t) +t(1 +t)²+ (1 +t)³, and the Tutte polynomial for the graphK_2,2 is equal tox+x²+x³+y.

(2) LetG=K_3,2 be complete bipartite graph of type (3,2). Then Hilb 3T₅⁰(3,2)^ab, t

= (1,6,15,17,7)

=t³(1 +t) + 3t² (1 +t)²+ 2t(1 +t)³+ (1 +t)⁴, and the Tutte polynomial for the graphK_3,2 is equal to

x+ 3x²+ 2x³+x⁴+y+ 3xy+y².

(3) LetG=K_3,3 be complete bipartite graph of type (3,3). Then Hilb 3T₆⁰(3,3)^ab, t

= (1,9,36,75,78,31) = (1 +t)⁵+ 4t(1 +t)⁴ + 10t²(1 +t)³+ 11t³(1 +t)²+ 5t⁴(1 +t), and the Tutte polynomial of the bipartite graphK3,3 is equal to

5x+ 11x²+ 10x³+ 4x⁴+x⁵+ 15xy+ 9x²y+ 6xy²+ 5y+ 9y²+ 5y³+y⁴. (4) Consider complete multipartite graphK2,2,2. One can show that

Hilb 3T₆⁽⁰⁾(K_2,2,2)^ab, t

= (1,12,58,137,154,64) = 11t⁴(1 +t) + 25t³(1 +t)² + 20t²(1 +t)³+ 7t(1 +t)⁴+ (1 +t)⁵,

and

Tutte(K_2,2,2, x, y) =x(11,25,20,7,1)_x+y(11,46,39,8)_x+y²(32,52,12)_x +y³(40,24)x+y⁴(29,6)x+ 15y⁵+ 5y⁶+y⁷.

The above examples show that the Hilbert polynomial Hilb(3T_n⁰(G)^ab, t) appears to be a cer-tain specialization of the Tutte polynomial of the corresponding graph G.

Instead of using the Hilbert polynomial of the algebra 3T_n⁰(G)^ab one can consider the graded Betti numbers (over a field k) polynomial Betti_k(3T_n⁰(G)^ab, x, y). For example,

Betti_Q 3T₃⁰(K₃)^ab, x, y

= 1 +xy(4,2)_x+x²y²(3,2)_x, Betti_Q 3T₄⁰(K_2,2)^ab, x, y

= 1 + 4xy+xy²(1,9,3)_x+x²y³(1,6,3)_x, Betti_Q 3T₅⁰(K_3,2)^ab, x, y

= 1 + 6xy+xy²(3,25,9) +x²y³(6,45,34,7) +x³y⁴(3,25,25,7), Betti_Q 3T₄⁰(K4)^ab, x, y

= 1 +xy(10,10) +x²y²(25,46,26,6) +x³y³(15,36,25,6), Betti_Z/2Z 3T₄⁰(K4)^ab, x, y

= 1 +xy(10,10,1)x+x²y²(25,46,26,6) +x³y³(16,36,25,6), Betti_Q 3T₅⁰(K₅)^ab, x, y

= 1 +xy(20,30) +x²y²(109,342,315,72) +x³y³(195,852,1470, 1232,639,190,24) +x⁴y⁴(105,540,1155,1160,639,190,24), Betti_Q 3T₅⁰(K5)^ab,1,1

= 9304, Betti_Z/3Z 3T₅⁰(K5)^ab, x, y

= 1 +xy(20,30) +x²y²(109,342,315,72,1)

+x³y³(195,852,1471,1232,640,190,24) +x⁴y⁴(105,540,1156,1160,639,190,24), Betti_Z/3Z 3T₅⁰(K5)^ab,1,1

= 9308, Betti_Z/2Z 3T₅⁰(K5)^ab, x, y

= 1 +xy(20,30,5) +x²y²(114,342,340,131,10) +x³y³(220,911,1500,1291,649,190,24) +x⁴y⁴(125,599,1165,1160,639,190,24), Betti_Z/2Z 3T₅⁰(K₅)^ab,1,1

= 9680, Betti_Z/2Z 3T₆⁰(K3,3)^ab, x, y

= 1 + 9xy+xy²(9,69,27) +x²y³(40,285,257,52) +x³y⁴(59,526,866,563,201,31)

+x⁴y⁵(28,311,636,520,201,31), Betti_Z/2Z 3T₆⁰(K_3,3)^ab,1,1

= 4740, Betti_Q 3T₆⁰(K_3,3)^ab, x, y

= 1 + 9xy+xy²(9,69,27) +x²y³(40,285,257,43) +x³y⁴(59,526,866,563,201,31)

+x⁴y⁵(28,302,636,520,201,31), Betti_Q 3T₆⁰(K3,3)^ab,1,1

= 4704.

Let us observe that in all examples displayed above, the Betti polynomials are divisible by 1+xy.

It should be emphasize that in the literatute one can find definitions of big variety of (graded) Betti’s numbers associated with a given simple graph Γ, depending on choosing an algebra/ideal has been attached to graph Γ. For example, to define Betti’s numbers, one can start withedge graph ideal/algebraassociated with a graph in question, theStanley–Reisnerideal/ring and so on and so far. We refer the reader to carefully written book by E. Miller and B. Sturmfels [105] for definitions and results concerning combinatorial commutative algebra graded Betti’s numbers.

As far as I’m aware, the graded Betti numbers we are looking for in the present paper, are different from those treated in [105], and more close to those studied in [11].

It is not difficult to see (A.K.) that for a simple connected graph Γ the coefficient just before the (unique!) monomial of the maximal degree in Bettik 3T⁰(Γ)^ab, x, y

is equal to Tutte(Γ; 1,0).

It is known [10] that the number Tutte(Γ; 1,0) counts that of acyclic orientations of the edges of Γ with a unique source at a vertex v ∈ Γ, or equivalently [10], the number of maximum Γ-parking functions relative to vertex v.

Claim 4.17. Let G= (V, E) be a connected graph without loops. Then over any field k Bettik 3T_n⁰(G)^ab,−x, x

= (1−x)^eHilb 3T_n⁰(G)^ab, x ,

where n=|V(G)|=number of vertices, e=|E(G)|=number of edges.

Question 4.18.

• Let Gbe a connected subgraph of the complete graphK_n. Does the graded Betti polynomial Betti_Q(3T_n⁰(G)^ab, x, y) is a certain specialization of the Tutte polynomial T(G, x, y)? If not, give example of two (simple) graphs such that their Orlik–Terao algebras have the same Tutte polynomial, but different Betti polynomials over Q, and vice versa.

• It is clear that for any graph Γ (or matroid) one has Tutte(Γ, x, y) = a(Γ)(x+y) + (higher degree terms) for some integer a(Γ) ∈ N. Does the number a(Γ) have a simple combinatorial interpretation?

Proposition 4.19. Let n= (n1, . . . , nr) be a composition of n∈Z≥1, then

Hilb 3T⁽⁰⁾(Kn1,...,nr)^ab, t

= X

k=(k1,...,kr) 0<kj≤nj

(−t)^|n|−|k|

r

Y

j=1

nj

k_j ^|k|−1

Y

j=1

(1 +jt),

where we set |k|:=k₁+· · ·+k_r.

Remark 4.20. This proposition is a consequence of Conjecture4.15(1), which has been proved in [89].

Corollary 4.21. One has (a) 1 +t(t−1) X

(n1,...,nr)∈Z^r≥0\0^r

Hilb 3T⁽⁰⁾(Kn1,...,nr

ab

, t)xⁿ₁¹

n1!· · ·xⁿ_r^r nr!

=



1 +t

r

X

j=1

(e^−xj −1)





1−t

,

(b) X

(n1,n2,...,nr)∈Z≥0\0^r

dim 3T⁽⁰⁾(K_n1,...,nr)^abxⁿ¹

n1!· · ·x^nr

nr! =−log



1−r+

r

X

j=1

e^−xj



, (c) Hilb 3T⁽⁰⁾(K_n1,...,nr)^ab, t

= (−t)^|n|Chrom K_n1,...,nr,−t⁻¹ , (d) dim 3T⁽⁰⁾(Γ)^ab

is equal to the number of acyclic orientations of Γ, where Γ stands for a simple graph.

Recall that for any graph Γ we denote by Chrom(Γ, x) the chromatic polynomial of that graph.

Indeed, one can show³⁶

Proposition 4.22. If r ∈Z≥1, then Chrom(Kn1,...,nr, t) = X

k=(k1,...,kr) r

Y

j=1

nj

kj

(t)|k|,

where by definition (t)m:=

m−1

Q

j=1

(t−j), (t)0 = 1, (t)m= 0 if m <0.

Finally we describe explicitly the exponential generating function for theTutte polynomials of the weighted complete multipartite graphs. We refer the reader to [98] for a definition and a list of basic properties of the Tutte polynomial of a graph.

36Ifr= 1, the complete unipartite graphK(n) consists ofndistinct points, and

Chrom(K(n), x) =xⁿ=

n−1

X

k=0

(n k )

(x)k.

Let us stress that to abuse of notation the complete unipartite graphK(n) consists ofndisjoint points with the Tutte polynomial equals to 1 for alln≥1, whereas the complete graphKnis equal to the complete multipartite graphK(1ⁿ).

Definition 4.23. Let r ≥ 2 be a positive integer and {S₁, . . . , Sr} be a collection of sets of cardinalities #|S_j| = n_j, j = 1, . . . , r. Let ` := {`_ij}_1≤i<j≤n be a collection of non-negative integers.

The`-weighted complete multipartite graphKn<sup>(`)</sup>1,...,nr is a graph with the set of vertices equals to the disjoint union

`r j=1

S_i of the sets S₁, . . . , S_r, and the set of edges {(α_i, β_j), α_i ∈ S_i, β_j ∈ S_j}1≤i<j≤r of multiplicity `_ij each edge (α_i, β_j).

Theorem 4.24. Let us fix an integer r ≥ 2 and a collection of non-negative integers ` :=

{`_ij}_1≤i<j≤r. Then

1 + X

n=(n1,...,nr)∈Zr

≥0 n6=0

(x−1)^{κ(`,n)</sup>Tutte K<sub>n</sub><sup>(`)}_1,...,nr, x, ytⁿ₁¹ n1!· · ·tⁿ_r^r

nr!

=





X

m=(m1,...,mr)∈Z^r≥0

y

P

1≤i<j≤r

`ijmimj

(y−1)^−|m|t^m₁¹

m₁!· · ·t^m_r^r m_r!





(x−1)(y−1)

,

where κ(`,n) denotes the number of connected components of the graph Kn<sup>(`)</sup>1,...,nr. Comments 4.25.

(a) Clearly the condition `ij = 0 means that there are no edges between vertices from the sets S_i and S_j. Therefore Theorem 4.24 allows to compute the Tutte polynomial of any (finite) graph. For example,

Tutte K_2,2,2,2⁽¹⁶⁾ , x, y

=

(0,362,927,911,451,121,17,1)x,

(362,2154,2928,1584,374,32)_x,(1589,4731,3744,1072,96)_x, (3376,6096,2928,448,16)x,(4828,5736,1764,152)x,

(5404,4464,900,32)x,(5140,3040,380)x,(4340,1840,124)x, (3325,984,24)_x,(2331,448)_x,(1492,168)_x,(868,48)_x,(454,8)_x, 210,84,28,7,1 _y.

(b) One can show that a formula for the chromatic polynomials from Proposition 4.19 cor-responds to the specialization y = 0 (but not direct substitution!) of the formula for generating function for the Tutte polynomials stated in Theorem 4.24.

(c) The Tutte polynomial Tutte Kn^(`)1,...,nr, x, y

does not symmetric with respect to parameters {`<sub>ij</sub>}1≤i<j≤r. For example, let us write `= (`<sub>12</sub>, `₂₃, `<sub>13</sub>, `₁₄, `<sub>24</sub>, `₃₄), then

Tutte K(6,3,4,5,2,4) 2,2,2,2 ,1,1

= 2⁸·3·5·11³·241 = 1231760640.

On the other hand, Tutte K(6,4,3,5,2,4)

2,2,2,2 ,1,1

= 2¹³·3·7·11²·61 = 1269768192.

ドキュメント内 Contents OnSomeQuadraticAlgebrasI :CombinatoricsofDunklandGaudinElements,Schubert,Grothendieck,Fuss–Catalan,UniversalTutteandReducedPolynomials (ページ 54-62)