Galois groups of multivariate Tutte polynomials

DOI 10.1007/s10801-011-0332-2

Galois groups of multivariate Tutte polynomials

Adam Bohn·Peter J. Cameron·Peter Müller

Received: 13 March 2011 / Accepted: 13 November 2011 / Published online: 30 November 2011

© Springer Science+Business Media, LLC 2011

Abstract The multivariate Tutte polynomialZˆM of a matroidMis a generalization of the standard two-variable version, obtained by assigning a separate variable v_e to each elementeof the ground setE. It encodes the full structure ofM. Let v= {v_e}e∈E, letKbe an arbitrary field, and supposeMis connected. We show thatZˆ_M is irreducible overK(v), and give three self-contained proofs that the Galois group of ZˆM over K(v)is the symmetric group of degree n, wherenis the rank ofM.

An immediate consequence of this result is that the Galois group of the multivariate Tutte polynomial of any matroid is a direct product of symmetric groups. Finally, we conjecture a similar result for the standard Tutte polynomial of a connected matroid.

Keywords Tutte polynomial·Multivariate Tutte polynomial·Matroids·Graphs· Galois theory

LetMbe a finite matroid on the setE. The rank ofMis denoted byr(M), andr_M is the rank function onM. With this notation we haver(M)=rM(E). To avoid degen- erate examples and exceptions, a connected matroid will be assumed throughout to have positive rank (our results are trivial for a matroid having zero rank). Following the usual notation in matroid theory, we will writeE\einstead ofE\ {e}fore∈E, and denote byM|Athe restriction ofMto someA⊂E.

