On Polynomials of Spanning Trees

Fan Chung^{1}, Chao Yang^{2}

fan@euclid.ucsd.edu

Annals of Combinatorics 4 (1) p.13-25 March, 2000

Abstract:

The Kirchhoff polynomial
of a graph *G* is the sum of weights of all spanning trees where the
weight of a tree is the product of all its edge weights, considered as
formal variables. Kontsevich conjectured that when edge weights are assigned
values in a finite field ,
for a prime power *q*, the number of zeros of the Kirchhoff polynomial
of a graph *G* is just a polynomial function of *q*. Stanley
verified this conjecture for some families of graphs and further proposed
several conjectures. In this paper, we derive and prove explicit formulas
for certain graphs, thus confirming Stanley's conjectures. We also consider
several extensions and generalizations of the conjecture of Kontsevich.

References:

1. R.P. Brent and B.D. McKay, On determinants of random matrices over Z m , Discrete Math. 66 (1987) 35-49.

2. R.P. Brent and B.D. McKay, Determinants and ranks of random matrices over Z m , Ars Combinatoria 26A (1988) 57-64.

3. L. Carlitz, Representations by quadratic forms in a finite field , Duke Math. J. 21 (1954) 123-137.

4. F. Kirchhoff, Über die Auflösung der Gleichungen , auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird, Ann. Phys. Chem. 72 (1847) 497-508.

5. M. Kontsevich, Gelfand Seminar Talk , Rutgers University, December 8, 1997.

6. J. MacWilliams, Orthogonal matrices over finite fields , Amer. Math. Monthly 76 (1969) 152-164.

7. R. Stanley, Spanning trees and a conjecture of Kontsevich , Ann. Combin. 2 (1998) 351-363.

8. J.R. Stembridge, Counting points on varieties over finite fields related to a conjecture of Kontsevich , Ann. Combin. 2 (1998) 365-385.

9. J.J. Sylvester, On the change of systems of independent variables , Quarterly J. of Math. 1 (1857) 42?6; Collected Mathematical Papers, Cambridge 2 (1908) 65-85.

10. C. Yang, The probabilistic Kirchhoff polynomials over finite field and a conjecture of Kontsevich , Ph.D. Thesis, University of Pennsylvania, March 1999.