Spanning-tree formula conjecture for the Fitting ideal of a graph

The spanning-tree formula for the Fitting ideal

Let $\Bbbk$ be an algebraically closed field of characteristic zero, and let $\Gamma$ be a connected simple graph on $[n]$, where $n\ge 3$. Write $E$ for its edge set, $F$ for its nonedge set, and $r=|F|$. Suppose $r\ge n-2$, and put

$$S=\Bbbk[x_1,\ldots,x_n],\qquad \mathfrak m=(x_1,\ldots,x_n).$$

Write $\mathcal T(\Gamma)$ for the set of spanning trees of $\Gamma$. For $T\in\mathcal T(\Gamma)$, define

$$m_T=\prod_{i=1}^n x_i^{\deg_T(i)-1}, \qquad I_{\mathcal T}(\Gamma)=(m_T:T\text{ a spanning tree of }\Gamma).$$

We prove Spiridon's Conjecture 3.21:

$$\operatorname{Fitt}_0(W_\Gamma) =I_{\mathcal T}(\Gamma)\,\mathfrak m^{\,r-n+2}. \tag{1}$$

The proof uses Cauchy–Binet and the classical spanning-tree minors of an incidence matrix. The key observation is that every maximal minor of the presentation matrix is a scalar times one monomial. Consequently, a determinant identity with nonnegative integer coefficients determines the whole Fitting ideal, not merely its zero set.

1. The presentation minors are monomials

The presentation of $W_\Gamma$ in the source has one row for each nonedge and one column for each triple. More explicitly, let $e_1,\ldots,e_n$ be the standard basis of $\Bbbk^n$, and let $K$ be the span of $e_i\wedge e_j$ for $\{i,j\}\in E$. Then $W_\Gamma$ is the cokernel of the map

$$\bigwedge^3\Bbbk^n\otimes S(-1) \longrightarrow (\bigwedge^2\Bbbk^n/K)\otimes S$$

which sends, for $i<j<k$,

$$e_i\wedge e_j\wedge e_k \longmapsto x_i e_j\wedge e_k-x_j e_i\wedge e_k+x_k e_i\wedge e_j \pmod K.$$

Call this $r$-row matrix $\Theta$. Its $r\times r$ minors generate $\operatorname{Fitt}_0(W_\Gamma)$.

All its entries have integer coefficients, so we first work over $\mathbb Q[x_1,\ldots,x_n]$. Let $C$ be the constant matrix obtained by replacing each nonzero entry of $\Theta$ by its sign. In the Laurent polynomial ring, let $D_F$ and $D_3$ be diagonal matrices with entries $x_i x_j$ for nonedges and $x_i x_j x_k$ for triples, respectively. Then

$$\Theta=D_F^{-1}CD_3.$$

For any set $A$ of $r$ triple-columns, the corresponding maximal minor is therefore

$$\Delta_A =\det(C_A)\, \frac{\displaystyle\prod_{\{i,j,k\}\in A}x_i x_j x_k} {\displaystyle\prod_{\{i,j\}\in F}x_i x_j}. \tag{2}$$

If $\det(C_A)\ne0$, the exponents on the right are nonnegative, since the left side is a polynomial. Thus every nonzero $\Delta_A$ is a nonzero integer times a monomial of degree $r$.

2. A Gram determinant identity

Put

$$x=(x_1,\ldots,x_n)^{\mathsf T},\qquad s=x_1^2+\cdots+x_n^2.$$

For any pair $i<j$, define the column vector

$$b_{ij}=x_j e_i-x_i e_j.$$

Let $B_E$ and $B_F$ consist of these columns for edges and nonedges, respectively. Direct multiplication gives

$$\begin{aligned} B_EB_E^{\mathsf T}+B_FB_F^{\mathsf T} &=sI_n-xx^{\mathsf T},\\ \Theta\Theta^{\mathsf T} &=sI_r-B_F^{\mathsf T}B_F. \end{aligned} \tag{3}$$

For example, the diagonal entry of the second identity at the nonedge $\{i,j\}$ is $\sum_{k\ne i,j}x_k^2$ on both sides. Entries at disjoint nonedges vanish; entries at two nonedges sharing a vertex agree with the signs in the displayed presentation.

