Właściwości losowo ukierunkowanych wykresów z ustalonym kątem końcowym

17

Interesują mnie właściwości losowo ukierunkowanych wykresów o ustalonym out-stopniu d . Wyobrażam sobie losowy model wykresu, w którym każdy wierzchołek wybiera u sąsiadów (powiedzmy z zamiennikiem)

Pytanie : Czy coś wiadomo o rozkładzie stacjonarnym i czasach mieszania losowych spacerów na tych losowych grafach (dla różnych wartości )? d

Szczególnie interesuje mnie przypadek, w którym , co odpowiada modelowi automatów losowych nad alfabetem boolowskim. (Tak, zdaję sobie sprawę, że te wykresy często nie są połączone, ale co dzieje się w danym składniku?) Cieszę się z częściowych wyników i wyników dotyczących innych właściwości tych wykresów.d=2

Wydaje się, że większość literatury na temat losowych wykresów koncentruje się na modelu Erdősa – Rényi, który ma bardzo inne właściwości niż model, o którym myślę.

Lew Reyzin
źródło
Mogę to zaoferować: jeśli wyszukujesz frazę „współczynnik grupowania”, możesz znaleźć więcej powiązanych literatur. Uznałem, że interesują mnie inne rzeczy, więc nie pamiętam szczegółów.
Aaron Sterling
powinieneś poszukać modeli grafów internetowych (zacznij od artykułu Aiello / Chung ( projecteuclid.org/… ) i pracuj dalej). Możliwe, że znajdziesz ciekawe modele wykresów internetowych. Zobacz także ostatnie dzieło Christosa Faloutsosa
Suresh Venkat,
dzięki za wskaźnik - spojrzałem na pracę Chunga i ten artykuł - chociaż rozważają ciekawe modele, niestety nie biorą pod uwagę moich ...
Lev Reyzin
Sugerujesz, aby proces odbywał się z wymianą. Czy to oznacza, że ​​zezwalasz na multidigrafię (z możliwie wieloma łukami od s do t)?
András Salamon,
Zgadza się - w losowym marszu pokonujesz każdą krawędź w sposób ekwiwalentny, a przy wielu łukach zwiększasz prawdopodobieństwo danego przejścia (i my również dopuszczamy pętle własne). Jeśli jednak chcesz odpowiedzieć na pytanie dotyczące wyboru krawędzi bez wymiany, to też jest w porządku.
Lew Reyzin

Odpowiedzi:

10

W przypadku nieukierunkowanym losowe wykresy nieregularne są ekspanderami o wysokim prawdopodobieństwie (nie dla d = 2 , ale myślę, że d 3 wystarcza), co oznacza, że ​​czas mieszania losowych spacerów wynosi O ( log n ) . Nie pamiętam wystarczająco dużo o tych dowodach, aby wiedzieć, czy wszystko przebiega w ukierunkowanym przypadku (z pewnością niektóre właściwości są różne: jednolity rozkład nie jest już stacjonarny), ale warto się temu przyjrzeć. Dobre referencje dla grafów ekspanderów to Grafy ekspanderów i ich zastosowania autorstwa Hoory'ego, Liniala i Wigdersona oraz Pseudorandomnessa autorstwa Vadhana.rere=2)re3)O(logn)

Ian
źródło
Dzięki - to dobra referencja. Widziałem już tę pracę, ale o niej zapomniałem. Z pewnością warto przejrzeć ich dowód.
Lew Reyzin
7

Czy wiesz o następującej pracy (i jej odnośnikach)? (Jest również dostępny w arXiv.)

Bohman, T. i Frieze, A. (2009), Hamilton jeździ cyklicznie w 3 wyjściach. Struktury losowe i algorytmy, 35: 393–417. doi: 10.1002 / rsa.20272

RJK
źródło
dzięki - to ciekawy wynik, ale posiadanie cyklu hamiltonowskiego jest dalekie od rodzaju nieruchomości, o której myślę.
Lew Reyzin
Hm, być może zbyt dosłownie przyjmowałem: „Jestem zadowolony z częściowych wyników i wyników dotyczących innych właściwości tych wykresów”. Wydaje mi się, że model k-out jest bardzo zbliżony do modelu, którym jesteś zainteresowany, a badanie wcześniejszych wyników k-out byłoby owocne, zwłaszcza biorąc pod uwagę, że zarówno hamiltonizm, jak i szybkie mieszanie można uznać za wzmocnione formy łączności w losowe modele wykresów.
RJK
masz rację - jest to rzeczywiście wynik właściwości tych wykresów i być może przydatny. Nie mogę dać ci zaakceptowanej odpowiedzi, ale z pewnością głosuję pozytywnie :)
Lew Reyzin
2

Nadal szukasz problemu? Ten artykuł jest właściwie trochę trafny: Alan Frieze, Páll Melsted i Michael Mitzenmacher, „ Analizy losowego chodzenia po kukułce ”, 2009.

Kaveh
źródło
1
czy masz do tego link?
Suresh Venkat