A 104/121 Lower Bound for Spectrally Symmetric Orientations

Read full text
Authors: John Seamons
Cited by: 0

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