Counting Points on Varieties over Finite Fields Related to a Conjecture of Kontsevich
John R. Stembridge
Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109–1109, USA
Annals of Combinatorics 2 (4) p.365-385 December, 1998
AMS Subject Classification: 05A15, 05-04, 14Q15, 68Q40
We describe a characteristic-free algorithm for "reducing" an algebraic variety defined by the vanishing of a set of integer polynomials. In very special cases, the algorithm can be used to decide whether the number of points on a variety, as the ground field varies over finite fields, is a polynomial function of the size of the field. The algorithm is then used to investigate a conjecture of Kontsevich regarding the number of points on a variety associated with the set of spanning trees of any graph. We also prove several theorems describing properties of a (hypothetical) minimal counterexample to the conjecture, and produce counterexamples to some related conjectures.
Keywords: spanning trees, matroids, computational algebra


1. T. Chow, private communication.

2. C.L. Dodgson, Condensation of determinants, Proc. Roy. Soc. London 15 (1866), 150-155.

3. L. Lováisz, Combinatorial Problems and Exercises, North-Holland, Amsterdam, 1979.

4. J.G. Oxley, Matroid Theory, Oxford University Press, New York, 1992.

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

6. D. Zeilberger, Dodgson's determinant-evaluation rule proved by two-timing men and women, Electron. J. Combin. 4(2) R22 (1997), 2pp.

This site is maintained by Bill Chen. If you have any suggestions or anything to contribute, please contact me at
津教备0272号 津ICP备06011496号