Jacobian graphs

Titel: Jacobian Graphs

Auteurs: Arthur Forey, Javier Fresán, Emmanuel Kowalski, Yuval Wigderson

---

1. Probleemstelling en Context

Het artikel adresseert een fundamenteel probleem in de extremale combinatoriek en de spectrale grafentheorie: het construeren van expliciete families van reguliere grafen die spectraal ononderscheidbaar zijn van willekeurige grafen (d.w.z. ze vertonen pseudorandom eigenschappen), maar die lokaal fundamenteel verschillen van willekeurige grafen.

Specifiek richten de auteurs zich op grafen die:

1. Spectrale Pseudorandomness: Hun niet-triviale eigenwaarden zijn geconcentreerd rondom de semicirkelverdeling (zoals bij willekeurige grafen), wat betekent dat ze "Ramanujan-achtige" eigenschappen kunnen hebben.
2. Extravante Combinatorische Structuur: Ze bevatten geen subgrafieken isomorf met $K_{2,3}$ (de complete bipartiete graaf met partities van grootte 2 en 3) of $C_4$ (cycli van lengte 4).
3. Dichtheid: Ze zijn zo dicht mogelijk bij de theoretische bovengrens voor $K_{2,3}$-vrije grafen, wat ze uitzonderlijk maakt vergeleken met willekeurige grafen met dezelfde dichtheid (die bijna zeker $K_{2,3}$-subgrafieken bevatten).

In een voorgaand werk ([15]) construeerden de auteurs dergelijke grafen, maar deze waren beperkt tot zeer specifieke gevallen (graaf op $p^2$ hoekpunten, met $p$ een priemgetal). Het doel van dit artikel is om deze constructie te generaliseren naar een veel breder scala aan grafen, gebruikmakend van geavanceerde algebraïsche meetkunde.

2. Methodologie

De constructie van de Jacobische grafen ($\Gamma(C, m; k)$) is gebaseerd op de meetkundige eigenschappen van generaliseerde Jacobianen van algebraïsche krommen over eindige velden.

De Data:
Een Jacobische graaf wordt gedefinieerd door:

• Een eindig veld $k$.
• Een gladde, projectieve, algebraïsche kromme $C$ gedefinieerd over $k$ met genus $g$.
• Een $k$-rationale effectieve divisor $m$ op $C$ (de "modulus").
• Een $k$-rationale divisor $\delta$ van graad 1.

De Constructie:

1. Generaliseerde Jacobiaan ($J_m$): Dit is een verbonden algebraïsche groep gedefinieerd over $k$ met dimensie $\dim(J_m) = g + \max(\deg(m)-1, 0)$.
2. Abel-Jacobi Afbeelding ($i_\delta$): Een afbeelding $i_\delta: C \setminus \text{supp}(m) \to J_m$.
3. De Graaf: De hoekpunten van de graaf zijn de $k$-rationale punten van de generaliseerde Jacobiaan, $V = J_m(k)$. Twee hoekpunten $x$ en $y$ zijn verbonden door een rand als en slechts als $x + y$ in het beeld ligt van de $k$-rationale punten van de kromme onder de Abel-Jacobi afbeelding: $x + y \in i_\delta((C \setminus \text{supp}(m))(k))$.

Spectrale Analyse:
De spectrale eigenschappen worden bepaald door de karakteristieke sommen (exponentiële sommen) over de kromme. De auteurs maken gebruik van:

• De Riemann-hypothese voor krommen over eindige velden (Weil/Deligne) om schattingen op de eigenwaarden te krijgen.
• Equidistributiestellingen voor karakteristieke sommen (gebaseerd op werk van Katz en Deligne) om de verdeling van de eigenwaarden te analyseren.
• De theorie van generaliseerde Jacobianen en de structuur van de bijbehorende algebraïsche groepen (bijv. exacte sequenties voor elliptische krommen met een modulus).

3. Belangrijkste Bijdragen

1. Generalisatie van de Constructie:
   In tegenstelling tot het eerdere werk ([15]), dat beperkt was tot specifieke priemgetallen en een vast aantal hoekpunten, kunnen de auteurs nu grafen construeren voor bijna elk aantal hoekpunten $n$. De constructie is "robust" en varieert in continue families, geparametriseerd door moduli-ruimtes van krommen (dimensie 1 voor genus 1, dimensie 3 voor genus 2).

2. Definitie van Jacobische Grafen:
   Het introduceren van een nieuwe klasse grafen die direct gekoppeld is aan de meetkunde van krommen van genus 1 en 2. Dit biedt een rijke bron van voorbeelden voor extremale combinatoriek.

