Graf de Ramanujan

En teoria de grafs espectrals, un graf de Ramanujan, és un graf regular la bretxa espectral del qual és gairebé tan gran com sigui possible (vegeu la teoria de grafs extremales). Aquests grafs són excel·lents expansors espectrals. Com assenyala l'estudi de Murty, els grafs de Ramanujan "fusionen diverses branques de les matemàtiques pures, a saber, la teoria de nombres, la teoria de la representació i la geometria algebraica". Porten aquest nom en referència a Srinivasa Ramanujan; i prové de la conjectura de Ramanujan–Petersson, que es va utilitzar en la construcció d'alguns d'aquests grafs.

Graf de Pappus: un graf regular, format per 18 vèrtexs, tots ells enllaçats amb altres tres vèrtexs

Definició

Sigui $G$ un graf connectat $d$-regular amb $n$ vèrtexs, i siguin $\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}$ els valors propis de la matriu d'adjacència de $G$ (o l'espectre de $G$). Atès que $G$ està connectat i és $d$-regular, els seus valors propis satisfan que $d=\lambda _{1}>\lambda _{2}$ $\geq \cdots \geq \lambda _{n}\geq -d$.

Ara es defineix $\lambda (G)=\max _{i\neq 1}|\lambda _{i}|=\max(|\lambda _{2}|,|\lambda _{n}|)$. Un graf connectat $d$-regular $G$ és un graf de Ramanujan si $\lambda (G)\leq 2{\sqrt {d-1}}$.

Moltes fonts usen una definició alternativa dels grafs de Ramanujan, mitjançant l'expressió $\lambda '(G)=\max _{|\lambda _{i}|<d}|\lambda _{i}|$ (sempre que existeixi $\lambda _{i}$ amb $|\lambda _{i}|<d$). En altres paraules, es permet $-d$ a més dels valors propis "petits". Ja que $\lambda _{n}=-d$ si i només si el graf és bipartit, l'article es refereix als grafs que satisfan aquesta definició alternativa, però no als grafs bipartits de Ramanujan segons la primera definició.

Com va observar Toshikazu Sunada, un graf regular és de Ramanujan, si i només, si la seva funció zeta d'Ihara satisfà un anàleg de la hipòtesi de Riemann.

Exemples i construccions

El graf complet $K_{d+1}$ té espectre $d,-1,-1,\dots ,-1$, i per tant $\lambda (K_{d+1})=1$, i llavors el graf és un graf de Ramanujan per cada $d>1$. El graf bipartit complet $K_{d,d}$ té espectre $d,0,0,\dots ,0,-d$ i per tant, és un graf bipartit de Ramanujan per cada $d$.

El graf de Petersen té espectre $3,1,1,1,1,1,-2,-2,-2,-2$, per la qual cosa és un graf de Ramanujan 3-regular. El graf icosaèdric és un graf de Ramanujan 5-regular.

Un graf de Paley d'ordre $q$ és ${\frac {q-1}{2}}$-regular amb tots els altres valors propis, amb ${\frac {-1\pm {\sqrt {q}}}{2}}$ fent que els grafs de Paley siguin una família infinita de grafs de Ramanujan.

Els matemàtics sovint estan interessats a construir grafs de Ramanujan $d$-regulars per a cada $d$ fix. Les construccions actuals de famílies infinites de tals grafs de Ramanujan són sovint algebraiques.

• Lubotzky, Phillips i Sarnak van demostrar com construir una família infinita de grafs de Ramanujan $(p+1)$-regulars, sempre que $p$ sigui un nombre primer i $p\equiv 1{\pmod {4}}$. La seva prova utilitza la conjectura de Ramanujan, circumstància que va portar a adoptar el nom de grafs de Ramanujan. A més de ser grafs de Ramanujan, la seva construcció satisfà algunes altres propietats, per exemple, la seva circumferència és $\Omega (\log _{p}(n))$ on $n$ és el nombre de nodes
• Morgenstern va estendre la construcció de Lubotzky, Phillips i Sarnak. La seva construcció estesa es manté sempre que $p$ sigui una potència primera.
• Arnold Pizer va demostrar que els grafs de isogenia supersingular són de Ramanujan, encara que tendeixen a tenir una circumferència menor que els grafs de Lubotzky, Phillips i Sarnak. Igual que els grafs de Lubotzky, Phillips i Sarnak, els graus d'aquests grafs són sempre un nombre primer més un. Aquests gràfics s'han proposat com a base per a la criptografia de corba el·líptica post-quàntica.
• Adam Marcus, Daniel Spielman i Nikhil Srivastava van demostrar l'existència d'infinits grafs bipartitos de Ramanujan $d$-regulars per qualsevol $d\geq 3$. Més tard van demostrar que existeixen grafs bipartios de Ramanujan de cada grau i cada nombre de vèrtexs. Michael B. Cohen va demostrar com construir aquests grafs en temps polinòmic.

