Ramanujan gróf

A spektrális gráfelméletben a Ramanujan gráf , amelyet Ramanujan indiai matematikusról neveztek el , egy szabályos gráf , amelynek spektrális rése majdnem a lehető legnagyobb (lásd az " Extremal Graph Theory " című cikket). Az ilyen gráfok kiváló spektrumbővítők .

A Ramanujan gráfok példái a klikkek , a teljes kétoldalú gráfok és a Petersen - gráf . Amint Murthy megjegyzi a Wayback Machine 2011. július 6-án archivált áttekintő cikkében , a Ramanujan grafikonok "összeolvasztják a tiszta matematika különböző ágait , nevezetesen a számelméletet , az ábrázoláselméletet és az algebrai geometriát ". Ahogy Toshikazu Sunada megjegyezte, egy reguláris gráf akkor és csak akkor Ramanujan gráf, ha Ihara zéta függvénye kielégíti a Riemann-hipotézis [1] analógját . $K_{{n,n}}$

Definíció

Legyen egy összefüggő szabályos gráf csúcsokkal és legyen a gráf szomszédsági mátrixának sajátértéke . Mivel a gráf összefüggő és -reguláris, sajátértékei kielégítik az egyenlőtlenségeket . Ha létezik olyan érték , amelyhez , akkor definiáljuk $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$ -A szabályos gráf egy Ramanujan gráf, ha . $G$ $\lambda (G)\leqslant 2{\sqrt {d-1))$

A Ramanujan-gráfot reguláris gráfként írják le, amelynek Ihara zéta függvénye kielégíti a Riemann-hipotézis analógját .

A Ramanujan gráfok szélső része

Rögzített értékű és nagy szabályos csúcsok esetén a Ramanujan gráfok szinte minimalizálják . Ha egy -reguláris gráf átmérővel , akkor Alon [2] tétele kimondja $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 }}.

Ha -reguláris , és legalább három csúcsra kapcsolódik , és ezért . Legyen az összes összefüggő -reguláris gráf halmaza, amelyeknek legalább csúcsai vannak. Mivel a gráf minimális átmérője a végtelenbe hajlik, fix és növekvő , ez a tétel magában foglalja Alon és Boppan tételét, amely kimondja $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- egy}}.

Kicsit szorosabb szegély

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

ahol . Friedman bizonyításának vázlata a következő. Vegyük . Legyen egy szabályos magasságfa és legyen a szomszédsági mátrixa. Be akarjuk bizonyítani, hogy egyesek csak attól függnek . A függvényt a következőképpen definiáljuk , ahol a távolság a gyökétől . Ha közel választjuk , ezt be tudjuk bizonyítani . Most legyen és legyen egy távolsági csúcspár, és határozzuk meg $c\approx 2\pi ^{2}$ $k=\left\lfloor {\frac {m}{2}}\right\rfloor -1$ $T_{d,k}$ $d$ $k$ $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}}

ahol egy csúcs -ben van , a távolság, amelytől a gyökig egyenlő a távolsággal ( ) -ig, és szimmetrikus -ra . A megfelelőek kiválasztásával a közeli és a közeli -t kapjuk . Ezután a minimax tétel alapján . $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})$

Épületek

A Ramanujan gráfok szerkezete gyakran algebrai.

Lubotsky, Phillips és Sarnack [3] megmutatta, hogyan lehet reguláris Ramanujan gráfokból végtelen családot alkotni, amikor egy prímszám és . Bizonyításuk a Ramanujan sejtést használja , innen ered a Ramanujan gráfok elnevezés. Amellett, hogy Ramanujan gráfok, felépítésük számos más tulajdonsággal is rendelkezik. Például a kerülete , ahol egyenlő a csomópontok számával. ${\megjelenítési stílus (p+1)}$ $p$ $p\equiv 1{\pmod {4}}$ $\Omega (\log _{p}(n))$ $n$
Morgenstern [4] kiterjesztette Lubotsky, Phillips és Sarnack építését. Kibővített konstrukciója akkor érvényes, ha főhatvány . $p$
Arnold Pitzer bebizonyította, hogy a gráf szuperszinguláris izogénjei Ramanujan-gráfok, bár általában kisebb kerületűek, mint a Lubotsky-, Phillips- és Sarnak-gráfok [5] . Lubotsky, Phillips és Sarnak gráfjaihoz hasonlóan ezeknek a gráfoknak a foka mindig egyenlő egy prímszámmal + 1. Ezeket a gráfokat javasolták a kvantum- elliptikus kriptográfia alapjául [6] .
Adam Markus, Daniel Speelman [7] és Nikhil Srivastava [8] bebizonyította a -reguláris kétrészes Ramanujan gráfok létezését bármely . Később [9] bebizonyították, hogy léteznek tetszőleges fokozatú és tetszőleges számú csúcsú kétoldalú Ramanujan gráfok. Michael B. Cohen [10] megmutatta, hogyan lehet ezeket a gráfokat polinomiális időben felépíteni. $d$ $d$