3. Spectrale Analyse en Ramanujan-eigenschappen:
   Het bewijzen dat voor bepaalde parameters (bijv. als de kromme "ordinair" is), er een rij van waarden bestaat waarvoor de grafen Ramanujan-grafen zijn. Dit betekent dat de niet-triviale eigenwaarden optimaal geconcentreerd zijn rondom de spectrale grens.

4. Equidistributie naar de Semicirkelwet:
   Het bewijzen dat de genormaliseerde eigenwaarden van deze grafen, wanneer het veld groeit, convergeren naar de semicirkelverdeling (Wigner's semicircle law). Dit bevestigt dat ze spectraal ononderscheidbaar zijn van willekeurige grafen.

5. Technische Voorwaarde voor $K_{2,3}$-vrijheid:
   Het gebruik van de eigenschap dat het beeld van de kromme in de Jacobiaan een symmetrisch Sidon-ensemble is. Dit garandeert dat de graaf geen $K_{2,3}$ bevat, wat een zeer zeldzame eigenschap is voor grafen met zo'n hoge dichtheid.

4. Resultaten (Theorema 1.2)

Voor een eindig veld $k$ en een uitbreiding $k_n$ van graad $n$, laat $\Gamma_n(C, m)$ de bijbehorende graaf zijn met $\dim(J_m)=2$ en genus $g \in \{1, 2\}$.

• Regelmaat en Dichtheid: De graaf is $d_n$-regulier, waarbij $d_n \sim |k_n|$.
• Geen $K_{2,3}$: De graaf bevat geen subgraaf isomorf met $K_{2,3}$.
• Spectrale Scherpte: De niet-triviale eigenwaarden liggen in het interval $[-2\sqrt{|k_n|} + O(|k_n|^{-1}), 2\sqrt{|k_n|} + O(|k_n|^{-1})]$.
• Ramanujan-eigenschap: Als $C$ ordinair is, bestaat er een rij van $n$ met positieve dichtheid waarvoor de graaf een Ramanujan-graf is (eigenwaarden binnen $[-2\sqrt{d_n-1}, 2\sqrt{d_n-1}]$).
• Semicirkelverdeling: Onder specifieke voorwaarden (afhankelijk van de genus en de modulus), zijn de genormaliseerde eigenwaarden $\lambda / \sqrt{d_n-1}$ equidistribueerd volgens de semicirkelwet $\mu_{sc}$ wanneer $n \to \infty$. De convergentie wordt gemeten via de 1-Wasserstein afstand.

5. Betekenis en Toekomstperspectief

• Combinatorische Toepassingen: Deze grafen dienen als krachtige testcases voor problemen in de Ramsey-theorie. Specifiek wordt de onafhankelijkheidsgetal (independence number) van deze grafen onderzocht. De auteurs vragen zich af of het onafhankelijkheidsgetal $O(n^{3/4-\delta})$ kan zijn, wat een belangrijke doorbraak zou zijn in de theorie van $K_{2,3}$-vrije grafen.
• Averaging Argumenten: Omdat de grafen afhangen van continue parameters (moduli-ruimtes), kunnen de auteurs "gemiddelde" eigenschappen bestuderen. Dit biedt een nieuwe methode om het bestaan van grafen met specifieke eigenschappen aan te tonen zonder ze expliciet te construeren (door te middelen over de familie).
• Vergelijking met Willekeurige Grafen: De resultaten tonen aan dat het mogelijk is om grafen te construeren die lokaal zeer gestructureerd zijn (geen $C_4$ of $K_{2,3}$) maar globaal (spectraal) identiek zijn aan willekeurige grafen. Dit weerlegt de intuïtie dat lokale restricties noodzakelijkerwijs leiden tot een afwijkend spectrum.
• Rekenkundige Meetkunde: Het artikel illustreert de kracht van diepe resultaten uit de algebraïsche meetkunde (Riemann-hypothese, equidistributie van monodromiegroepen) in de combinatoriek.

Conclusie:
Dit artikel introduceert een nieuwe, rijke familie van expliciete grafen die de brug slaan tussen algebraïsche meetkunde en extremale combinatoriek. Ze bieden een "continuous" familie van voorbeelden die zowel spectrale optimaliteit als extreme lokale structuur combineren, wat nieuwe inzichten biedt in de aard van pseudorandomheid en de limieten van de dichtheid van subgraaf-vrije grafen.