Paperlane

no. 5 · Friday 30 October 2026

Digraph Laplacian spectra: The 2005 polygon conjecture fails for all orders above four

Pavel Chebotarev

math.CO · v3 · 22 pp

Abstract

Let $Λ_n$ be the set of all eigenvalues of standardized Laplacian matrices of order $n$, equivalently, of stochastic $n\times n$ matrices with off-diagonal entries at most $\frac1n$. In 2005, a polygon $S_n\subseteqΛ_n$ was constructed, and it was conjectured that $Λ_n=S_n$; this holds for $n\le3$. We show that the conjecture fails for every $n\ge5$. The vertices of $S_n$ are eigenvalues of circulant Laplacians built from powers of the directed $n$-cycle. To first order, no perturbation of these circulants moves such an eigenvalue out of $S_n$; however, adding chords with nonconstant weights moves it along an edge of $S_n$ to first order and, with an explicit coefficient, beyond the supporting line of this edge to second order. Consequently, every edge of $S_n$ not incident to $0$ or $1$ contains interior points of $Λ_n$, except possibly, for even $n$, the two horizontal edges, whereas the four edges incident to $0$ or $1$ lie on $\partialΛ_n$. For $n=4$, whose only other edges are horizontal, the question was left open in the previous versions; it has since been settled, $Λ_4=S_4$, by a computer-assisted proof of L. Marshall, after an earlier claim by D.Z. Liu, who also proved that $Λ_n$ is not convex for $n\ge5$. We certify an explicit weighted counterexample for $n=5$, lying only $1.5\cdot10^{-3}$ outside $S_5$, and an unweighted one for $n=7$: the directed $6$-cycle with a duplicated vertex. Its eigenvalue outside $S_7$ is also an eigenvalue of the two-chord digraph that ends the above perturbation; for the analogous digraphs of order $n$, the excess is asymptotic to $\frac{π^2}{2n^4}$. We also observe that $S_n$ is a zonotope, describe $Λ_n$ in terms of eigenvectors, and prove that $S_m\subseteq S_n$ whenever $m\mid n$.

comments
22 pages, 1 figure. This Version 3 highlights (in blue) recent advancements by D.Z. Liu and L. Marshall
fields
Combinatorics, Rings and Algebras, Spectral Theory
pdf ↗ page arXiv:2610.14100 ↗