<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 4 Issue 1" %>
On Polynomials of Spanning Trees
Fan Chung1, Chao Yang2
1University of California,San Diego, La Jolla, CA92093-0112, USA
2University of Pennsylvania, Philadelphia, PA 19104, USA
Annals of Combinatorics 4 (1) p.13-25 March, 2000
AMS Subject Classification:05E99
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 $ {\mathbb{F}}_q$, 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.
Keywords: Kirchhoff polynomials, matrix-tree theorem, probabilistic Kirchhoff polynomial, combinatorial Laplacian, spanning trees


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.