Ich interessiere mich für Eigenschaften von zufallsgerichteten Graphen mit festem Grad . Ich stelle mir ein Zufallsgraphenmodell vor, in dem jeder Scheitelpunkt die Nachbarn auswählt (z. B. mit Ersetzung)
Frage : Ist etwas über die stationäre Verteilung und Mischzeiten von Zufallsläufen in diesen Zufallsgraphen bekannt (für verschiedene Werte von )?
Ich interessiere mich besonders für den Fall, dass , was einem Modell zufälliger Automaten über einem Booleschen Alphabet entspricht. (Ja, ich weiß, dass diese Diagramme oft nicht miteinander verbunden sind, aber was passiert in einer bestimmten Komponente?) Ich bin mit Teilergebnissen und Ergebnissen über andere Eigenschaften dieser Diagramme zufrieden.
Es scheint, dass sich der größte Teil der Literatur zu Zufallsgraphen auf das Erdős-Rényi-Modell konzentriert, das ganz andere Eigenschaften aufweist als das Modell, an das ich denke.
Antworten:
Im ungerichteten Fall sind zufällige reguläre Graphen Expander mit hoher Wahrscheinlichkeit (nicht für d = 2 , aber ich denke, d ≥ 3 ist ausreichend), was impliziert, dass die Mischzeit von Zufallsläufen O ( log n ) ist . Ich erinnere mich nicht genug an diese Beweise, um zu wissen, ob im gegebenen Fall alles durchgeht (sicherlich sind einige Eigenschaften anders: Die gleichmäßige Verteilung ist nicht mehr stationär), aber es könnte sich lohnen, sie zu untersuchen. Gute Referenzen für Expandergraphen sind Expandergraphen und ihre Anwendungen von Hoory, Linial und Wigderson sowie Pseudozufälligkeit von Vadhan.d d= 2 d≥ 3 O ( logn )
quelle
Kennen Sie die folgenden Arbeiten (und Referenzen darin)? (Es ist auch auf arXiv verfügbar.)
Bohman, T. und Frieze, A. (2009), Hamilton fahren 3-out. Random Structures & Algorithms, 35: 393–417. doi: 10.1002 / rsa.20272
quelle
Suchen Sie immer noch nach dem Problem? Dieses Papier ist eigentlich ein bisschen relevant: Alan Frieze, Páll Melsted und Michael Mitzenmacher, " Eine Analyse des zufälligen Kuckuck-Haschens ", 2009.
quelle