Kreivi Ramanujan

Spektrigrafiikkateoriassa intialaisen matemaatikon Ramanujanin mukaan nimetty Ramanujan - graafi on säännöllinen graafi , jonka spektrirako on melkein mahdollisimman suuri (katso artikkeli " Extremal Graph Theory "). Tällaiset graafit ovat erinomaisia spektrin laajentajia .

Esimerkkejä Ramanujan-graafista ovat klikkit , täydelliset kaksiosaiset graafit ja Petersen-graafi . Kuten Murthy huomauttaa yleiskatsausartikkelissa, joka on arkistoitu 6. heinäkuuta 2011 Wayback Machinessa , Ramanujan-kaaviot "sulauttavat yhteen puhtaan matematiikan eri haarat , nimittäin lukuteorian , esitysteorian ja algebrallisen geometrian ." Kuten Toshikazu Sunada huomautti, säännöllinen graafi on Ramanujan-graafi, jos ja vain jos sen Ihara zeta -funktio täyttää Riemannin hypoteesin [1] analogin . $K_{{n,n}}$

Määritelmä

Olkoon yhdistetty -säännöllinen graafi, jossa on pisteet ja olkoon graafin vierekkäisyysmatriisin ominaisarvot . Koska graafi on yhdistetty ja -säännöllinen, sen ominaisarvot täyttävät epäyhtälöt . Jos on olemassa arvo , jolle , määrittelemme $G$ $d$ $n$ ${\displaystyle \lambda _{0}\geqslant \lambda _{1}\geqslant \cdots \geqslant \lambda _{n-1))$ $G$ $G$ $d$ $d=\lambda _{0}>\lambda _{1}\geqslant \cdots \geqslant \lambda _{n-1}\geqslant -d$ $\lambda _{i}$ $|\lambda _{i}|<d$

\lambda (G)=\max _{|\lambda _{i}|<d}|\lambda _{i}|.\,

$d$ -Säännöllinen graafi on Ramanujan-graafi, jos . $G$ $\lambda (G)\leqslant 2{\sqrt {d-1))$

Ramanujan-graafia kuvataan säännöllisenä graafina, jonka Ihara zeta -funktio täyttää Riemannin hypoteesin analogin .

Ramanujan-kaavioiden ääripää

Kiinteän arvon ja suuren säännöllisen kärjen kohdalla Ramanujan-graafit melkein minimoivat . Jos on -säännöllinen kuvaaja, jonka halkaisija on , Alonin lause [2] toteaa $d$ $n$ $d$ $n$ $\lambda (G)$ $G$ $d$ $m$

\lambda _{1}\geqslant 2{\sqrt {d-1}}-{\frac {2{\sqrt {d-1}}-1}{\lfloor m/2\rfloor }}.

If on -säännöllinen ja kytketty vähintään kolmeen kärkeen , ja siksi . Antaa olla joukko yhdistettyjä -säännöllisiä kaavioita , joissa on vähintään pisteitä. Koska graafin minimihalkaisija in pyrkii äärettömyyteen , kiinteänä ja kasvavana , tämä lause viittaa Alonin ja Boppanin lauseeseen, jossa todetaan $G$ $d$ $|\lambda _{1}|<d$ ${\displaystyle \lambda (G)\geqslant \lambda _{1))$ ${\mathcal {G}}_{n}^{d}$ $d$ $G$ $n$ ${\mathcal {G}}_{n}^{d}$ $d$ $n$

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

Hieman tiukempi reunus

\lambda _{1}\geqslant 2{\sqrt {d-1}}\cdot \left(1-{\frac {c}{m^{2}}}\oikea),

