Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
T. Chow, private communication.
C.L. Dodgson, Condensation of determinants, Proc. Roy. Soc. London15 (1866), 150–155.
L. Lovász, Combinatorial Problems and Exercises, North-Holland, Amsterdam, 1979.
J.G. Oxley, Matroid Theory, Oxford University Press, New York, 1992.
R.P. Stanley, Spanning trees and a conjecture of Kontsevich, Ann. Combin.2 (1998) 351–363.
D. Zeilberger, Dodgson's determinant-evaluation rule proved by two-timing men and women, Electron. J. Combin.4(2) R22 (1997), 2pp.
Author information
Authors and Affiliations
Additional information
Partially supported by NSF Grant DMS-9700787 and RIMS, Kyoto University.
Rights and permissions
About this article
Cite this article
Stembridge, J.R. Counting points on varieties over finite fields related to a conjecture of Kontsevich. Annals of Combinatorics 2, 365–385 (1998). https://doi.org/10.1007/BF01608531
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF01608531