www.wikidata.uk-ua.nina.az

Граф Рамануджана У спектральній теорії графів граф Рамануджана названий на честь індійського математика Рамануджана це р

Граф Рамануджана

У спектральній теорії графів граф Рамануджана, названий на честь індійського математика Рамануджана, — це регулярний граф, спектральна щілина[en] якого майже настільки велика, наскільки це можливо (див. статтю «Екстремальна теорія графів»). Такі графи є чудовими спектральними експандерами.

Прикладами графів Рамануджана є кліки, повні двочасткові графи та граф Петерсена. Як зауважує Мурті, графи Рамануджана «сплавляють воєдино різні гілки чистої математики, а саме, теорію чисел, теорію представлень та алгебричну геометрію». Як зауважив Тосікадзу Сунада, регулярний граф є графом Рамануджана тоді й лише тоді, коли його дзета-функція Іхари[en] задовольняє аналогу гіпотези Рімана.

Визначення ред.

Нехай — зв'язний -регулярний графом із вершинами, а — власні числа матриці суміжності графа . Оскільки граф зв'язний і -регулярний, його власні числа задовольняють нерівності . Якщо існує значення , для котрого , визначимо

-Регулярний граф є графом Рамануджана, якщо .

Граф Рамануджана описується як регулярний граф, дзета-функція Іхари[en] якого задовольняє аналогу гіпотези Рімана.

Екстремальність графів Рамануджана ред.

Для фіксованого значення і великого -регулярні графи Рамануджана з вершинами майже мінімізують . Якщо є -регулярним графом із діаметром , теорема Алона стверджує

Якщо є -регулярним і зв'язним принаймні на трьох вершинах, , а тому . Нехай — множина всіх зв'язних -регулярних графів принаймні з вершинами. Оскільки мінімальний діаметр графа в прямує до нескінченності за фіксованого і збільшення , з цієї теореми випливає теорема Алона й Боппана, яка стверджує

Трохи строгіша межа

де . Суть доведення Фрідмана така. Візьмемо . Нехай — -регулярне дерево висоти , і — його матриця суміжності. Ми хочемо довести, що для деякого , що залежить тільки від . Визначимо функцію так: , де є відстанню від до кореня . Вибираючи близьким до , можна довести, що . Тепер нехай і — пара вершин на відстані і визначимо

де — вершина в , відстань від якої до кореня дорівнює відстані від до () і симетрична для . Вибравши відповідні ми отримаємо , для близьких до і для близьких до . Тоді, за теоремою про мінімакс, .

Побудови ред.

Побудови графів Рамануджана часто алгебричні.

  • Лубоцькі, Філіпс та Сарнак показали, як побудувати нескінченне сімейство -регулярних графів Рамануджана, коли є простим числом і . Їхнє доведення використовує гіпотезу Рамануджана, звідки й отримали назву графи Рамануджана. Крім властивості бути графами Рамануджана, їхня побудова має низку інших властивостей. Наприклад, обхват дорівнює , де — число вузлів.
  • Моргенштерн розширив побудову Лубоцькі, Філліпса та Сарнака. Його побудова допустима, якщо є степенем простого числа.
  • Арнольд Піцер довів, що суперсингулярні ізогенії графа[en] є графами Рамануджана, хоча, як правило, вони мають менший обхват, ніж графи Лубоцькі, Філліпса та Сарнака. Подібно до графів Лубоцькі, Філіпса та Сарнака, степеня цих графів завжди дорівнюють простому числу + 1. Ці графи пропонуються як базис постквантової еліптичної криптографії.
  • Адам Маркус, Даніель Спільман та Нікхіл Срівастава довели існування -регулярних двочасткових графів Рамануджана для будь-якого . Пізніше вони довели, що існують двочасткові графи Рамануджана будь-якого степеня та з будь-яким числом вершин. Міхаель Б. Коен показав, як будувати ці графи за поліноміальний час.

Примітки ред.

  1. M. Ram Murty. Ramanujan Graphs // J. Ramanujan Math. Soc.. — 2003. — Vol. 18, no. 1. — P. 1-20.
  2. Terras, 2011.
  3. Nilli, 1991, с. 207–210.
  4. Lubotzky, Phillips, Sarnak, 1988, с. 261–277.
  5. Morgenstern, 1994, с. 44–62.
  6. Pizer, 1990, с. 127–137.
  7. Eisenträger, Hallgren, Lauter, Morrison, Petit, 2018, с. 329–368.
  8. Німецьке прізвище і німецькою воно має звучати як Шпільман
  9. Marcus, Spielman, Srivastava, 2013.
  10. Marcus, Spielman, Srivastava, 2015.
  11. Cohen, 2016.

