Spanning trees and a conjecture of Kontsevich
Abstract
Description
Kontsevich conjectured that the number f(G,q) of zeros over the finite field with q elements of a certain polynomial connected with the spanning trees of a graph G is polynomial function of q. We have been unable to settle Kontsevich's conjecture. However, we can evaluate f(G,q) explicitly for certain graphs G, such as the complete graph. We also point out the connection between Kontsevich's conjecture and such topics as the Matrix-Tree Theorem and orthogonal geometry.
18 pages. This version corrects some minor inaccuracies and adds some computational information provided by John Stembridge
18 pages. This version corrects some minor inaccuracies and adds some computational information provided by John Stembridge