Jacobian graphs

1. Problem Statement and Motivation

The paper addresses the construction of explicit families of regular graphs that possess two seemingly contradictory properties:

1. Spectral Pseudorandomness: Their eigenvalue distribution is indistinguishable from that of random graphs (specifically, they follow the semicircle law and can be Ramanujan graphs).
2. Structural Rigidity: Unlike random graphs of the same density, they are free of specific small subgraphs, notably $K_{2,3}$ (the complete bipartite graph with partitions of size 2 and 3) and $C_4$ (cycles of length 4).

Previous work by the authors (in companion paper [15]) constructed such graphs using subsets of $k \times k$ related to Sidon sets and exponential sums. However, those constructions were limited: they produced graphs on $p^{2k}$ vertices (where $p$ is prime) and offered very few non-isomorphic examples. The authors aim to generalize this construction to create a "robust" family of graphs defined on nearly every integer number of vertices, utilizing the rich geometry of generalized Jacobians of algebraic curves.

2. Methodology

The construction relies on deep tools from algebraic geometry, arithmetic geometry, and spectral graph theory.

A. The Construction: Jacobian Graphs

A Jacobian graph $\Gamma(C, m; k)$ is defined by the following data:

• $k$: A finite field.
• $C$: A smooth, projective, geometrically connected algebraic curve over $k$.
• $m$: A $k$-rational effective divisor on $C$ (the modulus).
• $\delta$: A $k$-rational divisor of degree 1 on $C$.

From this data, the authors define:

1. The Generalized Jacobian ($J_m$): A connected algebraic group over $k$ of dimension $g + \max(\deg(m)-1, 0)$, where $g$ is the genus of $C$.
2. The Abel-Jacobi Map ($i_\delta$): A map from the curve (minus the support of $m$) to $J_m$.
3. The Graph: The vertex set is the group of rational points $J_m(k)$. An edge exists between $x$ and $y$ if and only if $x + y \in i_\delta(C \setminus \text{supp}(m))(k)$.

The authors focus on cases where $\dim(J_m) = 2$, which occurs when:

• $g=1$ and $\deg(m)=2$ (two distinct points or one double point).
• $g=2$ and $m=\emptyset$ (the classical Jacobian of a genus 2 curve).

B. Spectral Analysis via Equidistribution

The spectrum of these graphs is determined by character sums over the finite group $J_m(k)$. The authors employ the equidistribution theorems developed by Katz and Deligne for families of exponential sums.

• They associate the graph's spectrum to the trace of Frobenius acting on certain $\ell$-adic sheaves (specifically $i_{\delta, *}\mathbb{Q}_\ell[1](1/2)$).
• Using the Sato-Tate conjecture framework (generalized to this context), they prove that as the field extension degree $n \to \infty$, the normalized eigenvalues become equidistributed according to the semicircle law (Wigner's law).
• They utilize Larsen's Alternative and the classification of finite subgroups of $SU_2(\mathbb{C})$ to determine when the monodromy group is the full $SU_2(\mathbb{C})$, ensuring the semicircular distribution.

C. Combinatorial Properties

The absence of $K_{2,3}$ and $C_4$ subgraphs is derived from the fact that the image of the curve under the Abel-Jacobi map forms a symmetric Sidon set within the group $J_m(k)$. A Sidon set $S$ has the property that the equation $a+b=c+d$ has only trivial solutions. This structural constraint prevents the formation of specific dense subgraphs.

3. Key Contributions

1. Generalization of Constructions: The paper moves beyond the sparse, sporadic examples of [15] to a "continuous" family of graphs parameterized by moduli spaces of curves (dimension 1 for genus 1, dimension 3 for genus 2). This allows for the construction of graphs on nearly every integer $n$ (specifically, $n$ such that $n \sim p^2$).
2. Ramanujan Graphs: The authors prove the existence of infinite families of Ramanujan graphs (graphs where non-trivial eigenvalues are bounded by $2\sqrt{d-1}$) within this family, provided the underlying curve is ordinary and specific arithmetic conditions on the trace of Frobenius are met.
3. Semicircular Spectrum: They establish that the empirical spectral distribution of these graphs converges to the semicircle law $\mu_{sc} = \frac{1}{\pi}\sqrt{4-x^2}dx$ on $[-2, 2]$. They provide explicit bounds on the Wasserstein distance between the empirical spectrum and the semicircle law, showing convergence rates of $O(1/n)$.
4. Explicitness and Computability: Despite the heavy theoretical machinery, the graphs are "explicit." The authors provide algorithms to construct them efficiently using standard tools for elliptic and genus 2 curves (e.g., Cantor's algorithm for Jacobians).
5. Independence Number Question: The paper highlights the potential of these graphs for Ramsey theory. Because they are dense yet $K_{2,3}$-free, they are candidates for graphs with unusually small independence numbers (potentially $O(n^{3/4-\delta})$), a major open problem.

4. Main Results (Theorem 1.2)

Let $\Gamma_n(C, m)$ be the Jacobian graph over the extension field $k_n$. Assuming $\dim(J_m)=2$ and $g \in \{1, 2\}$:

1. Regularity and Structure: The graph is $d_n$-regular and contains no $K_{2,3}$ subgraph.
2. Spectral Bound: Non-trivial eigenvalues lie in the interval $[-2\sqrt{|k_n|} + O(|k_n|^{-1}), 2\sqrt{|k_n|} + O(|k_n|^{-1})]$.
3. Ramanujan Property: If $C$ is ordinary, there exists a sequence of $n$ with positive density such that $\Gamma_n$ is a Ramanujan graph.
4. Semicircular Distribution: Under specific conditions (e.g., $g=2$, or $g=1$ with specific constraints on the trace of Frobenius), the normalized eigenvalues become equidistributed according to the semicircle law as $n \to \infty$.
5. Convergence Rate: The Wasserstein distance between the normalized spectrum and the semicircle law is bounded by $O(1/n)$.

5. Significance and Impact

• Bridge Between Fields: The paper successfully bridges extremal combinatorics (Sidon sets, Turán-type problems) with arithmetic geometry (generalized Jacobians, equidistribution of Frobenius traces).
• New Test Cases: These graphs serve as "robust" test cases for conjectures in extremal graph theory. Their "continuous" parameterization allows for averaging arguments (as suggested in Remark 1.6) to prove the existence of graphs with specific properties without explicit construction.
• Resolution of Spectral vs. Structural Tension: It demonstrates that high spectral pseudorandomness (resembling random graphs) does not necessarily imply structural randomness (containing all small subgraphs). These graphs are "spectrally random" but "structurally rigid."
• Computational Feasibility: Unlike many theoretical constructions in algebraic geometry, these graphs can be explicitly computed for large parameters, making them suitable for applications in coding theory, cryptography, and network design.

In summary, the paper introduces a powerful new class of explicit graphs that are optimal in terms of spectral expansion (Ramanujan) and structural sparsity (Sidon sets), constructed via the sophisticated geometry of generalized Jacobians.