missä . Friedmanin todisteen pääpiirteet ovat seuraavat. Otetaan . Antaa olla säännöllinen korkeuspuu ja olla sen viereisyysmatriisi. Haluamme todistaa, että joillekin riippuu vain . Määrittelemme funktion seuraavasti , missä on etäisyys funktion juureen . Valitsemalla lähellä , voimme todistaa sen . Olkoon nyt ja olla pari kärkipisteitä etäisyyden päässä ja määritellä $c\approx 2\pi ^{2}$ $k=\left\lfloor {\frac {m}{2}}\right\rfloor -1$ $T_{d,k}$ $d$ $k$ ${\näyttötyyli A_{T_{k))}$ $\lambda (G)\geqslant \lambda (T_{d,k})=2{\sqrt {d-1}}\cos \theta$ $\theta$ $m$ $g:V(T_{d,k})\rightarrow \mathbb {R}$ $g(x)=(d-1)^{-\delta /2}\cdot \sin((k+1-\delta )\theta )$ $\delta$ $x$ $T_{d,k}$ $\theta$ $2\pi /m$ $A_{t,k}g=\lambda (T_{d,k})g$ $s$ $t$ $m$

f(v)={\begin{cases}c_{1}g(v_{s})&&dist(v,s)\leqslant k,\\-c_{2}g(v_{t})&&dist (v,t)\leqslant k,\\0&\end{cases}}

jossa on kärki , etäisyys, josta juureen on yhtä suuri kuin etäisyys kohteesta ( ) ja on symmetrinen . Valitsemalla sopivat saamme , lähelle ja lähelle . _ Sitten minimax-lauseen mukaan . $v_s$ $T_{d,k}$ $v$ $s$ $dist(v,s)$ $v_{t}$ ${\displaystyle c_{1},c_{2))$ $f\perp 1$ ${\displaystyle (Af)_{v}\geqslant \lambda (T_{d,k})f_{v))$ $v$ $s$ ${\displaystyle (Af)_{v}\leqslant \lambda (T_{d,k})f_{v))$ $v$ $t$ $\lambda (G)\geqslant fAf^{T}/\|f\|^{2}\geqslant \lambda (T_{d,k})$

Rakennukset

Ramanujan-graafien rakenteet ovat usein algebrallisia.

Lubotsky, Phillips ja Sarnack [3] osoittivat, kuinka luodaan ääretön perhe -säännöllisiä Ramanujan-kaavioita, kun on alkuluku ja . Heidän todistuksessaan käytetään Ramanujan-oletusta , mistä johtuu nimi Ramanujan-graafit. Ramanujan-graafien ominaisuuden lisäksi niiden rakenteessa on monia muita ominaisuuksia. Esimerkiksi ympärysmitta on , jossa on yhtä suuri kuin solmujen lukumäärä. ${\näyttötyyli (p+1)}$ $s$ $p\equiv 1{\pmod {4}}$ $\Omega (\log _{p}(n))$ $n$
Morgenstern [4] laajensi Lubotskyn, Phillipsin ja Sarnackin rakentamista. Sen laajennettu rakenne on voimassa, jos se on päävoima . $s$
Arnold Pitzer osoitti, että graafin supersingulaariset isogeniat ovat Ramanujan-grafioita, vaikka niiden ympärysmitta on yleensä pienempi kuin Lubotskyn, Phillipsin ja Sarnakin graafit [5] . Kuten Lubotskyn, Phillipsin ja Sarnakin graafit, näiden graafien asteet ovat aina yhtä suuria kuin alkuluku + 1. Näitä kaavioita ehdotetaan kvanttielliptisen kryptografian perustaksi [6] .
Adam Markus, Daniel Speelman [7] ja Nikhil Srivastava [8] osoittivat -säännöllisten kaksiosaisten Ramanujan-graafien olemassaolon mille tahansa . Myöhemmin [9] he osoittivat, että on olemassa minkä tahansa asteisia kaksiosaisia Ramanujan-grafioita, joilla on mikä tahansa määrä pisteitä. Michael B. Cohen [10] osoitti, kuinka nämä graafit rakennetaan polynomiajassa. $d$ $d$

Muistiinpanot

