Случайные регулярные графы и теорема Майерса Узнал давеча такой прикольный факт (возможно, неверный). Пусть
N -- какое-то число, и рассмотрим
d-регулярные графы на
N вершинах. Это конечное множество, введём на нём равномерную меру. Тогда ожидание количества несамопересекающихся циклов длины
\sqrt{N} в случайном графе из этого множества стремится к нулю, если
N стремится к бесконечности. Это явно правда при
d = 2, потому что 2-регулярные графы суть просто несвязные объединения циклов и соответствуют диаграммам Юнга, а про них это выглядит как стандартный факт. А вообще не знаю, но вроде как этим вчера пользовался профессор на курсе по случайным графам как известной вещью. Я спросил сейчас у другого студента, который там был -- он сказал, что припоминает, но доказать сходу не может.
А занятно это потому, что это означает, что локально случайный регулярный граф наверняка устроен как дерево. Это позволяет сравнить его с многообразием, которое локально устроено как шар. Значит, радиус
r, про котором
r-окрестность данной вершины перестаёт быть деревом -- это аналог радиуса инъективности, а максимальный радиус инъективности по всем точкам, как мы знаем -- это диаметр. Факт из первого абзаца утверждает, что почти наверняка радиус инъективности в любой точке больше
\sqrt{N}. А теорема Майерса даёт наоборот, верхнюю оценку на диаметр в терминах квадратного корня из величины, ограничивающей снизу кривизну Риччи. Тут конечно правильно говорить про нижнюю оценку на систоли, но я всё равно не нашёл никакого аналогичного результата.
Но вообще странное явление, дерево же типа 'отрицательно закривлено', а шар может иметь и положительную кривизну. Если бы я был поэтом, я бы написал стихотворение про то, что области неотрицательной кривизны следует мыслить как неодносвязные, но на субатомном уровне.
Не знал про Майерса, кстати:
He died unexpectedly from a heart attack during the 1955 Michigan–Army football game at Michigan Stadium.[5]Вкупе с первой картинкой в статье про систолическую геометрию в википедии особенно впечатляюще (впрочем, Майерс не занимался систолической геометрией).
Current Mood: hungryCurrent Music: Edward McDowell -- To a Wild Rose