Digraph Laplacian spectra: The 2005 polygon conjecture fails for all orders above four
Abstract
Let Λn be the set of all eigenvalues of standardized Laplacian matrices of order n, equivalently, of stochastic n× n matrices with off-diagonal entries at most 1/n. In 2005, a polygon Sn⊆Λn was constructed, and it was conjectured that Λn=Sn; this holds for n≤3. We show that the conjecture fails for every n≥5. The vertices of Sn 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 Sn; however, adding chords with nonconstant weights moves it along an edge of Sn to first order and, with an explicit coefficient, beyond the supporting line of this edge to second order. Consequently, every edge of Sn 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 ∂Λ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=S4, 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≥5. We certify an explicit weighted counterexample for n=5, lying only 1.5·10−3 outside S5, and an unweighted one for n=7: the directed $6$-cycle with a duplicated vertex. Its eigenvalue outside S7 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 π2/2n4. We also observe that Sn is a zonotope, describe Λn in terms of eigenvectors, and prove that Sm⊆ Sn whenever m| n.
Related
- Numerical results for the Stokes problem and the iterated Laplacian in a polygon
- The Distance Laplacian and Distance Signless Laplacian Spectra of 𝒞-Graphs
- Proof of a Conjecture of Matherne, Morales, and Selover on Encodings of Unit Interval Orders
- The Laplacian Sn,n conjecture is true
- On the Brouwer-type Conjecture for Signless Laplacian Eigenvalues of Graphs
BibTeX
@misc{chebotarev2026digraph,
title = {{Digraph Laplacian spectra: The 2005 polygon conjecture fails for all orders above four}},
author = {Pavel Chebotarev},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14100},
eprint = {2610.14100},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14100},
}
RIS
TY - UNPB
TI - Digraph Laplacian spectra: The 2005 polygon conjecture fails for all orders above four
AU - Pavel Chebotarev
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.14100
UR - https://arxiv.org/abs/2610.14100
AB - Let Λ_n be the set of all eigenvalues of standardized Laplacian matrices of order n, equivalently, of stochastic n× n matrices with off-diagonal entries at most 1/n. In 2005, a polygon S_n⊆Λ_n was constructed, and it was conjectured that Λ_n=S_n; this holds for n≤3. We show that the conjecture fails for every n≥5. 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 ∂Λ_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≥5. We certify an explicit weighted counterexample for n=5, lying only 1.5·10^−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 π^2/2n^4. We also observe that S_n is a zonotope, describe Λ_n in terms of eigenvectors, and prove that S_m⊆ S_n whenever m| n.
ER -