A 104/121 Lower Bound for Spectrally Symmetric Orientations
Abstract
Akbari et al. (2025) introduced the extremal problem for orientations whose sixth-root Hermitian adjacency spectrum is symmetric about zero and proved 13/18 ≤ ρ̂≤ 10/11. We give an explicit orientation on eleven vertices with 52 edges, underlying graph K11-3K2, and exact characteristic polynomial x^11 - 52x^9 + 810x^7 - 4357x^5 + 6793x^3 - 1494x. The polynomial is odd, hence the Hermitian spectrum is symmetric. By the equal-blow-up theorem, this single seed yields arbitrarily large examples of the same limit density and therefore raises the constructive bound to 104/121 ≈ 0.859504. This witness is supplied. A density-filtered tournament-completion search on an NVIDIA A100 found the construction; the search path is auxiliary to the exact certificate. The same search programme also produced exact 33-edge and 42-edge constructions on 9 and 10 vertices, with densities 22/27 and 21/25. The order-nine construction is fixed-order optimal; the order-ten optimality statement additionally uses the recorded exhaustive 43-edge campaign.
Fields of Study & Subjects
Graph theory and applications
Tensor decomposition and applications
Matrix Theory and Algorithms
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 19 August 2026
- Document type
- Preprint