INCIDENCE SCHEMES AND A CONJECTURE OF KONTSEVICH

PRAKASH BELKALE AND PATRICK BROSNAN

Abstract. Motivated by the relationship between Feynman amplitudes and multiple zeta values, Kontsevich introduced a polynomial P_{G} associated to every graph G and conjectured that the number of zeros of P_{G} over F_{q} is a polynomial in q. In studying this conjecture, Stanley introduced a closely related polynomial Q_{G} and showed that Kontsevich’s conjecture is true if and only if the number of zeroes of Q_{G} over F_{q} is a polynomial. Motivated by Stanley’s work, Stembridge proposed an a priori weaker conjecture: Let A be the adjacency matrix of a simple graph with n vertices. Then the number of n×n non-degenerate symmetric matrices M over F_{q} such that A_{ij}M_{ij} = 0 for all i, j is a polynomial in q. Using matroid theory, we prove the existence of a counterexample for all three conjectures, but verify Stembridge’s conjecture in several interesting cases. In spite of the counterexample, several interesting questions are raised by the methods of this article.

1. Introduction

Let G be a graph with vertices V = V (G) and edges E = E(G). We assume that G has neither multiple edges (two edges between the same two vertices) nor loops (an edge connecting a vertex to itself), and we assume that V is finite. Under these conditions one can view E as a subset of the set Sym^{2} V with Sym^{2} V ⊂ P(V) equal to the set of subsets of V having exactly two elements. Let S = S(G) ⊂ P(E) be the set of spanning trees of G.

For each edge e ∈ E, let x_{e} denote a formal variable. It is classical in circuit theory (e.g. Maxwell, Kirchoff, etc.) to consider the following

The second author would like to thank the Max-Planck-Institut für Mathematik in Bonn for its hospitality and support during the year when most of the work in this article was done.

two polynomials:

P_{G} = ∑_{T ∈S} ∏_{x_{e}∉T} x_{e}  (1.1)
Q_{G} = ∑_{T ∈S} ∏_{x_{e}∈T} x_{e}.  (1.2)

Let X_{G} (resp. Y_{G}) denote the scheme (a hypersurface) defined by Q_{G} (resp. P_{G}) over the integers. That is, X_{G} = V (Q_{G}) and Y_{G} = V (P_{G}). Motivated by computer calculations of Feynman amplitudes, Kontsevich has speculated that the periods of Y_{G} are “multiple zeta values” — that is, values of certain generalized zeta functions. And it seems that, given this information on the periods, it is natural to expect that the zeta functions associated to X_{G} and Y_{G} are zeta functions of motives of mixed Tate type.

Based on this idea, Kontsevich has made a number theoretic conjecture about the points of Y_{G} over a finite field. To describe this conjecture, we first make a notational convention: For any scheme X which is separated and of finite type over Z, we let [X] denote the function q ↦ #X(F_{q}). Thus [X] is a function from the set of primary numbers Q (i.e. positive integers with only one prime factor) to Z. We will say that X is polynomially countable or simply countable if [X] is a polynomial in q.

Conjecture 1.1 (Kontsevich). For all graphs G, Y_{G} is countable.

Using a Maple program Stembridge [Ste98] has verified this conjecture for all graphs with fewer than 12 edges. For certain graphs — e.g. cycles — it is relatively easy to see that the conjecture holds. For example, one sees easily that, for a G a cycle of length n, Y_{G} is simply A^{n−1} and, thus, [Y_{G}] = q^{n−1}.

There is an analogous conjecture for X_{G}, and this has been studied by both Stanley [Sta98] and Stembridge [Ste98].

Conjecture 1.2 (Stanley). For all graphs G, X_{G} is countable.

We will refer to Conjecture 1.1 as Konsevich’s conjecture and, although Conjecture 1.2 was not explicitly stated as a conjecture by Stanley, we will refer to it as Stanley’s conjecture.

Stanley has in fact shown that the two conjectures are equivalent. However, knowing Stanley’s conjecture for a particular graph G is not known to imply Kontsevich’s conjecture for that same G. In fact, knowing Stanley’s conjecture for one G alone is not known to imply Kontsevich’s conjecture for any other graph. To deduce Kontsevich’s conjecture for one G one must know Stanley’s conjecture for a rather large number of graph related to G (see [Ste98] Section 4).

There is another conjecture, which is in fact a special case of Stanley’s, stated by Stembridge as Conjecture 7.1 of [Ste98]. We now give the conjecture in a slightly different form than in the abstract. Let V (G) = {v_{1}, …, v_{n}} and let Z_{G}(F_{q}) be the set of n × n nondegenerage symmetric matrices M such that M_{ij} = 0 unless i = j or there is an edge from v_{i} to v_{j}.

Conjecture 1.3 (Stembridge). #Z_{G}(F_{q}) is a polynomial in q.

To explain how Stembridge’s conjecture is a special case of Stanley’s we need to introduce some notation. A vertex v is said to be an apex of G if it is connected by an edge to every other vertex in G. If we take a graph G not necessarily having an apex, there is a canonical way of producing a graph G^{∗} with an apex. Namely, one adds a vertex v_{0} and connects it to every other vertex v_{i} by an edge. Conversely, if G is a graph with vertices {v_{0}, …, v_{n}} such that v_{0} is an apex, then G = Γ^{∗} where Γ is the graph obtained from G by removing v_{0} and all edges connected to it.

Using the Matrix-Tree theorem, which we will review in Section 4, Stanley showed that his conjecture for G is equivalent to Stembridge’s conjecture for G^{∗}. This was in fact Stembridge’s motivation for stating his conjecture.

Given a subgraph F of G let the complement G − F of F in G be the graph with the same vertices as G but with all the edges in F removed. Let K_{n} be the complete graph with n vertices. (I.e, K_{n} has an edge between any pair of vertices). Let K_{1,s} be the star with one vertex connected to s other vertices (see [Sta98] Section 5.4). In [Sta98], Stanley has verified Stembridge’s conjecture in the following cases: G = K_{n} (Theorem 4.1), G = K_{n} − K_{m} (Section 5) and G = K_{n} − K_{1,s} (Theorem 5.4). Here, of course, one must take m ≤ n and s < n. Using the fact that (K_{n} − G)^{∗} = K_{n+1} − G, one sees that Stanley’s conjecture is true for G = K_{n}, G = K_{n+1} − K_{m} (for n ≥ m) and G = K_{n+1} − K_{1,s} for n > s.

In this paper, we verify Stembridge’s conjecture for G = K_{n} − F where F is any forest (Corollary 9.3). This generalized Stanley’s Theorem 5.4. We also show that the truth of Stembridge’s conjecture for a rather large set of graphs related to a graph G implies Stanley’s conjecture (Theorem 10.2) for G.

However, in the last section, we show that Stembridge’s conjecture is false for general G. This we do by showing that, if Stembridge’s conjecture were true for all graphs G, then every matroid M representable over a field of characteristic p would have to be representable over all fields.

But suppose we change the definition of what is countable. Consider the following definitions.

1. Call a scheme X (of finite type over Z) countable in each prime if given a prime p, there is a polynomial f_{p} so that #X(F_{q}) = f_{p}(q) for every q = p^{l}.

2. Call a scheme X (of finite type over Z) countable for almost all primes, if there is a finite set S of prime numbers, so that #X(F_{q}) is a polynomial in q, for all q = p^{l} where p ∉ S.

3. Let C be a class of integer valued functions on the primary positive integers which contains the polynomial functions, closed under multiplication and division. Call a scheme X (of finite type over Z) C-countable if q ↦ #X(F_{q}) is a function in C.

The methods of this article are equally valid for any definition of countability as above. For example Stembridge’s conjecture with countable replaced by countable for almost all primes implies Kontsevich’s and Stanley’s conjecture with countable replaced by countable for almost all primes. At this point we do not know if Stembridge’s conjecture holds for almost all primes.

The paper is organized as follows: In Section 2, we discuss certain schemes which will be basic for the paper. In Section 3, we prove a basic result about polynomial countability. In Section 4, we review Stanley’s use of the Matrix-Tree theorem and we reformulate Stembridge’s conjecture slightly. In Section 5, we introduce the incidence schemes A_{G}(s, r, k) for s, r, j ∈ N from the title of the paper. Using the Matrix-Tree theorem and the basic result of Section 3, we show in Theorem 5.5 that X_{G} is countable if and only if A_{G}(m, m, m) is countable for m = #V (G) − 1. In Section 6, we establish certain relations among the functions [A_{G}(s, r, k)] for varying s, r, and k. These relations enable us to show in Section 7 that all of the [A_{G}(s, r, k)] are determined by certain smaller subsets (for example, the [A_{G}(s, s, s)]). Using these results, we show in Section 8 that Stembridge’s conjecture is true if and only if the varieties A_{G^{∗}}(s, r, k) are countable for every graph G.

In Section 5, we introduce a scheme J_{G}(s) which is a union of certain A_{G}(s, r, k). And in Section 7 it will be seen that the countability of the J_{G}(s) is equivalent to the countability of all the A_{G}(s, r, k). It turns out that in the case that G is a forest complement (i.e. G = K_{n} − F with F a forest) the countability of J_{G^{∗}}(s) is easy to verify. We do this in Section 9 thereby proving in Corollary 9.3 that Z_{G} is countable for G a forest complement. In Section 10, we compare incidence schemes for G with incidence schemes corresponding to a various schemes associated to G. By doing this, we show that, if Stembridge’s conjecture is true for a certain set of graphs related to G, then Stanley’s conjecture is true for G.

