Charbit's spectral short-cycle conjecture: the sharp digon case and a Perron-period obstruction

Definitions and mathematical statement

Let $G$ be a finite simple directed graph on $n\geq1$ vertices, with no loops and at most one arc for each ordered pair of distinct vertices. Opposite arcs are allowed; when both occur, they form a directed cycle of length two. Its adjacency matrix $A\in\{0,1\}^{n\times n}$ has $A_{ij}=1$ exactly when $i\to j$ is an arc and has zero diagonal. The spectral radius is \[ \rho(A)=\max\{|\lambda|:\lambda\in\mathbb C, \det(\lambda I-A)=0\}. \] Although $A$ need not be symmetric, the radius is a well-defined nonnegative real number. A directed cycle of length $\ell$ consists of distinct vertices $v_1,\ldots,v_\ell$ with arcs $v_i\to v_{i+1}$ and $v_\ell\to v_1$.

Charbit's proposed spectral version of a short-cycle bound asks whether, for every integer $k\geq2$, \[ \rho(A)\geq\frac nk \quad\Longrightarrow\quad G\text{ contains a directed cycle of length at most }k. \] Equivalently, every digraph avoiding directed cycles of lengths $2,\ldots,k$ should satisfy the strict inequality $\rho(A)<n/k$. The boundary equality is included in the hypothesis and therefore cannot be discarded. The condition uses the spectral radius of the original adjacency matrix, not its symmetric part, a singular value, or a degree average. The graph is not assumed regular or strongly connected.

Short English statement

Does a large adjacency spectral radius force a short directed cycle with the proposed threshold $n/k$?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20001063 (AIM-COMBINATORICS-0188), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, The Caccetta-Haggkvist conjecture, item 6. Original workshop question underlying AIM-COMBINATORICS-0188. https://aimath.org/WWN/caccetta/caccetta.pdf.