Segueix sent un problema obert si hi ha infinits grafs de Ramanujan $d$-regulars (no bipartits) per qualsevol $d\geq 3$. En particular, el problema està obert per $d=7$, el cas més petit pel qual $d-1$ no és una potència primera i, per tant, no està cobert per la construcció de Morgenstern.

Grafs de Ramanujan com a grafs expansors

La constant $2{\sqrt {d-1}}$ en la definició dels grafs de Ramanujan és la millor constant possible per cada $d$ i per a grafs grans. En altres paraules, per cada $d$ i $\epsilon >0$, existeix un $n$ tal que tots grafs $d$-regulars $G$ amb almenys $n$ vèrtexs satisfan que $\lambda (G)>2{\sqrt {d-1}}-\epsilon$ (vegin-se més a baix declaracions més precises i esbossos de demostració). D'altra banda, Friedman va demostrar que per cada $d$ i $\epsilon >0$ i per un $n$ suficientment gran, qualsevol graf $G$ $d$-regular de $n$ vèrtexs satisfà que $\lambda (G)<2{\sqrt {d-1}}+\epsilon$ amb alta probabilitat. Això significa que els grafs de Ramanujan són essencialment els millors grafs expansors possibles.

Quan es necessita obtenir un límit ajustat en$\lambda (G)$, el lema del mescla de l'expansor proporciona límits excel·lents en la uniformitat de la distribució dels contorns en els grafs de Ramanujan, i qualsevol recorregut aleatori en aquests grafs posseeix un temps de mescla logarítmic (en termes del nombre de vèrtexs): en altres paraules, el recorregut aleatori convergeix a la distribució estacionària (uniforme) molt ràpidament. Per tant, el diàmetre dels gràfics de Ramanujan també està limitat logarítmicament en termes del nombre de vèrtexs.

Extremalitat dels grafs de Ramanujan

Si $G$ és un graf $d$-regular amb diàmetre $m$, un teorema a causa de Noga Alon estableix que

$\lambda _{2}(G)\geq 2{\sqrt {d-1}}-{\frac {2{\sqrt {d-1}}-1}{\lfloor m/2\rfloor }}.$

Quan $G$ és $d$-regular i està connectat en almenys tres vèrtexs, $|\lambda _{2}|<d$, i per tant $\lambda (G)\geq \lambda _{2}$. Sigui ${\mathcal {G}}_{n}^{d}$ el conjunt de tots els grafs connectats $d$-regulars $G$ amb almenys $n$ vèrtexs. Atès que el diàmetre mínim dels grafs en ${\mathcal {G}}_{n}^{d}$ s'acosta a l'infinit per a $d$ fix, i augmentant $n$, aquest teorema implica un teorema anterior de Alon i Boppana que estableix que

$\lim _{n\to \infty }\inf _{G\in {\mathcal {G}}_{n}^{d}}\lambda (G)\geq 2{\sqrt {d-1}}.$

Un límit lleugerament més fort és

$\lambda _{2}(G)\geq 2{\sqrt {d-1}}\cdot \left(1-{\frac {c}{m^{2}}}\right),$

on $c\approx 2\pi ^{2}$. L'esbós de la prova és el següent. Prengui's $k=\left\lfloor {\frac {m}{2}}\right\rfloor -1$. Sigui $T_{d,k}$ l'arbre complet $(d-1)$-ari d'altura $k$ (cada vèrtex intern té $d-1$ fills), i sigui $A_{d,k}$ la seva matriu de adyacencia. Es vol demostrar que $\lambda _{2}(G)\geq \lambda _{1}(T_{d,k})=2{\sqrt {d-1}}\cos \theta$, on $\theta ={\frac {\pi }{k+2}}$. Ara, es defineix una funció $g:V(T_{d,k})\rightarrow \mathbb {R}$ per $g(x)=(d-1)^{-\delta /2}\cdot \sin((k+1-\delta )\theta )$, on $\delta$ és la distància des de l'arrel $x$ de $T_{d,k}$. Es pot verificar que $A_{t,k}g=\lambda _{1}(T_{d,k})g$ i que $\lambda _{1}(T_{d,k})$ és de fet el major valor propi de $A_{d,k}$. Ara, siguin $s$ i $t$ un parell de vèrtexs a distància $m$ en $G$, i es defineix