Finally, in Section 11, we combine the work of all the previous sections to prove the existence of counterexamples to all three conjectures.

1.1. Notational. If X is a finite set, we write #X or |X| interchangeably for the number of points in X. When counting points of a scheme X over a field F_{q} we often view X simply as a set without reflecting this in the notation. It should be clear from the context when we mean X and when we mean X(F_{q}).

We are constantly working with graphs G with vertex set V = {v_{1}, …, v_{n_{G}}} and we constantly need to refer to the number n_{G} − 1. To compactify the notation we therefore set m_{G} = n_{G} − 1. When there is only one graph G under discussion we drop the G in the subscript and write simple n for |V (G)| and m for n − 1.

In this draft, we take a somewhat cavalier attitude to what constitutes a scheme over Z. We find that is is clearer to define a scheme X by simply giving its K points for K a field. Of course, this is not enough (or rather heretical to algebraic geometers). We promise to rectify this in the final version. We intend that this be accessible to combinatorialists, working on the problem. Aside from the use of Weil conjectures in section 3, the fact that Grassmannians are countable, the methods and the results of this article should be accessible to a wide audience.

1.2. Acknowlegments. The authors would like to thank T. Chow, N. Fakhruddin, A. Schwarz and B. Toen for useful conversations and suggestions.

2. Basic Schemes

Let R be a ring and E, F free R-module of ranks e and f respectively. Hom(E, F)_{R} (or simply Hom(E, F) when R is obvious — and for us it will be almost always be Z) is then a scheme which is isomorphic to A^{ef}. We write Hom_{r}(E, F) for the locally closed subscheme of Hom(E, F) whose K points — for K a field over R — consist of morphisms ψ : E⊗K → F ⊗K of rank r. We mention that, when L is an arbitrary ring over R, the L points of Hom_{r}(E, F) are the maps ψ : E ⊗ L → F ⊗ L with locally free rank f −r cokernel. Of course, Hom_{e}(E, E) = GL(E).

We define Bil(E) to be the scheme over R of symmetric bilinear forms on E. This is isomorphic to A^{\binom{e+1}{2}} and it is a closed subscheme of Hom(E, E^{∨}). We define Bil_{r}(E) to be the intersection of Bil(E) with Hom_{r}(E, E^{∨}). For K a field, Bil_{r}(E)(K) is the set of rank r bilinear forms on E ⊗ K. We write Bil_{r}^{n} for Bil_{r}(Z^{n}). For a set S, we write E^{S} or Fun(S, E) for the scheme Hom(R^{S}, E). The L points of this scheme for any ring L over R is the set of maps f from S to E ⊗ L. We write (E^{S})_{r} or Fun_{r}(S, E) for the scheme Hom_{r}(R^{S}, E).

Write Gr(r, F) for the Grassmanian of r-planes in F. This is defined in EGA [GD67]. We remark that there is a natural map Hom_{r}(E, F) → Gr(r, F) which for K valued points sends a map to its image. For Fun_{r}(S, E) this map is written as f ↦ ⟨f⟩.

As mentioned above, we always take R = Z unless otherwise specified. For future reference, we remark that all of the above schemes are countable and we give their associated polynomials.

[GL_{n}] = (q^{n} − 1)(q^{n} − q) ⋯ (q^{n} − q^{n−1})  (2.1)
[Gr(a, b)] = \frac{[GL_{b}]}{[GL_{a}][GL_{b−a}]q^{a(b−a)}}  (2.2)
[Hom_{r}(E, F)] = [Gr(r, e)][Gr(r, f)][GL_{r}]  (2.3)

The first two of the above are well known and the last is easy. That the rational functions give are actually polynomials can either be checked by hand or one can apply Theorem 3.1 of the next section.

More difficult is the following formula which is taken from [Sta98] who attributes it to [Mac69].

