A Note on Polynomial Certificates for Walk Inequalities

Abstract

Let $w_m(G)$ denote the total number of walks of length $m$ in an undirected graph $G$. Spectral decomposition shows that $(w_m(G){)}_{m\ge 0}$ is a moment sequence of a finite positive measure. We use exchangeability of its product measures to turn global nonnegativity of polynomial symmetrizations into universal inequalities for the number of walks. For exponent vectors $\alpha ,\beta$ in distinct permutation orbits, $\mathrm{Sym}(x^{\beta }-x^{\alpha })$ is globally nonnegative exactly when $\beta$ is coordinatewise even and majorizes $\alpha$. This finite criterion includes several classical inequalities as special cases; univariate polynomials and squared alternants also yield linear and Hankel determinant inequalities.

10 pages. Substantially revised and expanded version; title changed