Coefficient Positivity for Arborescence Ratios of Covering Digraphs

Source abstract

For a directed graph with a chosen root, the arborescence polynomial sums the products of edge weights over all spanning trees directed toward that root. In a finite graph cover, each lifted edge inherits the variable of its base edge. At corresponding roots, the ratio of the cover's arborescence polynomial to the base polynomial is known to be an integer polynomial. We prove that every coefficient of this ratio is nonnegative, resolving the positivity conjecture of Pylyavskyy. The key to the proof is to allow fibers of unequal size and replace the permutations defining a cover by arbitrary maps. For these more general systems, we prove a stronger coefficient-positivity theorem for a determinant derived from the graph Laplacian. The enlarged class is closed under two reductions: contraction of an edge over a base loop and elimination of a base vertex. Both yield nonnegative recurrences for the relevant coefficients in terms of smaller systems, allowing an inductive proof. We also pose the problem of finding a direct combinatorial interpretation of the coefficients.