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

Замечание о вакантном множестве случайных блужданий на гиперкубе и других регулярных графах высокой степени.

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

 Рассмотрим случайное блуждание наd-регулярный графG гдеd а такжеG Удовлетворяет определенным условиям. Наш главный пример -d-мерный гиперкуб, имеющийn=2d Вершин. Мы исследуем вероятную составную структуру вакантного набора, т.е.E. Множество непосещенных вершин. ПозволятьΛ(t) Подграф, индуцированный свободным множеством шага на шагеt. Покажем, что если выполнены некоторые условия, то графΛ(t) Претерпевает фазовый переход приt=nloged. Наши результаты таковы, что еслиt(1ϵ)t Затем w.часп. Как число вершинn, размерL1(t) Наибольшего компонента удовлетворяетL1logn Тогда как еслиt(1+\e)t тогдаL1(t)=o(logn).

Ссылка на публикацию
Коопер К. , Фриезе А.   Замечание о вакантном множестве случайных блужданий на гиперкубе и других регулярных графах высокой степени. - : , 2014. // arXiv.org, 2014.
Библиография
1.D. Олдос и Дж. Заполните. Обратимые марковские цепи и случайные блуждания по графам, http: // stat-www.Беркели.Edu / pub / users / aldous / RWG / book.Html.
2.Я. Бенджамини и А. Шнитман, Гигантная компонента и свободный набор для случайного блуждания на дискретном торе, Ж. Евро. Математика. Soc., 10 (2008) 1--40.
3.J. ? Черны, А. Тейшейра и Д. Windisch, Гигантская вакансия, оставленная случайным блужданием в случайном d-регулярном графе. Annales de lInstitut Henri Poincar? E (B) Probabilit? Es et Statistiques, 47 (2011) 929--968.
4.J. ? Черны и А. Тейшейра, Критическое окно для свободного множества, оставленного случайным блужданием на случайных регулярных графах, Случайные структуры и алгоритмы, 43 (2013) 313--337.
5.J. ? Черны и А. Тейшейра, От случайных блуждающих траекторий к случайным переплетениям, Sociedade Brasilera de Mathem? Atica, Ensaios Mathem? Aticos, 23 (2012) 1--78.
6.С. Купер и А.М. Frieze, Время покрытия гигантской компоненты случайного графа, Random Structures and Algorithms, 32 (2008) 401-439.
7.С. Купер, А.М. Фриз и Т. Радзик, Время покрытия случайных блужданий на случайных равномерных гиперграфах, Теоретическая информатика, 509 (2013) 51--69.
8.С. Купер и А.М. Фриз, Структура компонент, индуцированная случайным блужданием на случайном графе, Случайные структуры и алгоритмы, 42 (2013) 135-158.
9.С. Купер и А.М. Фриз, Свободные множества и свободные сети: Структуры компонент, индуцированные случайным блужданием. ArXiv: 1404.4403 (2014 г.).
10.W. Феллер, Введение в теорию вероятностей, том I, (Второе издание) Wiley (1960).
11.S. Харт, Замечание о ребрах n-куба, Дискретная математика, 14 (1976) 157-163.
12.D.E.Кнут, Искусство компьютерного программирования, Том 1, Основные алгоритмы, Addison-Wesley, 1968.
13.D. Левин, Y. Перес и Уилмер, Э., Марковские цепи и времена смешивания, AMS, Providence RI, 2009.
14.L. Lov? Asz. Случайные блуждания по графам: обзор. Математические исследования общества Бойяй. Комбинаторика, Пол Эрдсон - Восемьдесят 2: 1-46, Кестхей, Венгрия, 1993 год.
15.T. Вассмер, Фазовый переход для вакантного множества, оставленного случайным блужданием по гигантской компоненте случайного графа. Чтобы появиться в Ann. Inst. ЧАС. Пуанкаре. Статистик. ArXiv: 1308.2548
16.D. Виндиш, Логарифмические компоненты пустого множества для случайного блуждания на дискретном торе, Электронный журнал вероятностей, 13 (2008) 880--897.

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

Портал arXiv.org

Другие публикации этих авторов
1.Миноры случайного двоичного матроида
Коопер К. , Фриезе А. , Педжден В.
2.О случайных порожденных пересекающихся гиперграфах
Бохман Т. , Коопер К. , Фриезе А. , Мартин Р. Р., Русзинкó М.
3.Радужное дерево в случайных орграфах
Бал Д. , Беннетт П. , Коопер К. , Фриезе А. , Праłат П.
4.Время покрытия случайного графа со степенной последовательностью II: Разрешение вершин второй степени
Коопер К. , Фриезе А. , Лубетзку Е.
5.Свободные множества и свободные сети: Структуры компонент, индуцированные случайным блужданием
Коопер К. , Фриезе А.
6.Высота случайногоkДеревья и связанные с ними ветвящиеся процессы
Коопер К. , Фриезе А. , Уехара Р.
7.О длине случайного минимального остовного дерева
Коопер К. , Фриезе А. , Инке Н. , Джансон С. , Спенкер Д.
8.О жадном алгоритме с двумя сопоставлениями и циклах Гамильтона в случайных графах с минимальной степенью не менее трех
Фриезе А.
9.Стационарное распределение и время покрытия случайных блужданий на случайных орграфах
Коопер К. , Фриезе А.
10.Компонентная структура свободного множества, индуцированного случайным блужданием на случайном графе
Коопер К. , Фриезе А.
Другие публикации этой тематики
1.Гауэрс нормы для последовательностей Туэ-Морса и Рудина-Шапиро
Кониекзну Д.
2.Не возвращающая теорема Пойя
Кемптон М.
3.Смешивание ставок случайных блужданий с небольшим возвратом
Киоабă С. М., Ху Ф.
4.На обычных регулярных графах и графиках с симметричным временем
Джеорджакопоулос А.
5.Тестирование Weomorpheiler-Lehman и изоморфизма графов
Доуджлас Б. Л.
6.Детерминированные случайные блуждания на регулярных деревьях
Коопер Д. Д., Доерр Б. , Фриедрикх Т. , Спенкер Д.
7.Компонентная структура свободного множества, индуцированного случайным блужданием на случайном графе
Коопер К. , Фриезе А.
8.Детерминированные случайные блуждания на двумерной сетке
Доерр Б. , Фриедрикх Т.
9.Детерминированные случайные блуждания по целым числам
Коопер Д. Д., Доерр Б. , Спенкер Д. , Тардос Д.
10.Подсчет путей в графах
Бартхолди Л.