Sylvester's determinant identity, applied over $\mathbb Q(x_1,\ldots,x_n)$, now yields

$$\begin{aligned} \det(\Theta\Theta^{\mathsf T}) &=s^{r-n}\det(sI_n-B_FB_F^{\mathsf T})\\ &=s^{r-n}\det(B_EB_E^{\mathsf T}+xx^{\mathsf T}). \end{aligned} \tag{4}$$

The intermediate exponent $r-n$ may be negative; this calculation takes place in the rational function field.

We next compute the last determinant. For an edge set $A$, let $N_A$ denote its ordinary oriented incidence matrix, with column $e_i-e_j$ for $i<j$, and let $B_A$ contain the corresponding columns $b_{ij}$. Then

$$B_A=\operatorname{diag}(x_i^{-1})\, N_A\,\operatorname{diag}(x_i x_j)_{\{i,j\}\in A}. \tag{5}$$

Deleting any row from the incidence matrix of a spanning tree gives determinant $\pm1$, as follows by successive leaf removal. Its signed maximal cofactors are all equal: their vector lies in the left kernel, which is spanned by the all-ones vector. Consequently, for each spanning tree $T$ and any column $y$,

$$\det[\,N_T\mid y\,]=\varepsilon_T\sum_{i=1}^n y_i, \qquad \varepsilon_T\in\{1,-1\}.$$

Using (5) and taking $y_i=x_i^2$, we obtain

$$\begin{aligned} \det[\,B_T\mid x\,] &=\frac{\prod_{\{i,j\}\in T}x_i x_j}{\prod_i x_i} \det[\,N_T\mid (x_i^2)_i\,]\\ &=\varepsilon_T\,s\,m_T. \end{aligned} \tag{6}$$

Apply Cauchy–Binet to the matrix $[\,B_E\mid x\,]$. A selection of $n$ columns not containing $x$ has zero determinant because $x^{\mathsf T}B_E=0$. A selection containing $x$ and $n-1$ edge columns also has zero determinant unless those edges form a spanning tree: otherwise their incidence matrix has rank at most $n-2$. Hence (6) gives

$$\det(B_EB_E^{\mathsf T}+xx^{\mathsf T}) =s^2\sum_{T\in\mathcal T(\Gamma)}m_T^2. \tag{7}$$

Combining (4) and (7) proves the polynomial identity

$$\det(\Theta\Theta^{\mathsf T}) =s^{r-n+2}\sum_{T\in\mathcal T(\Gamma)}m_T^2. \tag{8}$$

Here $r-n+2\ge0$ by hypothesis, so the right side is indeed a polynomial.

3. Recovering the ideal from the determinant

Write $h=r-n+2$. Cauchy–Binet applied to $\Theta$ gives

$$\sum_A\Delta_A^2 =(x_1^2+\cdots+x_n^2)^h \sum_{T\in\mathcal T(\Gamma)}m_T^2. \tag{9}$$

By (2), the left side is a sum of squares of integer multiples of monomials. Its monomials therefore occur with positive integer coefficients, with no cancellation. The right side likewise has positive integer coefficients, and its monomials are exactly

$$(m_Tx^\alpha)^2, \qquad T\in\mathcal T(\Gamma),\quad \alpha\in\mathbb Z_{\ge0}^n,\quad |\alpha|=h,$$

where $x^\alpha=\prod_i x_i^{\alpha_i}$ and $|\alpha|=\sum_i\alpha_i$. Since squaring is injective on monomials, equality in (9) says that the monomials occurring in the nonzero maximal minors are precisely the monomials $m_Tx^\alpha$ with $|\alpha|=h$. These generate $I_{\mathcal T}(\Gamma)\mathfrak m^h$, proving (1) over $\mathbb Q$.

Finally, every nonzero integer coefficient of a minor remains nonzero, and hence invertible, in any characteristic-zero field. The same monomial generators therefore give (1) over $\Bbbk$. The argument includes $r=n-2$, when $h=0$, and the smallest allowed case $n=3$. Thus it covers every graph and parameter range in Conjecture 3.21.