Annals of Combinatorics 2(1998) 351-363
Spanning Trees and a Conjecture of Kontsevich
Richard P. Stanley
Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA
Received October 30, 1998
AMS Subject Classification: 05E99
Abstract. Kontsevich conjectured that the number of zeros over the field Fq of a certain polynomial QG associated with the spanning trees of a graph G is a polynomial function of q. We show the connection between this conjecture, the Matrix--Tree Theorem, and orthogonal geometry. We verify the conjecture in certain cases, such as the complete graph, and discuss some modifications and extensions.
Keywords: spanning tree, Matrix--Tree Theorem, orthogonal geometry