↑ Terras, 2011 .
↑ Nilli, 1991 , s. 207–210.
↑ Lubotzky, Phillips, Sarnak, 1988 , s. 261-277.
↑ Morgenstern, 1994 , s. 44–62.
↑ Pizer, 1990 , s. 127-137.
↑ Eisenträger, Hallgren, Lauter, Morrison, Petit, 2018 , s. 329-368.
↑ Saksalainen sukunimi ja saksaksi sen pitäisi kuulostaa Shpilmanilta
↑ Marcus, Spielman, Srivastava, 2013 .
↑ Marcus, Spielman, Srivastava, 2015 .
↑ Cohen, 2016 .

Kirjallisuus

Audrey Terras. Kaavioiden Zeta-funktiot: Kävely puutarhassa. - Cambridge University Press, 2011. - V. 128. - (Cambridge Studies in Advanced Mathematics). - ISBN 978-0-521-11367-0 .
Nilli A. Graafin toisesta ominaisarvosta // Diskreetti matematiikka . - 1991. - T. 91 , no. 2 . — S. 207–210 . - doi : 10.1016/0012-365X(91)90112-F .
Alexander Lubotzky, Ralph Phillips, Peter Sarnak. Ramanujan-kaaviot // Combinatorica. - 1988. - T. 8 , no. 3 . - doi : 10.1007/BF02126799 .
Moshe Morgenstern. q + 1:n säännöllisen Ramanujan-graafin olemassaolo ja eksplisiittiset rakenteet jokaiselle alkuvoimalle q // Journal of Combinatorial Theory, Series B. - 1994. - V. 62 . - doi : 10.1006/jctb.1994.1054 .
Arnold K. Pizer. Ramanujan-graafit ja Hecke-operaattorit // Bulletin of the American Mathematical Society. - 1990. - T. 23 , no. 1 . — S. 127–137 . - doi : 10.1090/S0273-0979-1990-15918-X .
Pääosissa Kirsten Eisenträger, Sean Hallgren, Kristin Lauter, Travis Morrison, Christophe Petit. Supersingulaariset isogeniakaaviot ja endomorfismirenkaat: Reductions and Solutions // Advances in Cryptology – EUROCRYPT 2018: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, 29. huhtikuuta - 3. toukokuuta 2018, osa III / Proceedings Jesper Buus Nielsen, Vincent Rijmen. - Cham: Springer, 2018. - T. 10822. - S. 329-368. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - doi : 10.1007/978-3-319-78372-7_11 .
Adam Marcus, Daniel Spielman, Nikhil Srivastava. Lomittavat perheet I: Kaikkien asteiden kaksipuoliset Ramanujan-graafit // Tietojenkäsittelytieteen perusteet (FOCS), 2013 IEEE 54th Annual Symposium. – 2013.
Adam Marcus, Daniel Spielman, Nikhil Srivastava. Lomitusperheet IV: Kaikenkokoiset kaksipuoliset Ramanujan-graafit // Tietojenkäsittelytieteen perusteet (FOCS), 2015 IEEE 56th Annual Symposium. – 2015.
Michael B. Cohen. Ramanujan Graphs in Polynomial Time // =Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium. - 2016. - doi : 10.1109/FOCS.2016.37 .
Guiliana Davidoff, Peter Sarnak, Alain Valette. Alkeislukuteoria, ryhmäteoria ja Ramanjuan-graafit. - Cambridge University Press , 2003. - V. 55. - (LMS-opiskelijoiden tekstit). — ISBN 0-521-53143-8 .
Sunada T. L-funktiot geometriassa ja eräissä sovelluksissa // Matematiikan luentomuistiinpanot .. - 1985. - T. 1201 . — S. 266–284 . — ISBN 978-3-540-16770-9 . - doi : 10.1007/BFb0075662 .

Linkit

M. Ram Murtyn kyselypaperi Arkistoitu 6. heinäkuuta 2011 Wayback Machinessa