[Bil_{r}^{n}] = \{ \begin{matrix}∏_{i=1}^{s} \frac{q^{2i}}{q^{2i}−1} · ∏_{i=0}^{2s−1}(q^{n−i} − 1), 0 ≤ r = 2s ≤ n, \\ ∏_{i=1}^{s} \frac{q^{2i}}{q^{2i}−1} · ∏_{i=0}^{2s}(q^{n−i} − 1), 0 ≤ r = 2s + 1 ≤ n \end{matrix} (2.4)

In sections 10 and 11, we will need to countability of one other type of scheme. But it is more easily expressed as the dimension of a vector space.

Let

A = F^{0}A ⊃ F^{1}A ⊃ ⋯ ⊃ F^{r−1}A ⊃ F^{r}A = 0  (2.5)

be a filtered vector space over a field F. We write F^{•}A for the filtered vector space. And we say that r is the length of the filtration. Let

a_{i} = dim(F^{i}A − F^{i+1}A),
a^{i} = dim F^{i}A.

If F^{•}B is a another filtered vector space, we write Hom(F^{•}A, F^{•}B) for the F-vector space of maps f ∈ Hom(A, B) such that f(F^{i}A) ⊂ F^{i}B.

Proposition 2.1. dim Hom(F^{•}A, F^{•}B) = ∑ a_{i}b^{i}.

Proof. The proof is by induction on the length r of F^{•}A. The result is obvious when the length is 0 or 1. Now let W^{•}A be the filtered space with W^{i}A = F^{i+1}A, and W^{•}B be the filtered space with W^{i}B = F^{i+1}B. W^{•}A has length r − 1, and we have an exact sequence

Hom(A/F^{1}A, B) ↣ Hom(F^{•}A, F^{•}B) ↠ Hom(W^{•}A, W^{•}B),

where the first Hom is of unfiltered vector spaces. The result then follows by induction.

3. Polynomial Countability

Let S be an infinite set and let R be a ring. We define Ae(S, R) to be the quotient of the ring of functions Fun(S, R) obtained by identifying any two functions f and g which agree outside of a finite set. We let ψ : Fun(S, R) → Ae(S, R) be the quotient map. We write f = g a.e. if ψ(f) = ψ(g) and note that ψ(f) is well-defined for any f defined outside of a finite set. If S ⊂ Q we note that there is an injection Q[x] → Ae(S, Q).

If f is a function on S and R is a subset of Q(q), we say that f ∈ R a.e. if there is a (necessarily unique) rational function g ∈ R such that f = g a.e. When X is a scheme of finite type over Z, we consider the function [X] as defined on the set S = Q. The goal of this section is to prove the following:

Theorem 3.1. If X is a scheme of finite type over Z and [X] ∈ Q(q) a.e. then X is countable.

The theorem is a slight generalization of Theorem 2.2 of [Sta98]. Its proof, which will occupy the rest of this section, is also a generalization of Stanley’s proof based on Dwork’s theorem [Dwo60].

Suppose now that X is a scheme of finite type over F_{p}. We write p^{Z^{+}} = {p^{n}| n ∈ Z^{+}} and we write [X]_{p} for the function p^{n} ↦ #X(F_{p^{n}}). We say that X is countable on p^{Z^{+}} if [X]_{p} ∈ Z[q]. It is easy to see that Theorem 3.1 follows directly from the following:

Theorem 3.2. If X is a scheme of finite type over F_{p} and [X]_{p} = f(q) a.e. on p^{Z^{+}} for some function f ∈ Q(q) then X is countable on p^{Z^{+}}.

We begin the proof of Theorem 3.2 with an easy lemma.

Lemma 3.3. If [X]_{p} ∈ Q(q) a.e. then [X]_{p} ∈ Q[q] a.e.

Proof. Actually, since [X]_{p}(q) ∈ Z for all q, this follows from a more general statement: If S is an infinite subset of Z and f : S → Z is any function such that f ∈ Q(q) a.e. then f ∈ Q[q] a.e.

To see this, set f = a/b with a, b ∈ Z[q]. Then a = db + r with deg r < deg b and with d, r ∈ Q[q]. Pick N ∈ Z^{+} such that Nd, Nr ∈ Z[q]. Then Na/b(q) = Nd(q) + Nr(q)/b(q) ∈ Z for all q. Thus Nr(q)/b(q) ∈ Z for all q. This, however, that r = 0. For otherwise, since deg r < deg b, lim_{q→∞} Nr(q)/b(q) = 0 and thus Nr(q)/b(q) = 0 for all q sufficiently large. And this itself implies that r = 0.

Thus in proving Theorem 3.2 we may assume that f(q) ∈ Q[q]. We will prove that f(q) ∈ Z[q] and that [X]_{p}(q) = f(q) for all q ∈ p^{Z^{+}} simultaneously using the rationality of the zeta function proved by Dwork [Dwo60].

We first recall that, for X a scheme of finite type over F_{p}, the zeta function of X is defined as

Z(X, t) = exp(∑_{k≥1} #X(F_{p}^{n})t^{n}/n).  (3.1)

Dwork showed that Z(X, t) is a rational function. It follows, since Z(X, t) is also an exponential, that there are nonzero complex numbers α_{1}, …, α_{r} and integers a_{1} …, a_{r} such that

Z(X, t) = ∏_{i=1}^{r}(1 − α_{i}t)^{−a_{i}}.  (3.2)

Now, let Div G_{m} be the set of all divisors on G_{m}, that is, the set of all finite formal sums ∑ a_{i}[α_{i}] with a_{i} ∈ Z and α_{i} ∈ C − {0}. (Div G_{m}) ⊗ Q is then the set of all such formal sums with a_{i} ∈ Q. For D ∈ (Div G_{m})⊗Q we let deg D = ∑ a_{i}. For f = a ∏(x−β_{i})^{b_{i}} ∈ C(x)^{×} we write div f for the divisor ∑_{β_{i}≠0} b_{i}[β_{i}].

For any D ∈ (Div G_{m}) ⊗ Q, we write N_{D}(k) for the (finite) sum ∑ a_{i}α_{i}^{k}. We write

f_{D}(t) = ∑_{k≥1} N_{D}(k)t^{k−1},  (3.3)
g_{D}(t) = ∑_{k≥1} N_{D}(k)t^{k}/k,  (3.4)
Z_{D}(t) = exp(∑_{k≥1} N_{D}(k)t^{k}/k).  (3.5)

We remark that if Δ_{D} is the maximum of the absolute values of the α_{i} then all of the above expressions converge for |t| < 1/Δ_{D}. If we pick 0 < R_{D} < 1/Δ_{D} then all of the above expressions converge absolutely for |t| < R_{D}. In the region |t| < R, it is then easy to see that

f_{D}(t) = ∑ \frac{a_{i}α_{i}}{1 − α_{i}t}  (3.6)
g_{D}(t) = − ∑ a_{i} log(1 − α_{i}t).  (3.7)

The first equation follows by summing the geometric series f_{D}(t) and the second follows by integrating this series termwise. Here log is a single valued function for |t| < R with log(1) = 0. It follows that, for D ∈ Div G_{m},

Z_{D}(t) = ∏(1 − α_{i}t)^{−a_{i}}  (3.8)

Thus Dwork’s theorem can be phrased as saying that for any scheme of finite type over F_{p} there exists a D ∈ Div G_{m} such that

Z(X, t) = Z_{D}(t).  (3.9)

Moreover, taking the logarithm of both sides of Equation 3.9, one sees that

[X]_{p}(p^{k}) = N_{D}(k)  (3.10)

for all k.

For D ∈ Div G_{m} we extend the definition of f_{D} and Z_{D} to rational functions on the entire complex plane using Equations 3.6 and 3.8.

Note that D can be obtained from the rational function Z_{D} by taking divisors. In fact,

D = − div Z(D, 1/t).  (3.11)

Now for any D_{1}, D_{2} ∈ (Div G_{m}) ⊗ Q and integers m_{1}, m_{2} it easy to see that

N_{m_{1}D_{1}+m_{2}D_{2}}(k) = m_{1}N_{D_{1}}(k) + m_{2}N_{D_{2}}(k)  (3.12)

Thus

f_{m_{1}D_{1}+m_{2}D_{2}} = m_{1}f_{D_{1}} + m_{2}f_{D_{2}},  (3.13)
g_{m_{1}D_{1}+m_{2}D_{2}} = m_{1}g_{D_{1}} + m_{2}g_{D_{2}},  (3.14)
Z_{m_{1}D_{1}+m_{2}D_{2}} = Z_{D_{1}}^{m_{1}}Z_{D_{2}}^{m_{2}}.  (3.15)

Proposition 3.4. Let D_{1}, D_{2} ∈ (Div G_{m}) ⊗ Q. If N_{D_{1}}(k) = N_{D_{2}}(k) for almost all k, then D_{1} = D_{2}.

Proof. Multiplying D_{1} and D_{2} by a suitable integer and using Equation 3.12, it is easy to see that it suffices to consider D_{1}, D_{2} ∈ Div G_{m}. Suppose then that N_{D_{1}} = N_{D_{2}} a.e. with D_{1}, D_{D} ∈ Div G_{m}. Set D = D_{1} − D_{2}. Then, by Equation 3.14, g_{D}(t) = tp(t) for some polynomial p. Thus Z_{D}(t) = exp(tp(t)). On the other hand, Z_{D}(t) ∈ C(t) by Equation 3.8. Since exponentials grow faster than polynomials, it follows that p(t) = 0. Thus g_{D} = 0 which implies that Z_{D} = 1, and, by Equation 3.11, this implies that D = 0.

Now we are ready to prove Theorem 3.2. Let Z(X, t) = Z_{D}(t) with D ∈ Div G_{m} as provided by Dwork’s theorem. As remarked earlier, by Lemma 3.3 we can assume that f ∈ Q[q]. Thus we write f(q) = ∑ b_{i}q^{i} with b_{i} ∈ Q. Set E = ∑ b_{i}[p^{i}] ∈ (Div G_{m}) ⊗ Q. We then have

f(p^{k}) = N_{E}(k)  (3.16)

for almost all k. On the other hand, from Equation 3.10, we have that

f(p^{k}) = N_{D}(k)  (3.17)

for almost all k. By Proposition 3.4, we then have that E = D and thus that f ∈ Z[q]. Then, by equation 3.10, we find that, for all k, #X(F_{p^{k}}) = f(p^{k}). Thus [X]_{p} is a polynomial.

We finish the section with one Corollary of Proposition 3.4 which will be conceptually useful in section 7.

Corollary 3.5. If X and Y are two schemes of finite type over F_{p} with [X]_{p} = [Y]_{p} a.e. then [X]_{p} = [Y]_{p}.

Proof. By Dwork’s theorem, we have divisors D_{1}, D_{2} ∈ Div G_{m} such that [X]_{p}(p^{k}) = N_{D_{1}}(k) and [Y]_{p}(p^{k}) = N_{D_{2}}(k). Thus, by Proposition 3.4, D_{1} = D_{2} and, hence, [X]_{p} = [Y]_{p}.

A direct consequence of Corollary 3.5 is the following

Corollary 3.6. If X and Y are two schemes of finite type over Z and [X] = [Y] a.e. then [X] = [Y].

4. The Matrix Tree Theorem

Stanley’s positive results mentioned in the introduction were mainly consequences of the Matrix-Tree Theorem of Kirchoff, Borchardt and Sylvester which gives an expression of the polynomial P_{G} as the determinant of a symmetric matrix. As this theorem is also basic to our results we briefly describe it.

4.1. For an edge e and a vertex v, we write v ∈ e to mean that the edge e meets the vertex v. Pick an ordering of the vertices of G so that V (G) = {v_{1}, …, v_{n}}. For v_{i}, v_{j} ∈ V (G), we write e_{ij} for the set {v_{i}, v_{j}}. We then write e_{ij} ∈ E to mean that there is an edge in G from v_{i} to v_{j}. We write x_{ij} for the variable x_{e_{ij}} when e_{ij} ∈ E. To simplify the notation we define x_{ij} = 0 for e_{ij} ∉ E.

Let L = L_{ij} be the n × n matrix defined by

L_{ij} = \{ \begin{matrix}∑_{k=1}^{n} x_{ik} & if i = j \\ −x_{ij} & if i ≠ j \end{matrix}

Let L_{0} be L with the last row and the last column removed. Stanley calls L the generic Laplacian matrix of G and L_{0} the reduced generic Laplacian.

Theorem 4.2 (The Matrix-Tree Theorem). P_{G} = det L_{0}.

Let X′_{G} denote the complement of X_{G} in A^{E}. Clearly X′_{G} is countable if and only if X_{G} is. Stanley’s use of the Matrix-Tree Theorem is based on the following important consequence.

Theorem 4.3. Assuming that v_{n} is an apex, [X′_{G}](q) is equal to the number of (n − 1) × (n − 1) nonsingular symmetric matrices M over F_{q} such that M_{ij} = 0 whenever i ≠ j and e_{ij} ∉ E.

Now let G be a graph with or without an apex and with vertices {v_{1}, …, v_{n}}. Let Z_{G} be the sub-scheme of GL_{n} whose K points for K a field are the non-singular symmetric matrices M_{ij} such that M_{ij} = 0 whenever e_{ij} ∉ E and i ≠ j. Taken together Theorem 4.3 and Conjecture 1.2 for G^{∗} imply that Z_{G} is countable as, in fact, [Z_{G}] = [X′_{G^{∗}}]. This leads to the following Conjecture 7.1 of [Ste98] which we present here as a slight reformulation (in terms of the scheme Z_{G}) of Conjecture 1.3.

Conjecture 4.4. For every graph G, the scheme of Z_{G} is countable.

Thus clearly Conjecture 4.4 (and thus Conjecture 1.3) is a special case of 1.2. As advertised in the introduction, we will show in Section 10 that they are actually equivalent.

5. Incidence Schemes

We now introduce the incidence schemes from the title of this paper. Here the remarks on the nature of this preliminary version given in the introduction are in full force. We, therefore, follow a slightly dubious method of defining schemes and maps between them.

Definition 5.1. Let r, k ∈ N, let W be a lattice and let G be a graph as in paragraph 4.1. We write A_{G}(W) (resp. A_{G}^{∗}(W)) for the closed subscheme of Bil(W) × Fun(V, W) consisting of pairs (Q, f) satisfying the following conditions (resp. satisfying (b)):

(a) ∑_{i=1}^{n} f(v_{i}) = 0,

(b) Q(f(v_{i}), f(v_{j})) = 0, e_{ij} ∉ E.

We then write A_{G}(W, r, k) (resp. A_{G}^{∗}(W, r, k)) for the locally closed subscheme of A_{G}(W) (resp. A_{G}^{∗}(W)) consisting of pairs (Q, f) ∈ Bil_{r}(W) × Fun_{k}(V, W). We write A_{G}(s, r, k) (resp. A_{G}^{∗}(s, r, k)) for A_{G}(Z^{s}, r, k) (resp. A_{G}^{∗}(Z^{s}, r, k)). We drop the G in the subscript when no confusion can result.

The A_{G}(W, r, k) (resp. A_{G}^{∗}(W, r, k)) form a stratification of A_{G}(W) (resp. A_{G}^{∗}(W)) by locally closed subschemes. We write A_{G}(W, r) (resp. A_{G}^{∗}(W, r)) for ⋃_{k} A_{G}(W, r, k) (resp. ⋃_{k} A_{G}^{∗}(W, r, k)).

The action of GL(W) on W gives rise an action on A_{G}(W, r, k) (resp. A_{G}^{∗}(W, r, k). Let T_{G} be the torus Fun(V, G_{m}). Then T_{G} acts on A^{∗}(W, r, k) by λ(Q, f) ↦ (Q, λf). We leave the verification of the following easy but important statement to the reader.

Claim 5.2. The map A_{G}^{∗}(s, r, k) → A_{G^{∗}}(s, r, k) sending (Q, f) to (Q, g) with g(v_{i}) = f(v_{i}) for i ∈ [1, n] and g(v_{0}) = − ∑_{i=1}^{n} f(v_{i}) is an isomorphism.

5.3. Note that A_{G}(s, r, k) = ∅ unless 0 ≤ k < n and 0 ≤ r, k ≤ s. Also note that A_{G}(s, r, 0) = Bil_{r}^{s}. There are several other important choices of s, r and k which are important enough to single out with special notation. To compactify the notation let m = n − 1 — a convention that we will also use later in the paper. We write

K_{G}(s) for A_{G}(s, s, s), K_{G}^{∗}(s) for A_{G}^{∗}(s, s, s),
J_{G}(s) for  A_{G}(s, s), J_{G}^{∗}(s) for A_{G}^{∗}(s, s),
H_{G}(s) for A_{G}(m, s, m), H_{G}^{∗}(s) for A_{G}^{∗}(n, s, n).

Remark 5.4. The idea of the notation is as follows: The K_{G}(s) (resp. the J_{G}(s) or the H_{G}(s)) will be seen in Section 7 to determine all other A_{G}(t, r, k). We believe that the J_{G}(s) are, however, the easiest to compute. And we do compute them in Section 9 for certain G. On the other hand, the H_{G}(s) enable induction from one graph to another. We single out the K_{G}(s) because they naturally come up in proofs as “building blocks” for all other A_{G}(s, r, k).

Note that the notation has been chosen so that, for example, H_{G^{∗}}(s) = H_{G}^{∗}(s). We keep this in all of our notation so that we can always move a ∗ superscript down by adding an apex to the graph in question.

Notice also that we have picked H_{G}^{∗}(s) to conform to the notation h(G, s) that Stanley gives in Section 5 of [Sta98]. In particular, for G a graph with an apex, [H_{G}^{∗}(s)] = [GL_{m}]h(G, s). We do not make use of this fact and leave its verification to the reader. Its proof is very similar to the proof of the next Theorem.

Theorem 5.5. (a) K_{G}(m) ≅ X′_{G} × GL_{m}.

(b) K_{G}(m) is countable if and only if X′_{G} is.

Proof. We first remark that (b) follows directly from (a), Theorem 3.1, and the countability of GL_{m}.

To prove (a) we let W = Z^{m} and view GL_{m} as the scheme of frames F on W. We have a map ψ : K(m) → X′_{G} × GL_{m} given by setting x_{ij} = −Q(f(v_{i}), f(v_{j})) for e_{ij} ∈ E and letting the frame F = (f(v_{1}), …, f(v_{m})).

Let (x, F) ∈ X_{G} × GL_{m} with F = (w_{1}, …, w_{m}). The inverse of ψ is the map ϕ which takes a pair (x, F) to the unique bilinear from determined by setting

Q(w_{i}, w_{j}) = \{ \begin{matrix}∑_{k=1}^{n} x_{ik} & i = j, \\ −x_{ij} & e_{ij} ∈ E \\ 0 & else, \end{matrix} f(v_{i}) = \{ \begin{matrix}w_{i} & i < n \\ − ∑_{k=1}^{m} w_{i} & i = n \end{matrix}

One must of course check that the ranges of ψ and ϕ are as advertised. This is done using The Matrix-Tree Theorem, and we leave this to the reader. It is then easy to check that ψ and ϕ are inverses.

Corollary 5.6. K_{G}^{∗} = Z_{G} × GL_{n}.

Proof. Since K_{G}^{∗} = K_{G^{∗}} and Z_{G} = X′_{G^{∗}}, the corollary follows from the theorem.

6. Reduction Formulae

In this section we give various formulae which allow us to reduce questions about A_{G}(s, r, k) (resp. A_{G}^{∗}(s, r, k)) for given s, r or k to questions where s, r or k is smaller. This allows us to set up inductions in favorable cases. We give the proofs and even the statements only for the A_{G}(s, r, k) leaving to the reader the trivial task of making the analogous statements for the A_{G}^{∗}(s, r, k) using the identity A_{G}^{∗}(s, r, k) = A_{G^{∗}}(s, r, k).

Let Q be a fixed bilinear form on F_{q}^{d_{1}} with rank r_{1}. Then let C_{Q}(d_{2}, r_{2}, d_{1}, r_{1}) be the number of ways to extend Q to a form on F_{q}^{d_{2}} of rank r_{2}. Stanley attributes the following theorem to MacWilliams [Mac69].

Theorem 6.1.

C_{Q}(d_{1} + 1, r_{2}, d_{1}, r_{1}) = \{ \begin{matrix}q^{r_{1}} & r_{2} = r_{1} \\ q^{r_{1}+1} − q^{r_{1}} & r_{2} = r_{1} + 1 \\ q^{d_{1}+1} − q^{r_{1}+1} & r_{2} = r_{1} + 2 \\ 0 & otherwise. \end{matrix}

We use the Theorem inductively to determine the C_{Q}(d_{2}, r_{2}, d_{1}, r_{1}) inductively using the fact that (for d_{2} > d_{1})

\begin{matrix}C_{Q}(d_{2}, & r_{2}, d_{1}, r_{1}) = \\ ∑_{j=0}^{2} C_{Q}(d_{2}, r_{2}, d_{1} + 1, r_{1} + j)C_{Q}(d_{1} + 1, r_{1} + j, d_{1}, r_{1}). \end{matrix} (6.1)

Corollary 6.2.

(a) C_{Q}(d_{2}, r_{2}, d_{1}, r_{1}) is a polynomial in q which is independent of Q. (We may therefore write C(d_{2}, r_{2}, d_{1}, r_{1}) leaving the Q out of our notation).

(b) C_{Q}(d_{2}, r_{2}, d_{1}, r_{1}) ≠ 0 iff d_{2} ≥ r_{2}, d_{1} ≥ r_{1}, and 0 ≤ r_{1} ≤ r_{2} ≤ r_{1} + 2(d_{2} − d_{1}).

Proof. (a) follows directly from the recursion formula 6.1.

The necessity of the first two inequalities of (b) are obvious for dimension reasons (the rank of a bilinear form can not be greater than the dimension of the ambient space). The third inequality follows from formula 6.1 by induction.

We prove the sufficiency of the the inequalities in (b) by induction on i = d_{2} − d_{1} using formula 6.1. We do not actually need this for the rest of the paper so the reader may safely skip the proof.

For i = 0 sufficiency is obvious. For i = 1 the sufficiency results from the fact that C(d_{1} + 1, r_{2}, d_{1}, r_{1}) = 0 iff r_{2} ∈ [r_{1}, r_{1} + 2] when d_{1} ≠ r_{1} and iff r_{2} ∈ [r_{1}, r_{1} + 1] when d_{1} = r_{1}.

Now suppose sufficiency is known for d_{2} − d_{1} < i and assume that (d_{2}, r_{2}, d_{1}, r_{1}) satisfies the conditions in (b) with d_{2} = d_{1} + i and r_{2} = r_{1} + k. By formula 6.1, C(d_{2}, r_{2}, d_{1}, r_{1}) ≠ 0 if there is a j such that both

1. C(d_{1} + i, r_{1} + k, d_{1} + 1, r_{1} + j) ≠ 0 and

2. C(d_{1} + 1, r_{1} + j, d_{1}, r_{1}) ≠ 0. One computes that (2) is satisfied whenever j ≤ d_{1} − r_{1} + 1. Using the the induction hypothesis, we see that (1) is satisfied for

k − 2i + 2 ≤ j ≤ min(k, d_{1} − r_{1} + 1).

So we need only show that k − 2i + 2 ≤ min(k, d_{1} − r_{1} + 1). That k − 2i + 2 ≤ k only says that i ≥ 1 which we are of course assuming. And k − 2i + 2 ≤ d_{1} − r_{1} + 1 iff (d_{2} − d_{1}) + (d_{2} − r_{2}) ≥ 1 which then follows from the fact that d_{2} ≥ r_{2}.

We are now ready to give our reduction theorems. We keep the notation of paragraph 4.1 and the convention that m = n − 1 and write A(s, r, k) for A_{G}(s, r, k).

Theorem 6.3.

[A(s, r, k)] = [Gr(k, s)] ∑_{j} C(s, r, k, j)[A(k, j, k)].

Proof. In this proof and the next one we will pick a base field F_{q} at the beginning and then, for any scheme X we encounter, write X instead of X(F_{q}).

Write W = F_{q}^{s}. For every map f ∈ W^{V} let ⟨f⟩ denote the span of the f(v_{i}). The map (Q, f) ↦ ⟨f⟩ fibers the set A(s, r, k) over the Gr(k, s). The fiber over a subspace U ⊂ W is then the set A(s, r, U) of (Q, f) ∈ A(s, r, k) such that ⟨f⟩ = U. The transitivity of the GL_{s} action on Gr(k, s) shows that the fibers all of the same number of points. Thus for any U

#A(s, r, k) = # Gr(k, s) · #A(s, r, U).  (6.2)

Now let A(s, r, U, j) be the set of (Q, f) ∈ A(s, r, U) such that Q|_{U} has rank j. This decomposes A(s, r, U) into disjoint subsets. Consider the map

p_{U} : A(s, r, U, j) → A(U, j, k) given by
(Q, f) ↦ (Q|_{U}, f).

The fiber of p_{U} above a given (\overline{Q}, f) ∈ A(U, j, k) is C\overline{Q}(s, r, k, j). Thus

#A(s, r, U, j) = C(s, r, k, j) · #A(k, j, k)  (6.3)

Summing over all the j in Equation 6.3 and substituting the result into Equation 6.2 we obtain the desired result.

Theorem 6.4. [A(s, r)] = q^{(s−r)m}[Gr(r, s)][J(r)].

Proof. Write W = F_{p}^{s} and let Ψ : A(W, r) → Gr(s − r, W) be the map associating to every (Q, f) the kernel ker Q of Q. The fiber of Ψ over a subspace U ⊂ W is the set A(W, r)_{U} consisting of all (Q, f) ∈ A(W, r) with Q|_{U} = 0. The transitivity of the action of GL(W) on Gr(s−r, W) show then that

#A(W, r) = #Gr(s − r, W) · #A(W, r)_{U}  (6.4)

Let T = W/U and let π : W → T be the quotient map. Q reduces in an obvious way to a form \overline{Q} on T. In fact Q ↦ \overline{Q} is a one-one correspondence between bilinear forms on W with kernel U and nondegenerate bilinear forms on T. We map p : A(W, r)_{U} → A(T, r) by sending (Q, f) to (\overline{Q}, π ∘ f). The fiber of p above a pair (\overline{Q}, g) ∈ A(T, r) is then identified with the set of f : V → W such that π ∘ f = g and ∑_{i=1}^{n} f(v_{i}) = 0. This is simply the affine translate by (any representative of) g of the vector space S of maps h : V → U satisfying ∑_{i=1}^{n} f(v_{i}) = 0. And S is isomorphic to U^{n−1} ≅ A^{(s−r)(n−1)}. Thus we find that

#A(W, r)_{U} = q^{(s−r)m} · #A(T, r)  (6.5)

As A(T, r) = A(r, r) = J(r), putting together the two fibrations gives the desired result.

7. Generators for the [A(s, r, k)]

Let Fun(Q, Z) denote the space of functions from the set of primary positive integers to Z. Let M be the subgroup of Fun(Q, Z) generated by the functions [X] for X a separated scheme of finite type over Z. Since [X × Y] = [X] × [Y], M is a subring of Fun(Q, Z). Note that Z[q] is a subring of M.

There is a natural map

ℜ : Q(q) ⊗_{Z[q]} Fun(Q, Z) → Ae(Q, Q)

defined by sending r ⊗ f to the almost everywhere defined function q ↦ r(q)f(q).

Proposition 7.1. ℜ restricted to Q(q) ⊗_{Z[q]} M is an inclusion. Thus Q(q) ⊗_{Z[q]} M is a subring of Ae(Q, Q).

Proof. Suppose that ∑(r_{i}/s) ⊗ [X_{i}] ∈ M ⊗_{Z[q]} Q(q) with r_{i}, s ∈ Z[q], and

∑ \frac{r_{i}(q)}{s(q)}[X_{i}](q) = 0

for almost all q. It follows that ∑ r_{i}(q)[X_{i}](q) = 0 for almost all q. Now for any r = ∑ a_{j}q^{j} ∈ Z[q] let

r^{≥} = ∑_{{i| a_{i}≥0}} a_{i}q^{i},
r^{<} = − ∑_{{i| a_{i}<0}} a_{i}q^{i}.

Thus r = r^{≥} − r^{<}. Now, for any t = ∑ a_{i}q^{i} with a_{i} ≥ 0, there is a scheme X(t) of finite type over Z such that [X(t)] = t. Thus, for any r, we have schemes X(r^{≥}) and X(r^{<}) such that r = [X(r^{≥})]−[X(r^{<})].

We have now that

∑ r_{i}^{≥}(q)[X_{i}](q) = ∑ r_{i}^{<}(q)[X_{i}](q)  (7.1)

for almost all q. Setting

X^{≥} = ∐ X(r_{i}^{≥}) × X_{i},
X^{<} = ∐ X(r_{i}^{<}) × X_{i},

it follows from Corollary 3.6 that [X^{≥}] = [X^{<}] and thus both sides of Equation 7.1 are equal. It then follows that ∑ r_{i} ⊗ [X_{i}] = 0 and, thus, that ∑(r_{i}/s) ⊗ [X_{i}] = 0.

For a graph G let M(G) be the Z[q] submodule of M generated by the [A_{G}(s, r, k)]. Let M(G)_{t} be the submodule of M(G) generated by the [A_{G}(s, r, k)] for s ≤ t. Theorem 6.3 shows that [A_{G}(s, r, k)] ∈ M(G)_{k}. Thus we have a finite filtration

M(G) = M(G)_{m} ⊃ M(G)_{m−1} ⊃ … ⊃ M(G)_{0} = Z[q]

In this section we show that the K_{G}(t) (resp. the J_{G}(t)) for t ≤ s span M(G)_{s}. We also show that the H_{G}(s) ∈ M(G)_{s} and then that the H_{G}(t) for t ≤ s span M(G)_{s} ⊗_{Z[q]} Q(q). Using this last fact we will show in section 8 that, if G has an apex, Conjecture 4.4 implies that M(G) = Z[q]. Thus for any graph Γ, A_{Γ}^{∗}(s, r, k) must be countable if Stanley’s conjecture holds.

Theorem 7.2. [A_{G}(s, r, k)] is in the Z[q]-module M̃ generated by the [K_{G}(t)] for t ≤ min{s, r, k}.

Proof. By induction, we can assume the result holds for s < s_{0}. (It obviously holds for s = 0). Theorem 6.3 shows that [A(s_{0}, r, k)] is in the Z[q]-module generated by the [A(k, j, k)]. By induction we can then assume that k = s_{0} and it suffices to prove the theorem for [A(k, j, k)]. And, of course, we assume that j < k as otherwise the theorem is a tautology.

But now [A(k, j, k)] = [A(k, j)] − ∑_{i=1}^{k−1}[A(k, j, i)]. By induction and and application of Theorem 6.3, the result holds for the [A(k, j, i)] since i < k = s_{0}. And by Theorem 6.4 [A(k, j)] is Z[q]-multiple of [A(j, j)]. That [A(j, j)] ∈ M̃ is then known by the inductive hypothesis. And this proves the theorem.

Corollary 7.3. (a) M(G)_{t} is generated by the [K_{G}(s)] for s ≤ t.

(b) [A(s, r, k)] ∈ M(G)_{t} for t = min{s, r, k}.

(c) [H_{G}(s)] ∈ M(G)_{s}.

Proof. (a) and (b) follow directly from Theorem 6.3 and (c) follows from (b).

Theorem 7.4.

(a) M(G)_{t} is generated by the [J_{G}(s)] for s ≤ t.

(b) [J_{G}(s)] ≡ [H_{G}(s)] mod M(G)_{s−1}.

Proof. (b) follows from the equation

[K(s)] = [J(s)] − ∑_{i=1}^{s−1}[A(s, s, i)]  (7.2)

and Corollary 7.3 part (b). (a) then follows by induction on s and Corollary 7.3 part (c).

Now we show that the [H_{G}(s)] span M(G) ⊗_{Z[q]} Q(q). We first wish to note a few computational facts.

Lemma 7.5. (a) C(s, r, k, r) = q^{r(s−k)}.

(b) [A(s, r, k)] ≡ [Gr(k, s)]q^{r(s−k)}[A(k, r, k)] mod M_{r−1}.

Proof. (a) is proved by induction using formula 6.1. For (b), write out [A(s, r, k)] using Theorem 6.3 and notice that all terms of the form C(s, r, k, j)[A(k, j, k)] for j ≠ r are in M_{r−1} by Theorem 7.2. Then use part (a) to compute the coefficient of A(k, r, k).

For p ∈ Z[q] let deg(p) be the degree of p as a polynomial in q. We make the convention that deg 0 = −∞. Theorem 6.4 says that [A(s, r)] = q^{m(s−r)}[Gr(r, s)][J(r)]. We write p(s, r) for q^{m(s−r)}[Gr(r, s)] and note that deg p(s, r) = m(s − r) + r(s − r) = (m + r)(s − r).

Lemma 7.6. For all s, r, k with s ≤ m, there is a polynomial p(s, r, k) ∈ Z[q] such that

(a) [A(s, r, k)] ≡ p(s, r, k)[J(r)] mod M_{r−1};

(b) deg p(s, r, k) < deg p(s, r) for s ≠ k;

(c) deg p(s, r, k) = deg p(s, r) for s = k.

Proof. Note first that the result is trivial unless k, r ≤ s as otherwise we can take p(s, r, k) = 0.

We prove all three statements simultaneously, reasoning by induction on s. The result is trivial when s = 0 as p(0, 0, 0) = 1. For a given s, we first assume that k < s. Then, by (b) of Lemma 7.5, A(s, r, k) ≡ Gr(k, s)q^{r(s−k)}A(k, r, k) mod M_{r−1}. Note that deg(Gr(k, s)q^{r(s−k)}) = (k+r)(s−k). By induction, A(k, r, k) ≡ p(k, r, k)J(r) mod M_{r−1} with deg p(k, r, k) = (m + r)(k − r). Thus A(s, r, k) ≡ p(s, r, k)J(r) with

deg(p(s, r, k)) = (m + r)(k − r) + (k + r)(s − k)
= (m + r)(s − r) − (m + r)(s − k) + (k + r)(s − k)
= (m + r)(s − r) − (m − k)(s − k)

This verifies the statement for k < s ≤ m.

For k = s, we then have (modulo M_{r−1})

[A(s, r, s)] ≡ [A(s, r)] − ∑_{k=1}^{s−1}[A(s, r, k)]

≡ p(s, r)[J(r)] − ∑_{k=0}^{s−1} p(s, r, k)[J(r)]

As deg(p(s, r)) = (m + r)(s − r) and deg p(s, r, k) < (m + r)(s − r) for k < s the result follows.

Theorem 7.7.

(a) The [H_{G}(t)] for t ≤ s generate M_{s} ⊗_{Z[q]} Q(q).

(b) If the H_{G}(t) are all countable then M(G) = Z[q].

Proof. Since the [J(t)] for t < s ≤ m generate M(G)_{s} (a) follows from Lemma 7.6. (b) then follows from Theorem 3.1.

8. Necessity

We now show that if Stembridge’s conjecture (a consequence of Kontsevich’s) is true then all A_{G}^{∗}(s, r, k) are countable for every G.

In this section and for the rest of the paper we will often consider several different graphs G simultaneously. To handle this notationally we make the following convention: For any graph G we now write n_{G} for |V (G)| and m_{G} for n_{G} − 1.

Lemma 8.1.

[A_{G^{∗}}^{∗}(s, r, k)] = q^{k}[A_{G}^{∗}(s, r, k)] + (q^{s} − q^{k−1})[A_{G}^{∗}(s, r, k − 1)].

Proof. Let W = F_{q}^{s}. Let f(V (G^{∗})) → W with ⟨f⟩ a k-dimensional subspace. The span of f|_{V (G)} is either a k or a k − 1 dimensional subspace. Counting the possibilities proves the lemma.

The following Lemma is a translation of Theorem 5.1 of [Sta98]

Lemma 8.2. For r ≤ n_{G},

[H_{G^{∗}}^{∗}(r)] = a_{G}(r)[H_{G}^{∗}(r)] + b_{G}(r)[H_{G}^{∗}(r − 1)] + c_{G}(r)[H_{G}^{∗}(r − 2)]

with

a_{G}(r) = q^{n_{G}+r}(q^{n_{G}+1} − 1)
b_{G}(r) = q^{n_{G}+r−1}(q^{n_{G}+1} − 1)(q − 1)
c_{G}(r) = q^{n_{G}}(q^{n_{G}+1} − 1)(q^{n_{G}} − q^{r−1})

all nonzero polynomials in q.

Proof. By the previous Lemma,

[H_{G^{∗}}^{∗}(r)] = (q^{n_{G}+1} − q^{n_{G}})[A_{G}^{∗}(n_{G} + 1, r, n_{G})].

Now applying Theorem 6.3 to [A_{G}^{∗}(n_{G} + 1, r, n_{G})] and expanding out [Gr(n_{G}, n_{G}+1)] in terms of q gives the result. One checks by inspection that a, b and c are nonzero.

For a graph G, define G(m) inductively by setting G(0) = G and G(m) = G(m − 1)^{∗}. Before stating the next theorem, we remind the reader that H_{G}(m_{G}) = K_{G}(m_{G}) ≅ GL_{m_{G}} ×X′_{G}. Thus [H_{G(i)}(m_{G}+i)] = [GL_{m_{G}+i}][X′_{G(i)}]

Lemma 8.3. If G = Γ^{∗} is a graph with an apex, then [J_{G(i)}(s)] = q^{is}[J_{G}(s)].

Proof. The statement will follow by induction on i once we prove that [J_{G^{∗}}(s)] = q^{s}[J_{G}(s)] or equivalently that [J_{Γ^{∗}}^{∗}(s)] = q^{s}[J_{Γ}^{∗}(s)]. Let Γ = {w_{1}, …, w_{m}} and G = {w_{0}, …, w_{n}}. Then we define a map ϕ : J_{G}^{∗}(s) → J_{Γ}^{∗}(s) by (Q, f) ↦ (Q, f|_{V (Γ)}). It is easy to see that the fiber of ϕ above any point in J_{Γ}^{∗}(s)(F_{q}) is precisely F_{q}^{s}.

Theorem 8.4. Let G = Γ^{∗} be a graph with an apex and let N(G) be the module over Q(q) generated by the [X_{G(i)}] for i ≥ 0. Then M(G) ⊗ Q(q) = N(G).

Proof. We first prove that M(G) ⊂ N(G). For this it suffices to prove the following statement: For any G with an apex and 0 ≤ i ≤ m_{G}, H_{G}(m_{G} − i) ∈ N(G).

The statement clear for i = 0. We prove it by induction on i. Assume then that it holds for i < j. Then set r = m_{G(1)} − (j − 1). By the induction hypothesis, H_{G(1)}(r) ∈ N(G(1)) ⊂ N(G).

But then by Lemma 8.2

H_{G(1)}(r) = a_{Γ}(r)H_{G}(m_{G} − (j − 2))  (8.1)
+ b_{Γ}(r)H_{G}(m_{G} − (j − 1)) + c_{Γ}(r)H_{G}(m_{G} − j).

Thus both sides of equation 8.1 are in N(G). But the first two terms on the right hand side are also in N(G) by induction. Since c(r) is a nonzero polynomial, it follows that H_{G}(m_{G} − j) ∈ N(G) and this proves that M(G) ⊗_{Z[q]} Q(q) ⊂ N(G).

To show that N(G) ⊂ M(G) we remark that each M(G) contains all of the J_{G}(s) and, thus, by Lemma 8.3 it contains all of the J_{G(i)}(s). Thus by Theorem 7.4 it contains M(G(i)) for all i. And thus it contains X_{G(i)} for all i.

Corollary 8.5. Let G be as in Theorem 8.4. Then, for any i ≥ 0, N(G(i)) = M(G) ⊗_{Z[q]} Q(q).

Proof. Lemma 8.3 in fact shows that, for G with an apex, M(G(i)) ⊗ Q(q) = M(G) ⊗ Q(q) for any i. Thus M(G) ⊗_{Z[q]} Q(q) = M(G(i)) = N(G(i)).

Corollary 8.6. Stembridge’s conjecture implies that all A_{G}^{∗}(s, r, k) are countable.

Proof. By Theorem 8.4, Stembridge’s conjecture implies that N(G^{∗}) = Z[q] for any graph G. Thus the A_{G}^{∗}(s, r, k) = A_{G^{∗}}(s, r, k) are all countable.

9. Complements of Complete Graphs

Every graph G is contained in a natural way in the complete graph K_{V (G)} = K_{n_{G}}. We let G^{o} denote the graph K_{n_{G}} − G. Note that G^{o}(i) = K_{n_{G}+i} − G.

Now J_{G^{o}}^{∗}(s)(F_{q}) is the set of all (Q, f) ∈ Bil_{s}(F^{s}) × Fun(V, F^{s}) such that Q(f(v_{i}), f(v_{j})) = 0 for e_{ij} ∈ E(G). To simplify the notation, we write P (G, s) for J_{G^{o}}^{∗}(s).

Theorem 9.1. If the P (G, s) are countable for 0 ≤ s ≤ n_{G} then

(a) M(G^{o∗}) = Z[q].

(b) For every n > n_{G}, X_{K_{n}−G} is countable.

Proof. (a): The hypothesis is that the J_{G^{o}}^{∗}(s) = J_{G^{o∗}}(s) are countable for 0 ≤ s ≤ n_{G}. It then follows from Theorem 7.4 that M(G^{o∗}) is countable. (b) now follows from (a), Theorem 8.4 and Theorem 3.1.

We are now going to prove that the P (G, s) are countable whenever G is a forest. To do so we need to introduce a few operations on graphs.

Let v ∈ V (G). We obtain a graph I_{v}(G) by adding one edge e connected to v and one new vertex w connected to e. Ie, we insert an edge at v. Clearly, a graph is tree if and only if it can be obtained from the graph with one vertex by successive applications of I_{v} for various v.

We define D(G) to be the graph obtained from G by simply adding a vertex w disjoint from V (G) and letting E(D(G)) = E(G). A graph is a forest if and only if it can be obtained from the empty graph ∅ by successive applications of D and I_{v}. We write D_{n} for D^{n}∅ — the graph with n disjoint vertices.

Lastly, we define R_{v} to be the graph obtained from G by deleting v and all edges meeting it. We mention that if G is a forest and v is any vertex in G, R_{v}G will always be a forest.

Theorem 9.2. Let G be a graph with v ∈ V (G).

(a) [P (D_{n}, s)] = q^{ns}[Bil_{s}^{s}].

(b) [P (DG, s)] = q^{s}P (G, s).

(c) [P (I_{v}, s)] = q^{s−1} (P (G, s) + (q − 1)P (R_{v}G, s))

Proof. For (b) let w be the vertex in V (DG) − V (G). Then the map P (DG, s) → P (G, s) × F_{q}^{s} given by (Q, f) ↦ (Q, f|_{V (G)}, f(w)) is an isomorphism. For (a) assume first that n = 0. Then tracing through the definitions one sees that P (∅, s) = Bil_{s}^{s}. The rest of (a) follows by induction from (b).

For (c) we work over F_{q} and consider the map π : P (I_{v}(G), s) → P (G, s) given by (Q, f) ↦ (Q, f|_{V (G)}). The fiber of π above a point (Q, g) ∈ P (G, s) depends on whether g(v) is 0 or not. Let P^{0}(G, s) (resp. P^{×}(G, s)) be the set where g(v) = 0 (resp. g(v) ≠ 0). Above a point (Q, g) ∈ P^{0}(G, s) the fiber of π will have q^{s} points. Above a point (Q, g) ∈ P^{×}(G, s) the fiber will have q^{s−1} points since Q is non-degenerate. Thus

|P (I_{v}(G), s)| = q^{s−1}|P^{×}(G, s)| + q^{s}|P^{0}(G, s)|  (9.1)

The result now follows from the observation that

|P^{0}(G, s)| = |P (R_{v}(G, s))|.

The next corollary follows directly from Theorem 9.1 and Theorem 9.2.

Corollary 9.3. Let F be a forest with r vertices contained in a complete graph K_{s} with s > r. Let G = K_{s} − F. Then X_{G} is countable.

10. Stembridge’s Conjecture

Remark 10.1 (Guide for the next section). This paper developed out of an attempt to prove Kontsevich’s conjecture. In the process, we found a proof that Stembridge’s conjecture implied Stanley’s. To us, this was an important step because Stembridge’s conjecture seemed more natural then Stanley’s in terms of our incidence schemes.

However, the same methods that we used to show that Stembridge’s conjecture implied Stanley’s eventually led us to a counterexample to all three conjectures.

In this section, we present the proof that Stembridge’s conjecture if it were true would imply Stanley’s. And in the next section we present the proof that, in fact, Stembridge’s conjecture itself is false. This may seem unnecessary, and, of course, logically speaking it is. But the methods used in this section are still interesting for the study of weaker versions of Kontsevich’s conjecture. And they play a large role in the counterexample of the next section. That is why we have decided to reproduce this proof intact for this MPI preprint.

As mentioned in the section 4, Conjecture 4.4 is a special case of Conjecture 1.2. The goal is to show that Conjecture 4.4 actually implies Conjecture 1.2. In other words, we will prove the following Theorem 10.2. Stanley’s conjecture is true if and only if it is true for all graphs with apexes.

Since Conjecture 1.2 is equivalent to Conjecture 1.1, this will show that actually that all three conjectures are equivalent. We warn the reader though that we do not show that the truth of Conjecture 4.4 for a particular graph G implies the truth of Conjecture 1.2 for that same graph. Rather we must assume the truth of Conjecture 4.4 for a set of graphs related to G to assure that Conjecture 1.2 is true for G.

In this section we will more or less abuse notation and define our various schemes by giving their F points for F a field.

Let V = V (G) = {v_{1}, …, v_{n}} and let m = n − 1. Our basic tool is the map

K^{∗}(m) →^{ϕ} P^{m−1}
(Q, f) ↦ {α ∈ F^{m}| ∑ α_{i}f(v_{i}) = 0}

Let T_{G} = G_{m}^{V}. Then ϕ is T_{G} equivariant provided the action of T_{G} on P^{m−1} is chosen appropriately. The orbits of T_{G} on P^{m−1} are in 1−1 correspondence with subsets ∅ ≠ H ⊂ V (G) with the correspondence sending H to the orbit of the characteristic function χ_{H} seen as an element of F^{n}. The orbit stabilizer is G_{m}T_{G−H} with the first G_{m} factor acting diagonally. Thus the orbit is isomorphic to G_{m}^{|H|−1}. Hence

[K^{∗}(m)] = ∑_{∅≠H⊂V (G)}[G_{m}]^{|H|−1}[ϕ^{−1}(χ_{H})].

Now ϕ^{−1}χ_{H} = {(Q, f) ∈ K^{∗}(m)| ∑_{v_{i}∈H} f(v_{i}) = 0}. In particular, ϕ^{−1}χ_{V} = K(m). Thus to prove Theorem 10.2 it suffices to show that the ϕ^{−1}(χ_{H}) are all countable for H ⫋ V (G). We will actually show that ϕ^{−1}(χ_{H}) is countable for all H ⊂ V (G) (including V (G) itself). But we will do this by induction on the H.

Let

K_{G}^{H}(m) = \{(Q, f) ∈ K_{G}^{∗}(m) | \begin{matrix}∃α : H → F^{×} s.t. \\ ∑ α(v)f(v) = 0, \end{matrix} \}
\overline{K}_{G}^{H}(m) = \{(Q, f) ∈ K_{G}^{∗}(m) | \begin{matrix}∃α : H → F s.t. \\ ∑ α(v)f(v) = 0, α ≠ 0 \end{matrix} \}

We remark that K_{G}^{H}(m) is the T_{G} orbit of ϕ^{−1}(χ_{H}).

Proposition 10.3. The following are equivalent:

(a) For all H, ϕ^{−1}(χ_{H}) is countable.

(b) For all H, K^{H}(m) is countable.

(c) For all H, K̄^{H}(m) is countable.

Proof. The first equivalence follows from the fact that [K^{H}(m)] = [G_{m}^{|H|−1}][ϕ^{−1}(χ_{H})]. (It is thus unnecessary to quantify over all H in this statement). (b)⇒(c) follows from the equality \overline{K}^{H}(m) = ∐_{J⊂H} K^{J}. This equality also implies that [K^{H}] = [\overline{K}^{H}] − ∑_{J⫋H}[K^{J}]. Thus to prove (c)⇒(b) it suffices to know (c)⇒(b) for J ⫋ H. As K^{H}(m) = \overline{K}^{H}(m) when H has one element, this follows by induction.

Our strategy now is to show that Stembridge’s conjecture implies that the \overline{K}_{G}^{H}(m) are countable for arbitrary graphs G. Recall that Stembridge’s conjecture implies that for any G the A_{G}^{∗}(s, r, k) are all countable (Corollary 8.6).

Keeping H fixed, we let J(k, a, b) be the variety of all (Q, f) ∈ J_{G}^{∗}(k) such that

1. dim⟨f(V)⟩ = a,

2. dim⟨f(H)⟩ = b.

Note then that J(m, m, |H|−1) = \overline{K}^{H}(m). Note also that J(k, a, b) = ∅ unless 0 ≤ b ≤ a ≤ k.

Under the assumption that Conjecture 1.2 is true, we will now prove that all J(k, a, b) are countable.

Let G(r, s) be the graph obtained by adjoining r + s vertices S = {x_{1}, …, x_{r}, y_{1}, …, y_{s}} all joined to each other (by an edge) such that the x_{i} are joined to no vertices in G and such that the second y_{i} are joined to all vertices in G that are not in H. Let X = {x_{1}, …, x_{r}}.

Suppose C ⊃ D are two F-vector spaces of ranks c and d respectively. Write M(r, s, C, D) for the number of maps ϕ : S → C such that ϕ(X) ⊂ D. From equation 2.1, we know that M(r, s, C, D) = q^{(rd+sc)}.

Proposition 10.4.

[J_{G(r,s)}^{∗}(k)] = ∑_{0≤i≤j≤k} q^{ri+sj}[J(k, k − i, k − j)]  (10.1)

Proof. To simplify the notation for the proof we write Z(i, j) for the set of (Q, f) ∈ J_{G(r,s)}^{∗}(k) such that dim⟨f(V (G))⟩ = k−i and dim⟨f(H)⟩ = k − j. Also, for Q ∈ Bil(F^{k}) and C ⊂ F^{k}, we write C^{⊥Q} for the space perpendicular to C under the Q.

We then have a map

Z(i, j) →^{π} J(k, k − i, k − j)
(Q, f) ↦ (Q, f|_{V (G)})

Suppose (Q, g) ∈ J(k, k−i, k−j). Then π^{−1}(Q, g) consists of the set of all (Q, f) where f is an arbitrary element of Fun(V (G) ∐ S, F^{k}) such that f|_{V (G)} = g, f(X) ∈ g(V (G))^{⊥Q} and f(S) ∈ g(H)^{⊥Q}. It follows that, for F = F_{q}

|π^{−1}(Q, g)| = M(r, s, g(H)^{⊥Q}, g(V (G))^{⊥Q})
= q^{ri+sj}.

Summing over the Z(i, j) finishes the proof.

Assuming Stembridge’s conjecture is true, all J_{G(r,s)}^{∗}(k) are countable. This follows from Corollary 8.6. Thus to show that the J(k, a, b) are countable it will suffice to know that as r and s vary the equations we get from 10.1 determine the J(k, k − i, k − j). Since J(k, k − i, k − j) is a variety it will then be forced to be countable by Theorem 3.1. That the equations from 10.1 are determined follows from the following.

Lemma 10.5. Let S_{N} = {0, …, N − 1}^{2}. For every x ∈ S_{N}, let f_{x} : S_{N} → Q(q) be the function given by f_{x}(y) = q^{x·y} (where x · y is the standard inner product). Then the functions f_{x} as x ranges through S_{N} form a basis for the space of functions F_{N} from S_{N} to Q(q).

Proof. We define a map h : Q[q] → C by sending q to e^{2πi/N}. Set ker h = I. Set E_{N} = Fun(S_{N}, Q[q]). Then E_{N} ⊗_{Q[q]} C = Fun(S_{N}, C). Write this tensor product as E_{NC}. We put a non-degenerate Hermitian inner product on E_{NC} by setting

< f, g >= \frac{1}{N^{2}} ∑_{z∈S_{N}} f(z)\overline{g(z)}  (10.2)

where we think of f and g as functions from S_{N} to C. It is easy to see that under this inner product the h(f_{x}) form an orthonormal basis as x ranges through S_{N}.

Let M_{N} be the Q[q] module generated by the f_{x} as x ranges through S_{N}. We then have that E_{N} = M_{N} + IE_{N}. It then follows from Nakayama’s lemma that M_{N} ⊗_{Z[q]} Q(q) = E_{N} ⊗_{Z[q]} Q(q). Since the dimension of F_{N} is N^{2} which is precisely equal to the number of f_{x} as x runs through S_{N}, this proves the lemma.

Theorem 10.6. Under the assumption that Stembridge’s conjecture holds, all J(k, k − i, k − j) are countable for any graph G and any subgraph H.

Proof. Since the set of i and j such that 0 ≤ i ≤ j ≤ k is contained in S_{k+1}. The equations in 10.1 for (r, s) ∈ S_{k+1} suffice by lemma 10.5 to determine the J(k, k − i, k − j).

Since J(m, m, |H| − 1) = \overline{K}^{H}(m) Theorem 10.2 now follows from Proposition 10.3 and the fact that K_{G}(m) = K_{G}^{V (G)}(m).

11. Bipartite Graphs and Counterexample to Kontsevich’s Conjecture and all related conjectures

We want to nail down the counterexample. The approach below is the shortest route to present the counterexample. This may not be the best thing to do, because there are actual theorems hidden here (Motives of complements of Bipartite graphs “=” motives of matroids). Also the hypotheses may not be minimal.

We assume that Stanley’s conjecture is true is true for all Graphs. First we generalize theorem 10.5. Let G be a graph, V the set of its vertices, U the set of subsets of

V. For π a function U ↦ Z, define

Definition 11.1. J(k, π) to be the variety of all (Q, f) ∈ J_{G}^{∗}(k) such that

dim⟨f(H)⟩ = π(H), for all H ∈ U.

More generally if W is a subset of U, For π a function W ↦ Z, define

Definition 11.2. J(k, W, π) to be the variety of all (Q, f) ∈ J_{G}^{∗}(k) such that

dim⟨f(H)⟩ = π(H), for all H ∈ W.

This generalizes the varieties of section 10, Using the same ideas we will show that

Theorem 11.3. Under the assumption that Stembridge’s conjecture holds, all J(k, W, π) are countable for any graph G, any subset W of U and any function π : W ↦ Z.

Proof. Induct on the number of elements in W.

If W is empty, the result is clear (taking into account theorems of section 8) Now suppose W′ = W ⋃{H}. Note that W has one fewer element than W′ . We can write for π : W ↦ Z.

[J_{G(0,s)}(k, W, π)] = ∑_{0≤i≤k} q^{si}[J(k, W′, π_{i})]  (11.1)

where π_{i} : W′ ↦ Z. is defined to be π on W and k − i on the subset H.

The proof is similar to a similar equation in 10.5. We can break up [J_{G(0,s)}(k, W, π)] into pieces where the rank of the vectors in H is k − i, the s added vectors are forced to lie in the space orthogonal to the subspace spanned by H, and hence a space of dimension i and hence q^{is} possibilities of choosing the s new vectors.

Now consideration of the Vandermonde determinant, completes the proof by induction. To elaborate this point imagine that we are trying to solve for [J(k, W′, π_{i})] in terms of [J_{G(0,s)}(k, W, π)] using the above equations for s = 0 till s = k. Then by Cramer’s rule this can be solved if the determinant of the matrix whose (i, j)th entry is q^{ij}. That is, the ith row is just powers of q^{i}. This is exactly the Vandermonde determinant and is nonzero since different powers of q do not coincide.

Let G be a complete graph, in this case it is easy to see that if π a function U ↦ Z, then

[J(k, π)] = [Q(k)][L(k, π)] where

1. Q(k) =variety of nondegenerate symmetric bilinear forms on a k dimensional space, by results quoted earlier this is countable.

2. L(k, π) =variety of f ∈ F un(V, F_{q}^{k}) so that dim⟨f(H)⟩ = π(H), for all H ∈ U.

(Looking at the definition of J(k, π) makes it clear that Q does not enter in the definition of the J’s for the complete graph.) Also note that only the vertex set V is needed for the definition of the L’s.

Therefore it is easy to see that Stembridge’s conjecture implies that the L’s are countable. But examples of L’s which are not countable are available from the theory of matroids. These can be found in Chapter 9 of [Wel76]. Instead of defining a matroid, we describe the L which is not countable. This is called the Fano Matroid. Let V = {1, 2, 3, 4, 5, 6, 7} ,k = 3. W = U, and to define π,

1. If card(H)=1, then π(H) = 1.

2. If Card(H)=2 then π(H) = 2.

3. If Card(H)=3 then π(H) = 3 UNLESS π = {1, 2, 6} or π = {1, 4, 7}or π = {1, 3, 5} or π = {2, 3, 4} or π = {2, 5, 7} or π = {3, 6, 7} or π = {4, 5, 6}. In the 7 cases above define π to equal 2.

4. If Card(H) = i where i > 3 then define π(H) = 3.

It is shown (and not difficult, uses simple projective geometry), that L has no points over fields of characteristic ≠ 2, and has points over every field of Characteristic 2. If it were countable then looking at the prime 2 we see that this polynomial is non zero, and hence non zero for every sufficiently large prime, but it has no points over fields of characteristic p for p ≠ 2. Contradiction.

We also add that the “pathology” can be arranged to occur over any prime.

References

[Dwo60] B.M. Dwork. On the rationality of the zeta function of an algebraic variety. Amer. J. Math., 82:631–648, 1960.

[GD67] A. Grothendiek and J. Dieudonné. Éléments de géométrie algébrique. Inst. Hautes Études Sci., (4, 8, 11, 17, 20, 24, 28, 32), 1960-1967.

[Mac69] J. MacWilliams. Orthogonal matrices over finite fields. Amer. Math. Monthly, 76:152–164, 1969.

[Sta98] R. Stanley. Spanning trees and a conjecture of Kontsevich. Annals of Combinatorics, 2:351–363, 1998.

[Ste98] J. Stembridge. Counting points on varieties over finite fields related to a conjecture of Kontsevich. Annals of Combinatorics, 2:365–385, 1998.

[Wel76] D.J.A. Welsh. Matroid Theory. Academic Press, 1976.

Department of Mathematics, University of Utah, 155 South 1400 East, JWB 233, Salt Lake City, Utah 84112-0090, USA

  E-mail address: belkale@math.utah.edu

Max-Planck-Institut für Mathematik, Vivatsgasse 7, D-53111 Bonn, Germany

  E-mail address: pbrosnan@mpim-bonn.mpg.de