У спектральній теорії графів граф Рамануджана, названий на честь індійського математика Рамануджана, — це регулярний граф, [en] якого майже настільки велика, наскільки це можливо (див. статтю «Екстремальна теорія графів»). Такі графи є чудовими спектральними експандерами.
Прикладами графів Рамануджана є кліки, повні двочасткові графи та граф Петерсена. Як зауважує Мурті, графи Рамануджана «сплавляють воєдино різні гілки чистої математики, а саме, теорію чисел, теорію представлень та алгебричну геометрію». Як зауважив Тосікадзу Сунада, регулярний граф є графом Рамануджана тоді й лише тоді, коли його [en] задовольняє аналогу гіпотези Рімана.
Визначення
Нехай — зв'язний -регулярний графом із вершинами, а — власні числа матриці суміжності графа . Оскільки граф зв'язний і -регулярний, його власні числа задовольняють нерівності . Якщо існує значення , для котрого , визначимо
-Регулярний граф є графом Рамануджана, якщо .
Граф Рамануджана описується як регулярний граф, [en] якого задовольняє аналогу гіпотези Рімана.
Екстремальність графів Рамануджана
Для фіксованого значення і великого -регулярні графи Рамануджана з вершинами майже мінімізують . Якщо є -регулярним графом із діаметром , теорема Алона стверджує
Якщо є -регулярним і зв'язним принаймні на трьох вершинах, , а тому . Нехай — множина всіх зв'язних -регулярних графів принаймні з вершинами. Оскільки мінімальний діаметр графа в прямує до нескінченності за фіксованого і збільшення , з цієї теореми випливає теорема Алона й Боппана, яка стверджує
Трохи строгіша межа
де . Суть доведення Фрідмана така. Візьмемо . Нехай — -регулярне дерево висоти , і — його матриця суміжності. Ми хочемо довести, що для деякого , що залежить тільки від . Визначимо функцію так: , де є відстанню від до кореня . Вибираючи близьким до , можна довести, що . Тепер нехай і — пара вершин на відстані і визначимо
де — вершина в , відстань від якої до кореня дорівнює відстані від до () і симетрична для . Вибравши відповідні ми отримаємо , для близьких до і для близьких до . Тоді, за теоремою про мінімакс, .
Побудови
Побудови графів Рамануджана часто алгебричні.
- Лубоцькі, Філіпс та Сарнак показали, як побудувати нескінченне сімейство -регулярних графів Рамануджана, коли є простим числом і . Їхнє доведення використовує гіпотезу Рамануджана, звідки й отримали назву графи Рамануджана. Крім властивості бути графами Рамануджана, їхня побудова має низку інших властивостей. Наприклад, обхват дорівнює , де — число вузлів.
- Моргенштерн розширив побудову Лубоцькі, Філліпса та Сарнака. Його побудова допустима, якщо є степенем простого числа.
- Арнольд Піцер довів, що [en] є графами Рамануджана, хоча, як правило, вони мають менший обхват, ніж графи Лубоцькі, Філліпса та Сарнака. Подібно до графів Лубоцькі, Філіпса та Сарнака, степеня цих графів завжди дорівнюють простому числу + 1. Ці графи пропонуються як базис постквантової еліптичної криптографії.
- Адам Маркус, Даніель Спільман та Нікхіл Срівастава довели існування -регулярних двочасткових графів Рамануджана для будь-якого . Пізніше вони довели, що існують двочасткові графи Рамануджана будь-якого степеня та з будь-яким числом вершин. Міхаель Б. Коен показав, як будувати ці графи за поліноміальний час.
Примітки
- M. Ram Murty. Ramanujan Graphs // J. Ramanujan Math. Soc.. — 2003. — Vol. 18, no. 1. — P. 1-20.
- Terras, 2011.
- Nilli, 1991, с. 207–210.
- Lubotzky, Phillips, Sarnak, 1988, с. 261–277.
- Morgenstern, 1994, с. 44–62.
- Pizer, 1990, с. 127–137.
- Eisenträger, Hallgren, Lauter, Morrison, Petit, 2018, с. 329–368.
- Німецьке прізвище і німецькою воно має звучати як Шпільман
- Marcus, Spielman, Srivastava, 2013.
- Marcus, Spielman, Srivastava, 2015.
- Cohen, 2016.
Література
- Audrey Terras. Zeta functions of graphs: A stroll through the garden. — Cambridge University Press, 2011. — Т. 128. — (Cambridge Studies in Advanced Mathematics) — .
- Nilli A. On the second eigenvalue of a graph // . — 1991. — Т. 91, вип. 2 (17 червня). — С. 207–210. — DOI: .
- Alexander Lubotzky, Ralph Phillips, Peter Sarnak. Ramanujan graphs // Combinatorica. — 1988. — Т. 8, вип. 3 (17 червня). — DOI: .
- Moshe Morgenstern. Existence and Explicit Constructions of q+1 Regular Ramanujan Graphs for Every Prime Power q // Journal of Combinatorial Theory, Series B. — 1994. — Т. 62 (17 червня). — DOI: .
- Arnold K. Pizer. Ramanujan graphs and Hecke operators // Bulletin of the American Mathematical Society. — 1990. — Т. 23, вип. 1 (17 червня). — С. 127–137. — (New Series). — DOI: .
- Kirsten Eisenträger, Sean Hallgren, Kristin Lauter, Travis Morrison, Christophe Petit. Supersingular isogeny graphs and endomorphism rings: Reductions and solutions // Advances in Cryptology – EUROCRYPT 2018: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018, Proceedings, Part III / Jesper Buus Nielsen, Vincent Rijmen. — Cham : Springer, 2018. — Т. 10822. — С. 329–368. — (Lecture Notes in Computer Science) — DOI:
- Adam Marcus, Daniel Spielman, Nikhil Srivastava. Interlacing families I: Bipartite Ramanujan graphs of all degrees // Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium. — 2013.
- Adam Marcus, Daniel Spielman, Nikhil Srivastava. Interlacing families 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:
- Guiliana Davidoff, Peter Sarnak, Alain Valette. Elementary number theory, group theory and Ramanjuan graphs. — Cambridge University Press, 2003. — Т. 55. — (LMS student texts) — .
- Sunada T. L-functions in geometry and some applications // Lecture Notes in Math.. — 1985. — Т. 1201 (17 червня). — С. 266–284. — (Lecture Notes in Mathematics). — . — DOI: .
Посилання
- Survey paper by M. Ram Murty Архівовано липень 6, 2011 на сайті Wayback Machine.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U spektralnij teoriyi grafiv graf Ramanudzhana nazvanij na chest indijskogo matematika Ramanudzhana ce regulyarnij graf en yakogo majzhe nastilki velika naskilki ce mozhlivo div stattyu Ekstremalna teoriya grafiv Taki grafi ye chudovimi spektralnimi ekspanderami Prikladami grafiv Ramanudzhana ye kliki povni dvochastkovi grafi Kn n displaystyle K n n ta graf Petersena Yak zauvazhuye Murti grafi Ramanudzhana splavlyayut voyedino rizni gilki chistoyi matematiki a same teoriyu chisel teoriyu predstavlen ta algebrichnu geometriyu Yak zauvazhiv Tosikadzu Sunada regulyarnij graf ye grafom Ramanudzhana todi j lishe todi koli jogo en zadovolnyaye analogu gipotezi Rimana ViznachennyaNehaj G displaystyle G zv yaznij d displaystyle d regulyarnij grafom iz n displaystyle n vershinami a l0 l1 ln 1 displaystyle lambda 0 geqslant lambda 1 geqslant cdots geqslant lambda n 1 vlasni chisla matrici sumizhnosti grafa G displaystyle G Oskilki graf G displaystyle G zv yaznij i d displaystyle d regulyarnij jogo vlasni chisla zadovolnyayut nerivnosti d l0 gt l1 ln 1 d displaystyle d lambda 0 gt lambda 1 geqslant cdots geqslant lambda n 1 geqslant d Yaksho isnuye znachennya li displaystyle lambda i dlya kotrogo li lt d displaystyle lambda i lt d viznachimo l G max li lt d li displaystyle lambda G max lambda i lt d lambda i d displaystyle d Regulyarnij graf G displaystyle G ye grafom Ramanudzhana yaksho l G 2d 1 displaystyle lambda G leqslant 2 sqrt d 1 Graf Ramanudzhana opisuyetsya yak regulyarnij graf en yakogo zadovolnyaye analogu gipotezi Rimana Ekstremalnist grafiv RamanudzhanaDlya fiksovanogo znachennya d displaystyle d i velikogo n displaystyle n d displaystyle d regulyarni grafi Ramanudzhana z n displaystyle n vershinami majzhe minimizuyut l G displaystyle lambda G Yaksho G displaystyle G ye d displaystyle d regulyarnim grafom iz diametrom m displaystyle m teorema Alona stverdzhuye l1 2d 1 2d 1 1 m 2 displaystyle lambda 1 geqslant 2 sqrt d 1 frac 2 sqrt d 1 1 lfloor m 2 rfloor Yaksho G displaystyle G ye d displaystyle d regulyarnim i zv yaznim prinajmni na troh vershinah l1 lt d displaystyle lambda 1 lt d a tomu l G l1 displaystyle lambda G geqslant lambda 1 Nehaj Gnd displaystyle mathcal G n d mnozhina vsih zv yaznih d displaystyle d regulyarnih grafiv G displaystyle G prinajmni z n displaystyle n vershinami Oskilki minimalnij diametr grafa v Gnd displaystyle mathcal G n d pryamuye do neskinchennosti za fiksovanogo d displaystyle d i zbilshennya n displaystyle n z ciyeyi teoremi viplivaye teorema Alona j Boppana yaka stverdzhuye limn infG Gndl G 2d 1 displaystyle lim n to infty inf G in mathcal G n d lambda G geqslant 2 sqrt d 1 Trohi strogisha mezha l1 2d 1 1 cm2 displaystyle lambda 1 geqslant 2 sqrt d 1 cdot left 1 frac c m 2 right de c 2p2 displaystyle c approx 2 pi 2 Sut dovedennya Fridmana taka Vizmemo k m2 1 displaystyle k left lfloor frac m 2 right rfloor 1 Nehaj Td k displaystyle T d k d displaystyle d regulyarne derevo visoti k displaystyle k i ATk displaystyle A T k jogo matricya sumizhnosti Mi hochemo dovesti sho l G l Td k 2d 1cos 8 displaystyle lambda G geqslant lambda T d k 2 sqrt d 1 cos theta dlya deyakogo 8 displaystyle theta sho zalezhit tilki vid m displaystyle m Viznachimo funkciyu g V Td k R displaystyle g V T d k rightarrow mathbb R tak g x d 1 d 2 sin k 1 d 8 displaystyle g x d 1 delta 2 cdot sin k 1 delta theta de d displaystyle delta ye vidstannyu vid x displaystyle x do korenya Td k displaystyle T d k Vibirayuchi 8 displaystyle theta blizkim do 2p m displaystyle 2 pi m mozhna dovesti sho At kg l Td k g displaystyle A t k g lambda T d k g Teper nehaj s displaystyle s i t displaystyle t para vershin na vidstani m displaystyle m i viznachimo f v c1g vs dist v s k c2g vt dist v t k 0 displaystyle f v begin cases c 1 g v s amp amp dist v s leqslant k c 2 g v t amp amp dist v t leqslant k 0 amp end cases de vs displaystyle v s vershina v Td k displaystyle T d k vidstan vid yakoyi do korenya dorivnyuye vidstani vid v displaystyle v do s displaystyle s dist v s displaystyle dist v s i simetrichna dlya vt displaystyle v t Vibravshi vidpovidni c1 c2 displaystyle c 1 c 2 mi otrimayemo f 1 displaystyle f perp 1 Af v l Td k fv displaystyle Af v geqslant lambda T d k f v dlya v displaystyle v blizkih do s displaystyle s i Af v l Td k fv displaystyle Af v leqslant lambda T d k f v dlya v displaystyle v blizkih do t displaystyle t Todi za teoremoyu pro minimaks l G fAfT f 2 l Td k displaystyle lambda G geqslant fAf T f 2 geqslant lambda T d k PobudoviPobudovi grafiv Ramanudzhana chasto algebrichni Lubocki Filips ta Sarnak pokazali yak pobuduvati neskinchenne simejstvo p 1 displaystyle p 1 regulyarnih grafiv Ramanudzhana koli p displaystyle p ye prostim chislom i p 1 mod4 displaystyle p equiv 1 pmod 4 Yihnye dovedennya vikoristovuye gipotezu Ramanudzhana zvidki j otrimali nazvu grafi Ramanudzhana Krim vlastivosti buti grafami Ramanudzhana yihnya pobudova maye nizku inshih vlastivostej Napriklad obhvat dorivnyuye W logp n displaystyle Omega log p n de n displaystyle n chislo vuzliv Morgenshtern rozshiriv pobudovu Lubocki Fillipsa ta Sarnaka Jogo pobudova dopustima yaksho p displaystyle p ye stepenem prostogo chisla Arnold Picer doviv sho en ye grafami Ramanudzhana hocha yak pravilo voni mayut menshij obhvat nizh grafi Lubocki Fillipsa ta Sarnaka Podibno do grafiv Lubocki Filipsa ta Sarnaka stepenya cih grafiv zavzhdi dorivnyuyut prostomu chislu 1 Ci grafi proponuyutsya yak bazis postkvantovoyi eliptichnoyi kriptografiyi Adam Markus Daniel Spilman ta Nikhil Srivastava doveli isnuvannya d displaystyle d regulyarnih dvochastkovih grafiv Ramanudzhana dlya bud yakogo d displaystyle d Piznishe voni doveli sho isnuyut dvochastkovi grafi Ramanudzhana bud yakogo stepenya ta z bud yakim chislom vershin Mihael B Koen pokazav yak buduvati ci grafi za polinomialnij chas PrimitkiM Ram Murty Ramanujan Graphs J Ramanujan Math Soc 2003 Vol 18 no 1 P 1 20 Terras 2011 Nilli 1991 s 207 210 Lubotzky Phillips Sarnak 1988 s 261 277 Morgenstern 1994 s 44 62 Pizer 1990 s 127 137 Eisentrager Hallgren Lauter Morrison Petit 2018 s 329 368 Nimecke prizvishe i nimeckoyu vono maye zvuchati yak Shpilman Marcus Spielman Srivastava 2013 Marcus Spielman Srivastava 2015 Cohen 2016 LiteraturaAudrey Terras Zeta functions of graphs A stroll through the garden Cambridge University Press 2011 T 128 Cambridge Studies in Advanced Mathematics ISBN 978 0 521 11367 0 Nilli A On the second eigenvalue of a graph 1991 T 91 vip 2 17 chervnya S 207 210 DOI 10 1016 0012 365X 91 90112 F Alexander Lubotzky Ralph Phillips Peter Sarnak Ramanujan graphs Combinatorica 1988 T 8 vip 3 17 chervnya DOI 10 1007 BF02126799 Moshe Morgenstern Existence and Explicit Constructions of q 1 Regular Ramanujan Graphs for Every Prime Power q Journal of Combinatorial Theory Series B 1994 T 62 17 chervnya DOI 10 1006 jctb 1994 1054 Arnold K Pizer Ramanujan graphs and Hecke operators Bulletin of the American Mathematical Society 1990 T 23 vip 1 17 chervnya S 127 137 New Series DOI 10 1090 S0273 0979 1990 15918 X Kirsten Eisentrager Sean Hallgren Kristin Lauter Travis Morrison Christophe Petit Supersingular isogeny graphs and endomorphism rings Reductions and solutions Advances in Cryptology EUROCRYPT 2018 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques Tel Aviv Israel April 29 May 3 2018 Proceedings Part III Jesper Buus Nielsen Vincent Rijmen Cham Springer 2018 T 10822 S 329 368 Lecture Notes in Computer Science DOI 10 1007 978 3 319 78372 7 11 Adam Marcus Daniel Spielman Nikhil Srivastava Interlacing families I Bipartite Ramanujan graphs of all degrees Foundations of Computer Science FOCS 2013 IEEE 54th Annual Symposium 2013 Adam Marcus Daniel Spielman Nikhil Srivastava Interlacing families 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 Elementary number theory group theory and Ramanjuan graphs Cambridge University Press 2003 T 55 LMS student texts ISBN 0 521 53143 8 Sunada T L functions in geometry and some applications Lecture Notes in Math 1985 T 1201 17 chervnya S 266 284 Lecture Notes in Mathematics ISBN 978 3 540 16770 9 DOI 10 1007 BFb0075662 PosilannyaSurvey paper by M Ram Murty Arhivovano lipen 6 2011 na sajti Wayback Machine