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

Get the DVI| PS|PDFfile of this abstract.