Modulating flow polynomials and parity bias in homological walk counting
Abstract
Long weighted walks seem to sample mod-t flows uniformly, but at even moduli a persistent parity bias survives. Writing CG(t) for the flow polynomial of a connected graph G of genus g, the proportion of nowhere-zero flows under uniform sampling is CG(t)/tg. For arbitrary positive directed weights and all moduli, we determine the exact leading corrections for both closed walks and nonbacktracking closed walks, which we call circuits. Only the circuit result requires g≥2. For closed walks, the canonical character governs the leading correction through the canonical modulating flow polynomial DG; for circuits, the period character, when it exists, governs the leading correction through the period modulating flow polynomial DG,η. At even moduli these give parity-dependent corrections: the two mechanisms coincide on nonbipartite graphs and separate only in the bipartite circuit problem. More generally, each integral-homology character ζ determines a balanced-dichromatic specialization DG,ζ. These polynomials form a character-indexed family whose finite-order members give Fourier coefficients of the nowhere-zero flow set and whose retained edge sets are the central sets of a gain semimatroid. We further show that DG is a cycle-matroid invariant and a signed-Tutte specialization satisfying signed deletion-contraction. Finally, an integral nowhere-zero approximation theorem implies that asymptotically almost every weighted circuit traverses every edge.
Related
- Low-Density Parity-Check Codes of High Girth from Permutation Polynomials
- Counting irreducible skew polynomials x2n+axn+1
- Counting k-tuples of positive integers such that the values of several polynomials of k variables are relatively prime
- Galois groups of polynomials over a fixed number field: determinant methods in general boxes, resolvents, and quantitative counting
- Real-rooted flow polynomials have only integral roots
BibTeX
@misc{luo2026modulating,
title = {{Modulating flow polynomials and parity bias in homological walk counting}},
author = {Ye Luo},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29773},
eprint = {2610.29773},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29773},
}
RIS
TY - UNPB
TI - Modulating flow polynomials and parity bias in homological walk counting
AU - Ye Luo
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29773
UR - https://arxiv.org/abs/2610.29773
AB - Long weighted walks seem to sample mod-t flows uniformly, but at even moduli a persistent parity bias survives. Writing C_G(t) for the flow polynomial of a connected graph G of genus g, the proportion of nowhere-zero flows under uniform sampling is C_G(t)/t^g. For arbitrary positive directed weights and all moduli, we determine the exact leading corrections for both closed walks and nonbacktracking closed walks, which we call circuits. Only the circuit result requires g≥2. For closed walks, the canonical character governs the leading correction through the canonical modulating flow polynomial D_G; for circuits, the period character, when it exists, governs the leading correction through the period modulating flow polynomial D_G,η. At even moduli these give parity-dependent corrections: the two mechanisms coincide on nonbipartite graphs and separate only in the bipartite circuit problem. More generally, each integral-homology character ζ determines a balanced-dichromatic specialization D_G,ζ. These polynomials form a character-indexed family whose finite-order members give Fourier coefficients of the nowhere-zero flow set and whose retained edge sets are the central sets of a gain semimatroid. We further show that D_G is a cycle-matroid invariant and a signed-Tutte specialization satisfying signed deletion-contraction. Finally, an integral nowhere-zero approximation theorem implies that asymptotically almost every weighted circuit traverses every edge.
ER -