Граф Рамануджана (Ijgs Jgbgur;'gug)

Перейти к навигации Перейти к поиску

В спектральной теории графов граф Рамануджана, названный по имени индийского математика Рамануджана, — это регулярный граф, спектральная щель[англ.] которого почти настолько велика, насколько это возможно (см. статью «Экстремальная теория графов»). Такие графы являются прекрасными спектральными экспандерами.

Примерами графов Рамануджана служат клики, полные двудольные графы и граф Петерсена. Как замечает Мурти в обзорной статье Архивная копия от 6 июля 2011 на Wayback Machine, графы Рамануджана «сплавляют воедино различные ветви чистой математики, а именно, теорию чисел, теорию представлений и алгебраическую геометрию». Как заметил Тосикадзу Сунада, регулярный граф является графом Рамануджана тогда и только тогда, когда его дзета-функция Ихары[англ.] удовлетворяет аналогу гипотезы Римана[1].

Определение

[править | править код]

Пусть будет связным -регулярным графом с вершинами и пусть будут собственными числами матрицы смежности графа . Поскольку граф связен и -регулярен, его собственные числа удовлетворяют неравенствам . Если существует значение , для которого , определим

-Регулярный граф является графом Рамануджана, если .

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

Экстремальность графов Рамануджана

[править | править код]

Для фиксированного значения и большого -регулярные графы Рамануджана с вершинами почти минимизируют . Если является -регулярным графом с диаметром , теорема Алона[2] утверждает

Если является -регулярным и связным по меньшей мере на трёх вершинах, , а потому . Пусть будет множеством всех связных -регулярных графов по меньшей мере с вершинами. Поскольку минимальный диаметр графа в стремится к бесконечности при фиксированном и увеличивающемся , из этой теоремы следует теорема Алона и Боппана, которая утверждает

Чуть более строгая граница

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

где — вершина в , расстояние от которой до корня равно расстоянию от до () и симметрично для . Путём выбора подходящих мы получим , для близких к и для близких к . Тогда по теореме о минимаксе .

Построения

[править | править код]

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

  • Лубоцки, Филлипс и Сарнак[3] показали, как построить бесконечное семейство -регулярных графов Рамануджана, когда является простым числом и . Их доказательство использует гипотезу Рамануджана, откуда и получили название графы Рамануджана. Кроме свойства быть графами Рамануджана, их построение имеет ряд других свойств. Например, обхват равен , где равно числу узлов.
  • Моргенштерн[4] расширил построение Лубоцки, Филлипса и Сарнака. Его расширенное построение допустимо, если является степенью простого числа.
  • Арнольд Пицер доказал, что суперсингулярные изогении графа[англ.] являются графами Рамануджана, хотя, как правило, они имеют меньший обхват, чем графы Лубоцки, Филлипса и Сарнака[5]. Подобно графам Лубоцки, Филлипса и Сарнака, степени этих графов всегда равны простому числу + 1. Эти графы предлагаются в качестве базиса постквантовой эллиптической криптографии[6].
  • Адам Маркус, Даниэль Спильман[7] и Никхил Сривастава[8] доказали существование -регулярных двудольных графов Рамануджана для любого . Позднее[9] они доказали, что существуют двудольные графы Рамануджана любой степени и с любым числом вершин. Михаэль Б. Коэн[10] показал, каким образом строить эти графы за полиномиальное время.

Примечания

[править | править код]
  1. Terras, 2011.
  2. Nilli, 1991, с. 207–210.
  3. Lubotzky, Phillips, Sarnak, 1988, с. 261–277.
  4. Morgenstern, 1994, с. 44–62.
  5. Pizer, 1990, с. 127–137.
  6. Eisenträger, Hallgren, Lauter, Morrison, Petit, 2018, с. 329–368.
  7. Немецкая фамилия и на немецком она должна звучать как Шпильман
  8. Marcus, Spielman, Srivastava, 2013.
  9. Marcus, Spielman, Srivastava, 2015.
  10. 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. — С. 207–210. — doi:10.1016/0012-365X(91)90112-F.
  • Alexander Lubotzky, Ralph Phillips, Peter Sarnak. Ramanujan graphs // Combinatorica. — 1988. — Т. 8, вып. 3. — 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. — doi:10.1006/jctb.1994.1054.
  • Arnold K. Pizer. Ramanujan graphs and Hecke operators // Bulletin of the American Mathematical Society. — 1990. — Т. 23, вып. 1. — С. 127–137. — 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. — С. 266–284. — ISBN 978-3-540-16770-9. — doi:10.1007/BFb0075662.