A Note on Polynomial Certificates for Walk Inequalities

Technical Summary: A Note on Polynomial Certificates for Walk Inequalities

Problem Statement
The paper addresses the problem of establishing universal inequalities for the number of walks of length $m$ in an undirected graph $G$, denoted as $w_m(G)$. These quantities, defined as $w_m(G) = \mathbf{1}^T A^m \mathbf{1}$ (where $A$ is the adjacency matrix and $\mathbf{1}$ is the all-ones vector), form a moment sequence of a finite positive measure derived from the spectral decomposition of $A$. While specific families of inequalities are known—such as those derived from Cauchy–Schwarz, the "sandwich" inequalities, and generalized Erdős–Simonovits inequalities—the paper seeks a unified, finite recognition criterion for a specific class of polynomial certificates that guarantee such inequalities hold for all undirected graphs.

Methodology
The authors employ a two-step methodology combining spectral graph theory with real algebraic geometry:

1. Spectral Moments and Transfer Principle: The authors utilize the spectral decomposition of the adjacency matrix to express $w_m(G)$ as the $m$-th moment of a finite positive measure $\nu_G$. They define a "walk functional" $\Phi_{G,r}(f)$ for a polynomial $f$, which maps the polynomial to a linear combination of products of walk counts. By leveraging the product structure of the measure $\nu_G^{\otimes r}$, they establish a "transfer principle" (Theorem 1). This principle states that the walk functional of a polynomial $f$ is equal to the integral of its normalized symmetrization, $\text{Sym}_r f$, against the product measure. Consequently, if $\text{Sym}_r f$ is globally nonnegative, the corresponding inequality for walk counts holds universally.

2. Symmetrized Binomial Analysis: The paper focuses on "symmetrized binomial certificates" of the form $C_{\alpha, \beta} = \text{Sym}_r(x^\beta - x^\alpha)$. The core task is to determine exactly when such a polynomial is globally nonnegative. The authors apply tools from majorization theory (Hardy–Littlewood–Pólya, Rado, Muirhead) and properties of Newton polytopes to analyze the coefficients and exponents of these polynomials.

Key Contributions and Results

• Exact Recognition Criterion (Theorem 3): The central result is a necessary and sufficient condition for the symmetrized binomial $m_\beta - m_\alpha$ to be globally nonnegative. For exponent vectors $\alpha, \beta \in \mathbb{N}_0^r$ in distinct permutation orbits, $m_\beta - m_\alpha$ is globally nonnegative if and only if:

  1. $\beta$ is coordinatewise even (i.e., every component of $\beta$ is an even integer).
  2. $\beta$ majorizes $\alpha$ ($\beta \succeq \alpha$).
     This reduces the algebraic question of global nonnegativity to a finite combinatorial test involving parity and partial sums.

• Universal Walk Inequalities (Corollary 4): By combining the transfer principle with the majorization criterion, the authors derive a general family of inequalities: if $\beta$ is coordinatewise even and $\beta \succeq \alpha$, then $\prod w_{\alpha_i}(G) \leq \prod w_{\beta_i}(G)$ for every undirected graph $G$.

• Recovery of Classical Inequalities: The framework recovers and generalizes several known results:

  • Sandwich Inequalities: The characterization for $r=2$ exactly recovers the nontrivial members of the sandwich family ($w_{2a+c} w_{2(a+b)+c} \leq w_{2a} w_{2(a+b+c)}$).
  • Permutation Inequalities: The paper derives inequalities of the form $\prod w_{\alpha_i + \alpha_{\sigma(i)}} \leq \prod w_{2\alpha_i}$, providing an exact single-square representation for the difference.
  • Determinantal Inequalities: The framework extends to Hankel determinants, showing that determinants of moment matrices formed by walk counts are nonnegative, with equality conditions linked to the number of distinct main eigenvalues.

• Limitations and Parity Obstruction (Corollary 8): The paper explicitly identifies the boundary of this method. It demonstrates that the generalized Erdős–Simonovits inequalities ($w_{2a+b}^k \leq w_{2a+bk} w_{2a}^{k-1}$) are universally valid but do not possess a symmetrized binomial certificate of the form $m_\beta - m_\alpha$ when $b$ and $k$ are both odd. In these cases, the majorization condition holds, but the coordinatewise evenness condition fails, proving that the method does not capture all valid universal inequalities.

Significance
The paper's primary contribution is the formulation of the "evenness-and-majorization" criterion as a pointwise symmetric polynomial realization. It provides a direct, finite algorithm to recognize symmetrized binomial certificates for walk inequalities without requiring Sum-of-Squares (SOS) representations. The authors position this work as a specialization of a broader framework relating moment cones and tropicalization (citing [3]), specifically tailored to graph walk counts.

The authors modestly claim that while this framework unifies and re-packages standard consequences of Muirhead's inequality and Hankel matrix positivity, it does not characterize all universally valid walk inequalities. The existence of valid inequalities (like the odd-parameter Erdős–Simonovits case) that lack this specific type of certificate highlights a gap. The paper concludes by identifying the characterization of symmetric polynomials $p$ such that $\Phi_{G,r}(p) \geq 0$ for all graphs $G$ as an open problem, suggesting that future work may require graph-specific certificates that exploit the entrywise nonnegativity of adjacency matrices beyond the scope of global polynomial nonnegativity.