Література ред.

  • Audrey Terras. Zeta functions of graphs: A stroll through the garden. — Cambridge University Press, 2011. — Т. 128. — (Cambridge Studies in Advanced Mathematics) — ISBN 978-0-521-11367-0.
  • Nilli A. On the second eigenvalue of a graph // Discrete Mathematics. — 1991. — Т. 91, вип. 2 (27 жовтня). — С. 207–210. — DOI:10.1016/0012-365X(91)90112-F.
  • Alexander Lubotzky, Ralph Phillips, Peter Sarnak. Ramanujan graphs // Combinatorica. — 1988. — Т. 8, вип. 3 (27 жовтня). — 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. — Т. 62 (27 жовтня). — DOI:10.1006/jctb.1994.1054.
  • Arnold K. Pizer. Ramanujan graphs and Hecke operators // Bulletin of the American Mathematical Society. — 1990. — Т. 23, вип. 1 (27 жовтня). — С. 127–137. — (New Series). — DOI:10.1090/S0273-0979-1990-15918-X.
  • 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: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. — Т. 55. — (LMS student texts) — ISBN 0-521-53143-8.
  • Sunada T. L-functions in geometry and some applications // Lecture Notes in Math.. — 1985. — Т. 1201 (27 жовтня). — С. 266–284. — (Lecture Notes in Mathematics). — ISBN 978-3-540-16770-9. — DOI:10.1007/BFb0075662.

