Coefficient Positivity for Arborescence Ratios of Covering Digraphs
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.
Related
- On (p,q)-binomial coefficient ratios for complex parameters
- A finite cover for coefficient positivity of stretched Littlewood-Richardson polynomials in the seven-row, size-thirty box
- CLT for the Weight of the Minimum Spanning Arborescence on the Complete Directed Graph
- Highly connected uniquely k-linked digraphs
- s-quasi-transitive weakly distance-regular digraphs
BibTeX
@misc{ju2026coefficient,
title = {{Coefficient Positivity for Arborescence Ratios of Covering Digraphs}},
author = {Muchen Ju and Junjie Ni and Kaixin Wang and Yihan Xiao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.31980},
eprint = {2610.31980},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.31980},
}
RIS
TY - UNPB
TI - Coefficient Positivity for Arborescence Ratios of Covering Digraphs
AU - Muchen Ju
AU - Junjie Ni
AU - Kaixin Wang
AU - Yihan Xiao
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.31980
UR - https://arxiv.org/abs/2610.31980
AB - 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.
ER -