Свойства случайно ориентированных графов с фиксированной степенью выхода

17

Меня интересуют свойства случайных ориентированных графов с фиксированной степенью d . Я представляю модель случайного графа, где каждая вершина выбирает d соседей (скажем, с заменой) uar

Вопрос : Известно ли что-нибудь о стационарном времени распределения и перемешивания случайных блужданий на этих случайных графах (для различных значений )? d

Меня особенно интересует случай, когда , что соответствует модели случайных автоматов над булевым алфавитом. (Да, я понимаю, что эти графы часто не связаны, но что происходит в данном компоненте?) Я доволен частичными результатами и результатами о других свойствах этих графов.d=2

Кажется, что большая часть литературы по случайным графам сосредоточена на модели Эрдеша – Реньи, которая обладает свойствами, совершенно отличными от модели, о которой я думаю.

graph-theory co.combinatorics automata-theory random-walks Лев Рейзин
источник
Я могу предложить это: если вы ищете фразу «коэффициент кластеризации», вы можете найти больше литературы, которая имеет отношение. Я решил, что меня интересуют другие вещи, поэтому я не помню подробностей.
Аарон Стерлинг
Вам следует искать модели веб-графиков (начните с статьи Айелло / Чунга ( projecteuclid.org/… ) и продолжайте работать). Возможно, вы найдете интересные модели веб-графиков. Также посмотрите на недавнюю работу Кристоса Фалуцоса
Суреш Венкат
спасибо за указатель - я посмотрел на работу Чунга и эту статью - хотя они и рассматривают интересные модели, они, к сожалению, не считают мои ...
Лев Рейзин
Вы предполагаете, что процесс происходит с заменой. Означает ли это, что вы разрешаете мультидиграф (возможно, с несколькими дугами от s до t)?
Андрас Саламон
Это верно - в случайном блуждании вы берете каждое ребро равновероятно, а с несколькими дугами вы увеличиваете вероятность данного перехода (и мы также допускаем самостоятельные петли). Однако, если вы хотите ответить на вопрос о выборе ребер без замены, это тоже хорошо.
Лев Рейзин

Ответы:

10

В неориентированном случае случайные регулярные графы являются расширителями с высокой вероятностью (не для d = 2 , но я думаю, что d ≥ 3 достаточно), что означает, что время смешивания случайных блужданий равно O ( log n ) . Я не помню достаточно об этих доказательствах, чтобы знать, проходит ли все в направленном случае (конечно, некоторые свойства различны: равномерное распределение больше не является стационарным), но это может стоить изучить. Хорошими ссылками на графы расширителей являются графы расширителей и их приложения от Hoory, Linial и Wigderson, а также от псевдослучайности от Vadhan.ddзнак равно2d≥3О(журнал⁡N)

Ян
источник
Спасибо - это хорошая ссылка. Я видел эту работу раньше, но забыл об этом. Это, безусловно, стоит пройти через их доказательство.
Лев Рейзин
7

Знаете ли вы о следующей работе (и ссылки в ней)? (Это также доступно на arXiv.)

Bohman, T. and Frieze, A. (2009), циклы Гамильтона в 3 выхода. Случайные структуры и алгоритмы, 35: 393–417. doi: 10.1002 / rsa.20272

RJK
источник
спасибо - это интересный результат, но наличие гамильтонова цикла далеко от того типа имущества, о котором я думаю.
Лев Рейзин
Хм, возможно, я слишком буквально воспринял «Я доволен частичными результатами и результатами о других свойствах этих графиков». Мне кажется, что модель k-out очень близка к интересующей вас модели, и исследование прошлых результатов по k-out было бы плодотворным, особенно если учесть, что как гамильтоновость, так и быстрое смешивание можно считать усиленными формами связности в модели случайных графов.
RJK
Вы правы - это действительно результат свойства этих графиков и, возможно, полезный. Я не могу дать вам принятый ответ, но, конечно, выговор :)
Рейзин Лев