$f(v)={\begin{cases}c_{1}g(v_{s})&{\text{per a }}v{\text{ a la distància }}\leq k{\text{ des de }}s,\\-c_{2}g(v_{t})&{\text{per a }}v{\text{ a la distància }}\leq k{\text{ des de }}t,\\0&{\text{altrament,}}\end{cases}}$

on $v_{s}$ és un vèrtex en $T_{d,k}$ la distància del qual a l'arrel és igual a la distància des de $v$ a $s$ i la simètrica per $v_{t}$. Es pot pensar en això com "incrustar" dues còpies separades de $T_{d,k}$, amb alguns vèrtexs col·lapsats en un. En triar el valor dels reals positius $c_{1},c_{2}$ adequadament s'obté $f\perp 1$, $(Af)_{v}\geq \lambda _{1}(T_{d,k})f_{v}$ per $v$ prop d'$s$ i $(Af)_{v}\leq \lambda _{1}(T_{d,k})f_{v}$ per $v$ prop de $t$. Llavors pel teorema mín-màx s'obté

$$\lambda _{2}(G)\geq fAf^{T}/\|f\|^{2}\geq \lambda _{1}(T_{d,k})\approx 2{\sqrt {d-1}}\left(1-{\frac {1}{2}}\left({\frac {2\pi }{m}}\right)^{2}\right),$$

tal com es pretenia.

Exemple numèric

Graf de Pappus (3-regular amb 18 vèrtexs). Es comprova que és un graf de Ramanujan mitjançant l'anàlisi dels autovalors de la seva matriu d'adjacència

El gràfic de Pappus és un polígon regular de 18 vèrtexs, en el qual cada vèrtex, a més de tenir els seus dos vèrtexs adjacents, està connectat amb un tercer vèrtex guardant una configuració pròpia.

Això implica que es tracta d'un graf 3-regular, format per 18 vèrtexs. Per comprovar que es tracta d'un graf de Ramanujan, és necessari construir la seva matriu d'adjacència, i analitzar els seus autovalors. Per a això, es parteix d'una matriu de 18x18 (inicialment amb totes les seves cel·les amb valor 0), i es van situant valors 1 en les cel·les que es corresponguin amb alguna connexió en el gràfic. Per exemple, la fila 4 té emplenades amb 1 les columnes 3 i 5 (els dos vèrtexs adjacents al vèrtex 4 en el perímetre del polígon) i la columna 15 (corresponent a la connexió entre els vèrtexs 4 i 15). Una vegada acabat aquest procés d'emplenat de files pels 18 vèrtexs, s'obté una matriu que donades les condicions del polígon, és simètrica, i posseeix tres cel·les amb el número 1 en cada fila i en cada columna.

Per a confirmar si es tracta d'un graf de Ramanujan, és necessari determinar els autovalors $\lambda _{i}$ de la matriu d'adjacència $A$, que compleixen amb la propietat que:

$\det(A-\lambda I)=0\!\$

Per a això, s'ha utilitzat el programa "MATLAB", dissenyat per treballar amb matrius. Determinar aquests 18 $\lambda _{i}$ equival a resoldre un polinomi de grau 18, calculant les seves 18 arrels. Donada la gran simetria de la matriu, el càlcul dels autovalors llança el resultat següent:

• Una vegada -3; sis vegades $-{\sqrt {3}}$; quatre vegades 0; sis vegades ${\sqrt {3}}$; i finalment, una vegada 3

D'acord amb la definició de partida, tots els $\lambda _{i}$ estan compresos entre +d i -d, i atès que d val 3, queda demostrat que el polígon de Pappus és un graf de Ramanujan.

Bibliografia addicional

• Guiliana Davidoff; Peter Sarnak; Alain Valette. Elementary number theory, group theory and Ramanjuan graphs. 55. Cambridge University Press, 2003 (LMS student texts). ISBN 0-521-53143-8. OCLC 50253269. 
• T. Sunada «L-functions in geometry and some applications». Lecture Notes in Math., 1201, 1985, pàg. 266–284. DOI: 10.1007/BFb0075662.

Enllaços externs

• Document d'enquesta de M. Ram Murty