Maximum edge density of spectrally symmetric graphs

Problem 1 · arXiv:2512.08049

arXiv Problem high confidence— first stated 2025-12-08

Authors: Saieed Akbari, Jonathan Aloni, Maxwell Levit, Bojan Mohar, Steven Xia

Status open high confidence

The paper establishes that the minimal density constant $\widehat{\rho}$ satisfies $\frac{13}{18} \leq \widehat{\rho} \leq \frac{10}{11}$, with the lower bound witnessed by a spectrally symmetric orientation of $K_6 - E(2K_2)$ and the upper bound coming from a density obstruction for line graphs of dense graphs. No follow-up paper resolving the exact value of $\widehat{\rho}$ was found in the literature as of May 2026; the problem remains open.

Reviewer notes. No follow-up found in the indexed literature. The conjecture is approximately 5 months old (posted December 2025). Four web searches and one WebFetch on the source paper abstract were performed; all returned only the original arXiv:2512.08049 entry, confirming the open status with high confidence.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Problem. Find the minimal constant $\widehat{\rho}\in[0,1]$ such that each spectrally symmetric graph satisfies $\frac{2|E(G)|}{|V(G)|^{2}}\leq\widehat{\rho}$.

Context

Motivated by the classical fact that a graph of order $n$ with more than $\frac{n^2}{4}$ edges is not bipartite (and hence its adjacency spectrum is not symmetric), the authors ask for an analogous density threshold for spectrally symmetric orientations. The paper establishes $\frac{13}{18}\leq\widehat{\rho}\leq\frac{10}{11}$ but the exact value remains open.

Source paper

Spectrally symmetric orientations of graphs
Saieed Akbari, Jonathan Aloni, Maxwell Levit, Bojan Mohar, Steven Xia · 2025-12-08
https://arxiv.org/abs/2512.08049