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

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ę.

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.$d$$d=2$$d \ge 3$$O(\log n)$

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

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.