A. Bohn (

School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, UK

e-mail:[email protected] P. Müller

Institut für Mathematik, Universität Würzburg, Campus Hubland Nord, 97074 Würzburg, Germany

For eache∈Eletv_ebe a variable, and let v be the collection of these variables.

IfAis a subset ofE, we will denote by vA the set{v_e}e∈A. In [7], Sokal defines the following multivariate version of the Tutte polynomial of a matroidM.¹

For another variableq set

Z˜M(q,v)=

A⊆E

q^−rM(A)

e∈A

ve.

ThenZ˜_M(q,v)is a polynomial in¹_q with coefficients inZ[v].

For our purpose it is more convenient to use the following minor modification:

ZˆM(q,v)=

A⊆E

q^r(M)−rM(A)

e∈A

ve.

Then

ZˆM(q,v)=q^r(M)Z˜M(q,v),

andZˆ_M(q,v)is a polynomial of degreer(M)inq, which is monic ifM contains no loops. In particular, ifMis connected thenZˆ_M(q,v)is monic. Combinatorially, Zˆ_M(q,v)is a generating function for the content and rank of the subsets ofE, and thus encodes all of the information aboutM.

By making the substitutions

q←(x−1)(y−1), v_e←y−1

for eache∈E, and multiplying by a prefactor(y−1)^−r(M), we obtain the standard bivariate Tutte polynomial:

T_M(x, y)=

A⊆E

(x−1)^r(M)−rM(A)(y−1)^|A|−rM(A).

ThusT_Mis essentially equivalent to a special case ofZˆ_M in which the same vari- able is assigned to every element ofE.

Theorem 1 LetMbe a finite connected matroid with positive rankn=r(M), and letZˆ_M(q,v)be as defined above. LetKbe an arbitrary field. Then the Galois group ofZˆ_M(q,v)overK(v)is the symmetric group on thenroots ofZˆ_M(q,v).

Fore∈E, letM\ebe the deletion ofe, andM/ethe contraction ofe. Note that M\eandM/eare matroids on the setE\e. The essential tool for our first proof is a theorem of Tutte (see [6, Theorem 4.3.1]), which says that connectivity ofMimplies that at least one of the matroidsM\eorM/eis connected. SinceMis connected,e

1The multivariate Tutte polynomial for matroids has in fact been discovered a number of times; it appears, for example, in [2] as the “Tugger polynomial”.

is not a coloop, sor(M\e)=r_M(E\e)=r_M(E)=r(M). By [6, Proposition 3.1.6], we have thatr(M/e)=r_M(E)−r_M(e). Nowr_M(e)=1, sinceeis not a loop. So r(M/e)=r(M)−1.

The proofs will be based on some lemmas.

Lemma 2 LetMbe a finite connected matroid ande∈E. Then Zˆ_M= ˆZ_M\e+v_eZˆ_M/e.

Proof SinceMis connected,eis neither a loop nor a coloop. By [7, (4.18a)],Z˜M= Z˜_M\e+^v_q^eZ˜_M/e, hence

ZˆM=q^{r(M)−r(M\e)}ZˆM\e+q^{r(M)−r(M/e)}v_e qZˆM/e.

The claim then follows from the previous determination of the ranks ofE\eand

E/e.

As an intermediate step in the proof of the theorem, we need to know thatZˆ_M is irreducible overK(v). AsT_M is essentially a specialization ofZˆ_M, this would follow from [4] in the case whereKhas characteristic zero. However, the multivariate case allows for a much simpler proof, and one which holds for any characteristic.

Lemma 3 LetMbe a finite connected matroid. ThenZˆM is irreducible overK(v).

Proof The induction proof is most conveniently formulated by considering a coun- terexampleM wherer(M)is minimal; among those counterexamples, we pick one where|E| is minimal. Clearly, the result holds for r(M)=1, so r(M)≥2. Pick e∈E. By Lemma2,ZˆM = ˆZM\e+veZˆM/e. Note thatve does not appear inZˆM\e

andZˆ_M/e. IfM\eis connected, thenZˆ_M\e is irreducible by minimality of|E|. As ZˆM andZˆM\ehave the same degree, settingve=0 shows thatZˆM is irreducible, a contradiction. SoM\eis not connected, which by Tutte’s theorem means thatM/e is connected. Sor(M/e)≥1 (becauser(M)≥2), andZˆ_M/eis monic. Note also that becauseMis loopless, so too isM\e, and henceZˆ_M\eis also monic.

Now, consider a non-trivial factorization ofZˆM. SinceZˆM is monic and linear in ve, we can writeZˆM=(U+veV )W, whereU, V , W are polynomials inK[v][q]in whichv_edoes not appear, and where each factor has positive degree inq.

So(U +v_eV )W = ˆZ_M\e+v_eZˆ_M/e. Comparing coefficients with respect to v_e givesU W= ˆZM\eandV W= ˆZM/e. By minimality of the counterexample,ZˆM/eis irreducible. ButWhas positive degree inq, soV =1 andW= ˆZ_M/e. ThusUZˆ_M/e= Zˆ_M\e. Now,Zˆ_M/eandZˆ_M\eare monic of degreesr(M)−1 andr(M), respectively.

SoU=q+β for someβ∈K[v]. Letv¯=v\ {v_e}, and note that Zˆ_M\e(1,v)¯ =

i∈E\e

(1+v_i)= ˆZ_M/e(1,v),¯

soβ=0. Now settingq=0 givesZˆ_M\e(0,v)¯ =0. This means that there are no bases inM\e, which is only possible if every element of E\eis a loop. So we have a

contradiction.

In order to prove the theorem, we need more precise information about how Galois groups behave under specializations of parameters. The next result is well-known, it follows, for instance, from [3, Theorem IX.2.9].

Proposition 4 LetRbe an integral domain which is integrally closed in its quotient fieldF. Let f ∈R[X]be monic and irreducible overF. Let R→k, r→ ¯r be a homomorphism to a fieldk. Iff¯∈k[X]is separable, then Gal(f / k)¯ is a subgroup of Gal(f/F ).

The following two lemmas can be obtained through applications of this proposi- tion.

Lemma 5 Let A be a subset of E. Then Gal(Zˆ_M|A/K(vA)) is a subgroup of Gal(Zˆ_M/K(v)).

Proof Let B be such that A⊂B⊆E, and let e be an element of B\A. Note that removinge fromB corresponds to specializingv_e to zero inZˆ_M|B. LetR= K(vB\e)[ve], and letI be the maximal ideal ofRgenerated byve. The image ofZˆM

in the canonical homomorphismR→R/I is eitherqZˆ_M|(B\e)orZˆ_M|(B\e), depend- ing on whether or noteis a coloop. In both cases, we have a separable polynomial, as the presence of a repeated irreducible factor would contradict the fact thatZˆM|(B\e)

is linear in the elements of vB\e. Furthermore,R is integrally closed in its quotient fieldK(v). So we have that Gal(Zˆ_M|(B\e)/K(v_B\e))≤Gal(Zˆ_M|B/K(vB))by Propo-

sition4, and the result follows by induction.

Lemma 6 Letybe a variable over the fieldk, andU, V∈k[X]with degV=n−1, andU monic of degreen(wheren≥2). Suppose thatf (X)=U (X)+yV (X) is irreducible overk(y) (which is equivalent to U and V being relatively prime). If Gal(U/ k)=S_nor Gal(V / k)=S_n−1, then Gal(f/ k(y))=S_n.

Proof First suppose that Gal(U/ k)=Sn. Then the assertion follows immediately from Proposition4by settingR=k[y]and considering the homomorphismR→k, h(y)→h(0).

Now assume that Gal(V / k)=S_n−1. Set t=1/y and replace f (X)=U (X)+ yV (X)=U (X)+¹_tV (X)witht times the reciprocal off (X), that is, setf (X)ˆ = Xⁿ(t U (1/X)+V (1/X)). Clearly,k(t )=k(y)and Gal(f/ k(y))=Gal(f / k(t )). Theˆ coefficient ofXⁿinfˆist u+v, whereuandvare the constant terms ofUandV. If v=0, thenV has the root 0. However,V is irreducible since Gal(V / k)=S_n−1. So n=2. The result clearly holds in this case becausef is then irreducible of degree 2.

So assumev=0. Let R ⊂k(t ) be the localization of k[t] with respect to the ideal(t ), soRconsists of the fractionsp(t )/q(t )withq(0)=0. Note that _{t u}¹_+vfˆis monic with coefficients inR. Also,R(as a local ring) is integrally closed ink(t ). Let

R→kbe the homomorphism given byp(t )/q(t )→p(0)/q(0). Proposition4then gives Gal(f / k(t ))ˆ ≥Gal(XⁿV (1/X)/ k)=S_n−1. Because Gal(f / k(t ))ˆ is transitive on thenroots offˆ, we must have Gal(f / k(t ))ˆ =S_n.

We are now ready to prove Theorem1.

First proof of Theorem1 Again assume that the matroidMis a counterexample with r_M(E) minimal, and among these cases pick one with|E| minimal. Note that the statement is trivially true ifr(M)=1, thusr(M)≥2 in the minimal counterexample.

Picke∈E. By Lemma2,Zˆ_M= ˆZ_M\e+v_eZˆ_M/e. Letv¯=v\ {v_e}, and setk= K(v). Recall that¯ Zˆ_M is irreducible overk(v_e)by Lemma3. We have seen above that r(M\e)=r(M)=nandr(M/e)=n−1. As established previously, eitherM\eor M/eis connected. By assuming a minimal counterexample, we have Gal(Zˆ_M\e/ k)= Snor Gal(ZˆM/e/ k)=Sn−1. Theorem1then follows from Lemma6.

We will now present an alternative proof of Theorem1. While it is less efficient than the above proof, it uses a group-theoretical inductive process which is perhaps more intuitive. We will need to first prove that the theorem holds for circuits.

Lemma 7 LetC⊆Ebe a circuit of a finite matroidM. Then Gal(ZˆM|C/K(vC))= Sr_M(C).

Proof The rank of any proper subset ofCis the same as its cardinality, andrM(C)=

|C| −1, so:

ZˆM|C(q,v)=qⁿ+σ1qⁿ⁻¹+σ2qⁿ⁻²+ · · · +σn−1q+(σn+σn+1), whereσi is theith elementary symmetric polynomial in the{ve}e∈C for eachi. The elementary symmetric polynomials are algebraically independent, and thus so too are the coefficients ofZˆM|C(q,v). It is well known that the Galois group of a polynomial with algebraically independent coefficients is the full symmetric group.

Second proof of Theorem1 Let C be a circuit of maximum cardinality inM. By Lemma7, Gal(ZˆM|C/K(vC))=Sr_M(C). This will serve as the base case for the in- duction.

Now, letAbe any proper subset ofE such thatC⊆A andM|Ais connected, and suppose that Gal(Zˆ_M|A/K(vA))=S_rM(A). Identify a non-empty independent set B⊆E\Aof minimal size such thatM|(A∪B)is connected, and letA=(A∪B).

We will show that Gal(Zˆ_M|A/K(vA))=S_rM(A).

By [6, Lemma 1.3.1],r_M(A)≤r_M(A)+r_M(B). By maximality ofC, any circuit ofM|Ahas rank at mostr_M(C). By minimality ofB, any circuit ofM|Anot con- tained inM|Amust include at least one element ofA, sor_M(B)≤r_M(C)−1, and we haver_M(A)≤r_M(A)+r_M(C)−1.

By Lemma 5, S_rM(A) = Gal(Zˆ_M|A/K(vA)) ≤ Gal(Zˆ_M|A/K(vA)). So Gal(Zˆ_M|A/K(v_A))must contain at least one transposition. LetHbe the group gen- erated by all of the transpositions in Gal(Zˆ_M|A/K(vA)); thenHis a direct product

of symmetric groups. As Gal(Zˆ_M|A/K(vA)) is transitive, each of these symmet- ric groups must have the same degreei, which must therefore divide the degree of Gal(Zˆ_M|A/K(v_A)). By Lemma3,Zˆ_M|A is irreducible, and its Galois group must therefore be transitive of degree r_M(A). So we have that j i=r_M(A) for some positive integerj.

Now,S_rM(A)contains at least one of the transpositions ofH, so must be a subgroup of one of theS_i, which meansr_M(A)≤i. So we have:

j rM(A)≤j i=rM(A)≤rM(A)+rM(C)−1.

Suppose thatj≥2. Then 2rM(A)≤r_M(A)+r_M(C)−1, and sor_M(A)≤r_M(C)−1.

This is impossible, as C ⊂A. So j =1, and hence i =r_M(A). This means that H is a direct product of symmetric groups of degree rM(A). But H is a subgroup of Gal(Zˆ_M|A/K(vA)), which is transitive of degree r_M(A), and so

Gal(Zˆ_M|A/K(v_A))=H=S_rM(A).

Now, in view of the proof of Lemma7, one might wonder if the coefficients of Zˆ_M(q,v)are algebraically independent for any finite connected matroid. This does indeed turn out to be the case, leading us to our third and final proof of Theorem1.

Third proof of Theorem1 LetMbe a finite connected matroid of rankr(M)=n≥1, and writeZˆ_M(q,v)=qⁿ+a_n−1qⁿ⁻¹+ · · · +a1q+a0∈K[v][q], whereKis an ar- bitrary field. It suffices to show that the coefficientsa0, a1, . . . , an−1are algebraically independent overK.

Ifn=1, thenZˆ_M(q,v)=q−1+

e∈E(v_e+1), so the claim clearly holds. Thus we may assumen≥2.

Assume thatM is a counterexample in which|E| is minimal. We will use the deletion–contraction identityZˆM= ˆZM\e+veZˆM/eof Lemma2. First consider the case thatM\eis connected. By the assumption of a minimal counterexample, the co- efficients ofZˆ_M\e(excluding the leading coefficient 1) are algebraically independent overK. However, these coefficients arise from the coefficientsa0, a1, . . . , an−1upon settingv_e=0. Of course, an algebraic dependency relation ofa₀, a₁, . . . , a_n−1over Kremains an algebraic dependency relation upon settingv_e=0, a contradiction.

ThusM\eis not connected, so we may assume thatM/eis connected. For each 0≤i≤n−1, writea_i=b_i+v_ec_i, whereb_iandc_iare polynomials in the elements of v_E\e. Eachc_j is then the coefficient ofq^j inZˆ_M/e, soc_n−1=1 (asr(M/e)=n−1) andc0, c1, . . . , cn−2 are algebraically independent overK. Asa0, a1, . . . , an−1 are algebraically dependent, there is a non-zero polynomialP innvariables overKsuch that

P (b₀+v_ec₀, . . . , b_n−2+v_ec_n−2, b_n−1+v_e)=0.

LetQbe the expansion ofP with respect tov_e, so thatQis a polynomial inv_ewith coefficients inK[vE\e]. As the elements of v are algebraically independent, these coefficients must be identically zero. Let d be the total degree ofP. Then Qhas degreed inv_e, and thev^d_e term must arise from a K-linear sum of products of the form:

(b₀+v_ec₀)^d0· · ·(b_n−2+v_ec_n−2)^dn−2(b_n−1+v_e)^dn−1,

whered₀, . . . , d_n−1are non-negative integers which sum tod. This means that the co- efficient ofv_e^dinQis aK-linear combination of monomials of the formc^d₀⁰· · ·c^d_nⁿ⁻₋₂², wheredi ≥0 for eachi, andd0+ · · · +dn−2≤d. The vanishing of this coefficient then implies that the set of such monomials is linearly dependent over K, which contradicts our assertion thatc₀, . . . , c_n−2are algebraically dependent overK.

Remark 8 Sokal showed that the multivariate Tutte polynomial for matroids factor- izes over summands (see [7, (4.4)]). That is, ifM is the direct sum of connected matroidsM1, M2on the setsE1, E2, respectively (whereE1andE2are disjoint and E=E1∪E2) then:

Zˆ_M(q,v)= ˆZ_M1(q,vE1)Zˆ_M2(q,vE2).

As vE1 and vE2 are disjoint, there are clearly no algebraic dependencies between the roots ofZˆ_M1 andZˆ_M2, so we have that

GalZˆ_M/K(v)

=GalZˆ_M1/K(vE1)

×GalZˆ_M2/K(vE2) .

Theorem1then implies that the Galois group of the multivariate Tutte polynomial of any matroid is a direct product of symmetric groups corresponding to the connected direct summands.

Finally, we computed the Galois group of the bivariate Tutte polynomialTG(x, y) overQ(y)for every biconnected graphGof ordern≤10, and found that all were the symmetric group of degreen−1. As the Tutte polynomial of any connected matroid is irreducible over fields of characteristic zero (as noted in [4], this is not necessarily the case for fields of positive characteristic), this would seem to suggest the following:

Conjecture 9 LetMbe a finite connected matroid with positive rankn=r(M), and letKbe a field of characteristic zero. Then the Galois group of the Tutte polynomial TM(x, y)overK(y)is the symmetric group of degreen.

As remarked previously, the bivariate Tutte polynomial is essentially a special- ization of the multivariate version. This means that Theorem1would follow from a proof of Conjecture9for fields of characteristic zero.

Interestingly, specializing the Tutte polynomial further produces a range of differ- ent Galois groups. For example, it was shown in [1] that all of the transitive permu- tation groups of degree at most 5 apart fromC5appear as Galois groups of just one family of chromatic polynomials. Furthermore, Morgan [5] showed that a range of transitive groups of higher degree occur for chromatic polynomials of graphs on up to 10 vertices.

References

1. Cameron, P.J., Morgan, K.: Algebraic properties of chromatic roots. Submitted

2. Kung, J.P.S.: Twelve views of matroid theory. In: Combinatorial & Computational Mathematics:

Present and Future, Pohang, the Republic of Korea, 15–17 February 2000, p. 56 (2001)

3. Lang, S.: Algebra. Addison-Wesley, Menlo Park (1984)

4. Merino, C., de Mier, A., Noy, M.: Irreducibility of the Tutte polynomial of a connected matroid.

J. Comb. Theory 83, 298–304 (2001)

5. Morgan, K.: Algebraic aspects of the chromatic polynomial. PhD thesis

6. Oxley, J.G.: Matroid Theory, Oxford Science Publications. Clarendon/Oxford University Press, New York (1992)

7. Sokal, A.D.: The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In: Surveys in Combinatorics, vol. 327, pp. 173–226 (2005)