Paperlane

no. 2 · Monday 26 October 2026

Coefficient Positivity for Arborescence Ratios of Covering Digraphs

Muchen Ju, Junjie Ni, Kaixin Wang and Yihan Xiao

math.CO · code · ∎ lean builds · 16 pp

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.

code
github.com/muchenju-math/positivity-lean ∎ Lean project (lakefile.lean, lean-toolchain) builds, no sorry at 6511eea, checked 2026-10-27 build details
comments
16 pages, 5 figures. Lean formalization: https://github.com/muchenju-math/positivity-lean
fields
Combinatorics
pdf ↗ page arXiv:2610.31980 ↗