Jegyzetek

↑ Terras, 2011 .
↑ Nilli, 1991 , p. 207–210.
↑ Lubotzky, Phillips, Sarnak, 1988 , p. 261–277.
↑ Morgenstern, 1994 , p. 44–62.
↑ Pizer, 1990 , p. 127–137.
↑ Eisenträger, Hallgren, Lauter, Morrison, Petit, 2018 , p. 329–368.
↑ Német vezetéknév, és németül úgy kell hangzani, mint Shpilman
↑ Marcus, Spielman, Srivastava, 2013 .
↑ Marcus, Spielman, Srivastava, 2015 .
↑ Cohen, 2016 .

Irodalom

Audrey Terras. Grafikonok zéta függvényei: Séta a kertben. - Cambridge University Press, 2011. - V. 128. - (Cambridge Studies in Advanced Mathematics). - ISBN 978-0-521-11367-0 .
Nilli A. A gráf második sajátértékéről // Diszkrét matematika . - 1991. - T. 91 , sz. 2 . – S. 207–210 . - doi : 10.1016/0012-365X(91)90112-F .
Alexander Lubotzky, Ralph Phillips, Peter Sarnak. Ramanujan gráfok // Combinatorica. - 1988. - T. 8 , sz. 3 . - doi : 10.1007/BF02126799 .
Moshe Morgenstern. A q + 1 reguláris Ramanujan gráfok létezése és explicit konstrukciói minden q prímhatalomhoz // Journal of Combinatorial Theory, B. sorozat - 1994. - V. 62 . - doi : 10.1006/jctb.1994.1054 .
Arnold K. Pizer. Ramanujan gráfok és Hecke operátorok // Bulletin of the American Mathematical Society. - 1990. - T. 23 , sz. 1 . – S. 127–137 . - doi : 10.1090/S0273-0979-1990-15918-X .
Kirsten Eisenträger, Sean Hallgren, Kristin Lauter, Travis Morrison, Christophe Petit. Szuperszinguláris izogén gráfok és endomorfizmus gyűrűk: redukciók és megoldások // Advances in Cryptology – EUROCRYPT 2018: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Izrael, 2018. április 29. - május 3., Proceedings, III. Jesper Buus Nielsen, Vincent Rijmen. - Cham: Springer, 2018. - T. 10822. - S. 329-368. — (Számítástechnikai előadásjegyzetek). - doi : 10.1007/978-3-319-78372-7_11 .
Adam Marcus, Daniel Spielman, Nikhil Srivastava. Interlacing family I: Bipartite Ramanujan graphs of all fokozat // Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium. — 2013.
Adam Marcus, Daniel Spielman, Nikhil Srivastava. Interlacing family IV: Bipartite Ramanujan graphs of all sizes // Foundations of Computer Science (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. Elemi számelmélet, csoportelmélet és Ramanjuan gráfok. - Cambridge University Press , 2003. - V. 55. - (LMS hallgatói szövegek). — ISBN 0-521-53143-8 .
Sunada T. L-függvények a geometriában és néhány alkalmazásban // Lecture Notes in Math .. - 1985. - T. 1201 . – S. 266–284 . — ISBN 978-3-540-16770-9 . - doi : 10.1007/BFb0075662 .

Linkek

M. Ram Murty felmérési dokumentuma archiválva : 2011. július 6. a Wayback Machine -nél