Hrabě Ramanujan

V teorii spektrálních grafů je Ramanujanův graf , pojmenovaný po indickém matematikovi Ramanujanovi , pravidelným grafem , jehož spektrální mezera je téměř co největší (viz článek „ Teorie extrémních grafů “). Takové grafy jsou vynikajícími spektrálními expandéry .

Příklady Ramanujanových grafů jsou kliky , kompletní bipartitní grafy a Petersenův graf . Jak poznamenává Murthy v přehledném článku Archived 6. July 2011 at Wayback Machine , Ramanujanovy grafy „spojují dohromady různé obory čisté matematiky , jmenovitě teorii čísel , teorii reprezentace a algebraickou geometrii “. Jak poznamenal Toshikazu Sunada, pravidelný graf je Ramanujanův graf právě tehdy, když jeho funkce Ihara zeta splňuje analogii Riemannovy hypotézy [1] . $K_{{n,n}}$

Definice

Nechť je spojitý - pravidelný graf s vrcholy a nechť jsou vlastní čísla matice sousednosti grafu . Protože je graf souvislý a pravidelný, jeho vlastní hodnoty uspokojují nerovnosti . Pokud existuje hodnota , pro kterou , definujeme $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$ -Normální graf je Ramanujanův graf, jestliže . $G$ $\lambda (G)\leqslant 2{\sqrt {d-1))$

Ramanujanův graf je popsán jako pravidelný graf, jehož funkce Ihara zeta splňuje analogii Riemannovy hypotézy .

Extremity of the Ramanujan grafs

Pro pevnou hodnotu a velký pravidelný vrchol Ramanujanovy grafy téměř minimalizují . Je-li -regulární graf s průměrem , říká Alonova věta [2] $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 je -regular a připojený alespoň na tři vrcholy, , a proto . Nechť je množina všech spojených -pravidelných grafů s alespoň vrcholy. Protože minimální průměr grafu v inklinuje k nekonečnu jako , pevný a rostoucí , tato věta implikuje Alonovu a Boppanovu větu, která říká $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- jeden}}.

Trochu těsnější okraj

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

kde . Nástin Friedmanova důkazu je následující. Vezměme si . Nechť je pravidelný výškový strom a nechť je jeho matice sousednosti. Chceme dokázat, že pro některé závisí pouze na . Funkci definujeme následovně , kde je vzdálenost od kořene . Když si vybereme blízko , můžeme to dokázat . Nyní nechejte a buďte párem vzdálených vrcholů a definujte $c\cca 2\pi ^{2}$ $k=\left\lfloor {\frac {m}{2}}\right\rfloor -1$ ${\displaystyle 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$ ${\displaystyle 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}}

kde je vrchol v , vzdálenost od kořene se rovná vzdálenosti od do ( ) a je symetrická pro . Výběrem vhodných získáme , pro blízko a pro blízko . Potom pomocí věty o minimaxu . $v_s$ ${\displaystyle T_{d,k))$ $proti$ $s$ $dist(v,s)$ $v_{t}$ ${\displaystyle c_{1},c_{2))$ $f\perp 1$ ${\displaystyle (Af)_{v}\geqslant \lambda (T_{d,k})f_{v))$ $proti$ $s$ ${\displaystyle (Af)_{v}\leqslant \lambda (T_{d,k})f_{v))$ $proti$ $t$ $\lambda (G)\geqslant fAf^{T}/\|f\|^{2}\geqslant \lambda (T_{d,k})$

Budovy

Konstrukce Ramanujanových grafů jsou často algebraické.

Lubotsky, Phillips a Sarnack [3] ukázali, jak sestrojit nekonečnou rodinu -regulárních Ramanujanových grafů, když je prvočíslo a . Jejich důkaz používá Ramanujanův dohad , odtud název Ramanujanovy grafy. Kromě vlastnosti Ramanujanových grafů má jejich konstrukce řadu dalších vlastností. Například obvod je , kde se rovná počtu uzlů. $(p+1)$ $p$ $p\equiv 1{\pmod {4}}$ $\Omega (\log _{p}(n))$ $n$
Morgenstern [4] rozšířil stavbu Lubotského, Phillipse a Sarnaka. Jeho rozšířená konstrukce je platná, pokud je hlavní mocninou . $p$
Arnold Pitzer dokázal, že nadsingulární izogeneze grafu jsou Ramanujanovy grafy, i když zpravidla mají menší obvod než grafy Lubotského, Phillipse a Sarnaka [5] . Stejně jako grafy Lubotského, Phillipse a Sarnaka jsou stupně těchto grafů vždy rovny prvočíslu + 1. Tyto grafy jsou navrženy jako základ postkvantové eliptické kryptografie [6] .
Adam Markus, Daniel Speelman [7] a Nikhil Srivastava [8] prokázali existenci -regulárních bipartitních Ramanujanových grafů pro jakýkoli . Později [9] dokázali, že existují bipartitní Ramanujanovy grafy libovolného stupně a s libovolným počtem vrcholů. Michael B. Cohen [10] ukázal, jak sestavit tyto grafy v polynomiálním čase. $d$ $d$

