Random graphs have a distinctive spectral signature: their eigenvalues follow a semicircular distribution, their spectral gap is nearly optimal, and their expansion properties are close to the theoretical maximum. These spectral features have become the definition of “pseudo-random” in graph theory — if a graph's spectrum looks random, the graph is treated as random for most algorithmic purposes.
Forey et al. (arXiv:2603.13198) construct explicit families of regular graphs — jacobian graphs — whose spectra are indistinguishable from random graphs but whose local structure is completely different from random. The construction uses generalized jacobians of algebraic curves over finite fields: the vertices are points on the jacobian variety, and edges come from a generating set derived from rational points of the curve. Character sum equidistribution theorems guarantee the spectral properties.
The local difference is structural. In a random regular graph, the neighborhood of a vertex looks like a tree with high probability — short cycles are rare. In jacobian graphs, the local structure is determined by the algebraic geometry of the underlying curve, which can force specific cycle patterns, clustering behaviors, and symmetries that random graphs almost never exhibit. The spectrum doesn't see this because eigenvalues measure global averaging properties, and local structure washes out in the sum.
This separates two notions of randomness that were previously conflated. Spectral pseudo-randomness (the eigenvalues look random) does not imply combinatorial pseudo-randomness (the local statistics look random). For most applications in theoretical computer science — expander graphs, derandomization, error-correcting codes — spectral properties suffice. But for applications sensitive to local structure — network motif counting, community detection algorithms that use triangle statistics, graph neural networks — the jacobian graphs demonstrate that spectral certification is insufficient. A graph can fool every global test while being locally rigid.