Эта страница переведена с помощью средств машинного перевода. Смотреть оригинал

Невозвратные случайные блуждания и взвешенная теорема Ихара.

Авторы
ИзданиеarXiv.org.
Год издания2016

 Мы изучаем скорость перемешивания случайных блужданий без возврата на графиках, рассматривая невозвратные блуждания как прогулки по направленным ребрам графа. Результат, известный как теорема Ихара, связывает матрицу смежности графа с матрицей, относящуюся к невозвратным блужданиям по направленным ребрам. Докажем взвешенную версию теоремы Ихара, которая связывает матрицу вероятности перехода невозвратного блуждания с матрицей перехода для обычного случайного блуждания. Это позволяет нам определить спектр матрицы вероятности перехода невозвратного случайного блуждания в случае регулярных графов и бирегулярных графов. Как следствие, мы получаем результат Алон и др. Al. Что в большинстве случаев случайное блуждание без возврата по регулярному графу имеет более быструю скорость смешивания, чем обычное случайное блуждание. Кроме того, аналогичный результат получается для бирегулярных графов.

 15 страниц

Ссылка на публикацию
Кемптон М.   Невозвратные случайные блуждания и взвешенная теорема Ихара. - : , 2016. // arXiv.org, 2016.
Библиография
1.N. Алон, я. Бенджамини, Э. Лубецкий и С. Sodin, случайные блуждания без возвратов смешиваются быстрее, Communications in Contemporary Mathematics, 09, (2007) 585.
2.O. Angel, J. Фридман и С. Hoory, Спектр без обратного возврата универсального покрытия графа, Труды Американского математического общества, 326 (6), (2015) 4287--4318.
3.ЧАС. Басс, дзета-функция Ихара-Сельберга древовидной решетки, Internat. J. Математика., 3 (1992), 717-797.
4.F. Чанга, Лапласиана и неравенство Чигера для ориентированных графов, Анналы комбинаторики, 9 (2005), 1--19.
5.F. Чунг, Теория спектральных графов, AMS Publications, 1997.
6.К. Фэн и У.-C. W. Ли, Спектры гиперграфов и приложений, Журнал теории чисел, 60 (1), (1996) 1- 22.
7.Р. Фицнер и Р. Ван дер Хофстад, случайное блуждание без возврата, Дж. Stat. Phys., 150 (2), (2013) 264-284.
8.К. Хишимото, L-функтоны Артина и теорема плотности для простых циклов на конечных графах, Internat. J. Математика., 3 (1992), 809-826.
9.Y. Ихара, О дискретных подгруппах двух на две проективные линейные группы над p-адическими полями, J. Математика. Soc. Japan, 18 (1966), 219-235.
10.М. Котани и Т. Сунада, Дзета-функции конечных графов, Ж. Математика. Sci. Univ. Токио, 7 (2000), 7-25.
11.F. Кржакала, С. Мур, Э. Моссел, Дж. Нееман, А. Sly, L. Здеборова и П. Чжан, Спектральный выкуп в кластеризации редких сетей, Труды Национальной академии наук, 110 (52), (2013) 20935--20940.
12.W.-C. W. Ли и П. Sol? E, Спектры регулярных графов и гиперграфов и ортогональных многочленов. European Journal of Combinatorics, 17 (5), (1996) 461-477.
13.L. Lov? Asz, Случайные блуждания по графам: обзор, Комбинаторика, Пол Эрд "os - Восемьдесят (Том 2), Кестхей (Венгрия) (1993)1-46.
14.A. Nilli, На втором собственном знаке графа. Дискретная математика., 91 (1991), 207-210.
15.ЧАС. М. Старк и А. A. Террас, Дзета-функции конечных графов и покрытий, Успехи математических наук, 121, (1996) 124-165.

Эта публикация на других ресурсах

Портал arXiv.org