Poznámky

↑ Terras, 2011 .
↑ Nilli, 1991 , str. 207–210.
↑ Lubotzky, Phillips, Sarnak, 1988 , str. 261–277.
↑ Morgenstern, 1994 , s. 44–62.
↑ Pizer, 1990 , str. 127–137.
↑ Eisenträger, Hallgren, Lauter, Morrison, Petit, 2018 , str. 329–368.
↑ Německé příjmení a v němčině by mělo znít jako Shpilman
↑ Marcus, Spielman, Srivastava, 2013 .
↑ Marcus, Spielman, Srivastava, 2015 .
↑ Cohen, 2016 .

Literatura

Audrey Terrasová. Zeta funkce grafů: Procházka zahradou. - Cambridge University Press, 2011. - V. 128. - (Cambridge Studies in Advanced Mathematics). - ISBN 978-0-521-11367-0 .
Nilli A. O druhém vlastním čísle grafu // Diskrétní matematika . - 1991. - T. 91 , čís. 2 . — S. 207–210 . - doi : 10.1016/0012-365X(91)90112-F .
Alexander Lubotzky, Ralph Phillips, Peter Sarnak. Ramanujanovy grafy // Combinatorica. - 1988. - T. 8 , no. 3 . - doi : 10.1007/BF02126799 .
Moše Morgenstern. Existence a explicitní konstrukce q + 1 pravidelných Ramanujanových grafů pro každou primární mocninu q // Journal of Combinatorial Theory, Series B. - 1994. - V. 62 . - doi : 10.1006/jctb.1994.1054 .
Arnold K. Pizer. Ramanujanovy grafy a Heckeho operátory // Bulletin American Mathematical Society. - 1990. - T. 23 , no. 1 . — S. 127–137 . - doi : 10.1090/S0273-0979-1990-15918-X .
Kirsten Eisenträger, Sean Hallgren, Kristin Lauter, Travis Morrison, Christophe Petit. Grafy supersingulární izogeny a prstence endomorfismu: Redukce a řešení // Pokroky v kryptologii – EUROCRYPT 2018: 37th Annual International Conference on Theory and Applications of Cryptographic Techniques, Tel Aviv, Izrael, 29. dubna - 3. května 2018, Proceedings, Part III / Jesper Buus Nielsen, Vincent Rijmen. - Cham: Springer, 2018. - T. 10822. - S. 329-368. — (Poznámky z informatiky). - doi : 10.1007/978-3-319-78372-7_11 .
Adam Marcus, Daniel Spielman, Nikhil Srivastava. Prokládání rodin I: Bipartitní Ramanujanovy grafy všech stupňů // Základy informatiky (FOCS), 54. výroční symposium IEEE v roce 2013. — 2013.
Adam Marcus, Daniel Spielman, Nikhil Srivastava. Prokládání rodin IV: Bipartitní Ramanujanovy grafy všech velikostí // Základy informatiky (FOCS), 56. výroční sympozium IEEE v roce 2015. — 2015.
Michael B. Cohen. Ramanujanovy grafy v polynomiálním čase // =Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium. - 2016. - doi : 10.1109/FOCS.2016.37 .
Guiliana Davidoff, Peter Sarnak, Alain Valette. Základní teorie čísel, teorie grup a Ramanjuanovy grafy. - Cambridge University Press , 2003. - V. 55. - (Studentské texty LMS). — ISBN 0-521-53143-8 .
Sunada T. L-funkce v geometrii a některých aplikacích // Lecture Notes in Math .. - 1985. - T. 1201 . — S. 266–284 . — ISBN 978-3-540-16770-9 . - doi : 10.1007/BFb0075662 .

Odkazy

Průzkumný dokument M. Ram Murty Archivováno 6. července 2011 na Wayback Machine