Посилання ред.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
U spektralnij teoriyi grafiv graf Ramanudzhana nazvanij na chest indijskogo matematika Ramanudzhana ce regulyarnij graf spektralna shilina 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 K n n displaystyle K n n ta graf Petersena Yak zauvazhuye Murti 1 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 dzeta funkciya Ihari en zadovolnyaye analogu gipotezi Rimana 2 Zmist 1 Viznachennya 2 Ekstremalnist grafiv Ramanudzhana 3 Pobudovi 4 Primitki 5 Literatura 6 PosilannyaViznachennya red Nehaj G displaystyle G nbsp zv yaznij d displaystyle d nbsp regulyarnij grafom iz n displaystyle n nbsp vershinami a l 0 l 1 l n 1 displaystyle lambda 0 geqslant lambda 1 geqslant cdots geqslant lambda n 1 nbsp vlasni chisla matrici sumizhnosti grafa G displaystyle G nbsp Oskilki graf G displaystyle G nbsp zv yaznij i d displaystyle d nbsp regulyarnij jogo vlasni chisla zadovolnyayut nerivnosti d l 0 gt l 1 l n 1 d displaystyle d lambda 0 gt lambda 1 geqslant cdots geqslant lambda n 1 geqslant d nbsp Yaksho isnuye znachennya l i displaystyle lambda i nbsp dlya kotrogo l i lt d displaystyle lambda i lt d nbsp viznachimo l G max l i lt d l i displaystyle lambda G max lambda i lt d lambda i nbsp d displaystyle d nbsp Regulyarnij graf G displaystyle G nbsp ye grafom Ramanudzhana yaksho l G 2 d 1 displaystyle lambda G leqslant 2 sqrt d 1 nbsp Graf Ramanudzhana opisuyetsya yak regulyarnij graf dzeta funkciya Ihari en yakogo zadovolnyaye analogu gipotezi Rimana Ekstremalnist grafiv Ramanudzhana red Dlya fiksovanogo znachennya d displaystyle d nbsp i velikogo n displaystyle n nbsp d displaystyle d nbsp regulyarni grafi Ramanudzhana z n displaystyle n nbsp vershinami majzhe minimizuyut l G displaystyle lambda G nbsp Yaksho G displaystyle G nbsp ye d displaystyle d nbsp regulyarnim grafom iz diametrom m displaystyle m nbsp teorema Alona 3 stverdzhuye l 1 2 d 1 2 d 1 1 m 2 displaystyle lambda 1 geqslant 2 sqrt d 1 frac 2 sqrt d 1 1 lfloor m 2 rfloor nbsp Yaksho G displaystyle G nbsp ye d displaystyle d nbsp regulyarnim i zv yaznim prinajmni na troh vershinah l 1 lt d displaystyle lambda 1 lt d nbsp a tomu l G l 1 displaystyle lambda G geqslant lambda 1 nbsp Nehaj G n d displaystyle mathcal G n d nbsp mnozhina vsih zv yaznih d displaystyle d nbsp regulyarnih grafiv G displaystyle G nbsp prinajmni z n displaystyle n nbsp vershinami Oskilki minimalnij diametr grafa v G n d displaystyle mathcal G n d nbsp pryamuye do neskinchennosti za fiksovanogo d displaystyle d nbsp i zbilshennya n displaystyle n nbsp z ciyeyi teoremi viplivaye teorema Alona j Boppana yaka stverdzhuye lim n inf G G n d l G 2 d 1 displaystyle lim n to infty inf G in mathcal G n d lambda G geqslant 2 sqrt d 1 nbsp Trohi strogisha mezha l 1 2 d 1 1 c m 2 displaystyle lambda 1 geqslant 2 sqrt d 1 cdot left 1 frac c m 2 right nbsp de c 2 p 2 displaystyle c approx 2 pi 2 nbsp Sut dovedennya Fridmana taka Vizmemo k m 2 1 displaystyle k left lfloor frac m 2 right rfloor 1 nbsp Nehaj T d k displaystyle T d k nbsp d displaystyle d nbsp regulyarne derevo visoti k displaystyle k nbsp i A T k displaystyle A T k nbsp jogo matricya sumizhnosti Mi hochemo dovesti sho l G l T d k 2 d 1 cos 8 displaystyle lambda G geqslant lambda T d k 2 sqrt d 1 cos theta nbsp dlya deyakogo 8 displaystyle theta nbsp sho zalezhit tilki vid m displaystyle m nbsp Viznachimo funkciyu g V T d k R displaystyle g V T d k rightarrow mathbb R nbsp 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 nbsp de d displaystyle delta nbsp ye vidstannyu vid x displaystyle x nbsp do korenya T d k displaystyle T d k nbsp Vibirayuchi 8 displaystyle theta nbsp blizkim do 2 p m displaystyle 2 pi m nbsp mozhna dovesti sho A t k g l T d k g displaystyle A t k g lambda T d k g nbsp Teper nehaj s displaystyle s nbsp i t displaystyle t nbsp para vershin na vidstani m displaystyle m nbsp i viznachimo f v c 1 g v s d i s t v s k c 2 g v t d i s t 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 nbsp de v s displaystyle v s nbsp vershina v T d k displaystyle T d k nbsp vidstan vid yakoyi do korenya dorivnyuye vidstani vid v displaystyle v nbsp do s displaystyle s nbsp d i s t v s displaystyle dist v s nbsp i simetrichna dlya v t displaystyle v t nbsp Vibravshi vidpovidni c 1 c 2 displaystyle c 1 c 2 nbsp mi otrimayemo f 1 displaystyle f perp 1 nbsp A f v l T d k f v displaystyle Af v geqslant lambda T d k f v nbsp dlya v displaystyle v nbsp blizkih do s displaystyle s nbsp i A f v l T d k f v displaystyle Af v leqslant lambda T d k f v nbsp dlya v displaystyle v nbsp blizkih do t displaystyle t nbsp Todi za teoremoyu pro minimaks l G f A f T f 2 l T d k displaystyle lambda G geqslant fAf T f 2 geqslant lambda T d k nbsp Pobudovi red Pobudovi grafiv Ramanudzhana chasto algebrichni Lubocki Filips ta Sarnak 4 pokazali yak pobuduvati neskinchenne simejstvo p 1 displaystyle p 1 nbsp regulyarnih grafiv Ramanudzhana koli p displaystyle p nbsp ye prostim chislom i p 1 mod 4 displaystyle p equiv 1 pmod 4 nbsp 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 log p n displaystyle Omega log p n nbsp de n displaystyle n nbsp chislo vuzliv Morgenshtern 5 rozshiriv pobudovu Lubocki Fillipsa ta Sarnaka Jogo pobudova dopustima yaksho p displaystyle p nbsp ye stepenem prostogo chisla Arnold Picer doviv sho supersingulyarni izogeniyi grafa en ye grafami Ramanudzhana hocha yak pravilo voni mayut menshij obhvat nizh grafi Lubocki Fillipsa ta Sarnaka 6 Podibno do grafiv Lubocki Filipsa ta Sarnaka stepenya cih grafiv zavzhdi dorivnyuyut prostomu chislu 1 Ci grafi proponuyutsya yak bazis postkvantovoyi eliptichnoyi kriptografiyi 7 Adam Markus Daniel Spilman 8 ta Nikhil Srivastava 9 doveli isnuvannya d displaystyle d nbsp regulyarnih dvochastkovih grafiv Ramanudzhana dlya bud yakogo d displaystyle d nbsp Piznishe 10 voni doveli sho isnuyut dvochastkovi grafi Ramanudzhana bud yakogo stepenya ta z bud yakim chislom vershin Mihael B Koen 11 pokazav yak buduvati ci grafi za polinomialnij chas Primitki red M 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 Literatura red Audrey 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 Discrete Mathematics 1991 T 91 vip 2 27 zhovtnya 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 27 zhovtnya 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 27 zhovtnya 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 27 zhovtnya 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 27 zhovtnya S 266 284 Lecture Notes in Mathematics ISBN 978 3 540 16770 9 DOI 10 1007 BFb0075662 Posilannya red Survey paper by M Ram Murty Arhivovano lipen 6 2011 na sajti Wayback Machine Otrimano z https uk wikipedia org w index php title Graf Ramanudzhana amp oldid 36915669