Polynomial positivity cones for Coxeter roots and walks in trees
Abstract
For a finite simple graph G and an integer k≥0, let wk(G) denote the number of walks of length k. We prove the conjecture of Täubig, Weihmann, Kosub, Hemmecke, and Mayr for every finite tree and determine all equality cases. If T has n≥1 vertices, then n wk+1(T)−2(n−1)wk(T)≥0 for every k≥1; for n≥3, equality holds if and only if T is a star and k is even, whereas for n=1 or n=2, equality holds for every k≥1. For non-Dynkin trees and even indices, the proof is based on a polynomial positivity cone associated with the adjacency operator of a finite graph and a positive real root of its simply-laced Coxeter system. For finite connected bipartite non-Dynkin graphs, we establish sufficient positivity conditions in terms of Coxeter orbits and inversion sets, and verify these conditions for indicator roots supported on connected induced subtrees. For non-Dynkin trees, this yields the rooted even-index inequality and, after summation, the corresponding global inequality. We also prove that if G is a finite connected bipartite non-Dynkin simple graph, ∅≠ U⊆ V(G), and the subgraph of G induced by U is a tree, then |U|wk+1(G,U)−2(|U|−1)wk(G,U)≥0 for every k≥0, where wk(G,U) counts the length-k walks in G whose initial and terminal vertices lie in U; the intermediate vertices are unrestricted. The remaining even-index cases for finite Dynkin trees are handled by generating-function recurrences, while the odd-index cases follow from a spectral covariance identity.
Related
- Powers, Roots, and Positivity
- Matrix roots of order n of a multivariate polynomial
- Improved computation of polynomial roots over number fields when using complex embeddings
- Eigensolvers for polynomial roots and tensor decomposition
- Polynomial stability conditions for vector bundles: positivity, equivariance and blow-ups
BibTeX
@misc{cai2026polynomial,
title = {{Polynomial positivity cones for Coxeter roots and walks in trees}},
author = {Dongxiu Cai and Zhenbo Chen and Jiasheng Zeng and Xiao-Dong Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11323},
eprint = {2609.11323},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11323},
}
RIS
TY - UNPB
TI - Polynomial positivity cones for Coxeter roots and walks in trees
AU - Dongxiu Cai
AU - Zhenbo Chen
AU - Jiasheng Zeng
AU - Xiao-Dong Zhang
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11323
UR - https://arxiv.org/abs/2609.11323
AB - For a finite simple graph G and an integer k≥0, let w_k(G) denote the number of walks of length k. We prove the conjecture of Täubig, Weihmann, Kosub, Hemmecke, and Mayr for every finite tree and determine all equality cases. If T has n≥1 vertices, then n w_k+1(T)−2(n−1)w_k(T)≥0 for every k≥1; for n≥3, equality holds if and only if T is a star and k is even, whereas for n=1 or n=2, equality holds for every k≥1. For non-Dynkin trees and even indices, the proof is based on a polynomial positivity cone associated with the adjacency operator of a finite graph and a positive real root of its simply-laced Coxeter system. For finite connected bipartite non-Dynkin graphs, we establish sufficient positivity conditions in terms of Coxeter orbits and inversion sets, and verify these conditions for indicator roots supported on connected induced subtrees. For non-Dynkin trees, this yields the rooted even-index inequality and, after summation, the corresponding global inequality. We also prove that if G is a finite connected bipartite non-Dynkin simple graph, ∅≠ U⊆ V(G), and the subgraph of G induced by U is a tree, then |U|w_k+1(G,U)−2(|U|−1)w_k(G,U)≥0 for every k≥0, where w_k(G,U) counts the length-k walks in G whose initial and terminal vertices lie in U; the intermediate vertices are unrestricted. The remaining even-index cases for finite Dynkin trees are handled by generating-function recurrences, while the odd-index cases follow from a spectral covariance identity.
ER -