Amplitude zufälliger kubischer Graphen

Betrachten Sie einen zusammenhängenden zufälligen kubischen Graphen $G=(V,E)$ von $n =|V|$ Eckpunkte, gezeichnet aus $G(n, 3$ reg $)$ (wie hier definiert , dh $3n$ ist gerade und zwei beliebige Graphen haben die gleiche Wahrscheinlichkeit).

Natürlich gibt es möglich Breadth sucht zuerst, eine für jeden Startknoten . A Breitensuche beginnend am Knoten weist jedem Knoten eine Ebene zu , wobei der Abstand zwischen und in . $n$ $s \in V$ $B_G$ $s \in V$ $d(s, v)$ $v \in V$ $d(s, v)$ $s$ $v$ $G$

$B_G$

L (s, {u, v}) = max {d (s, u), d (s, v)}

$L(s, \{u,v\}) = \max\{ d(s,u), d(s,v) \}$

e = {u, v} \in E

$e=\{u,v\} \in E$

Bei einer bestimmten Breitensuche sei die Anzahl der Kanten, denen die Ebene zugewiesen wurde , und . Mit anderen Worten, ist die Anzahl der Kanten der Ebene, die mehr Kanten enthält als jede andere Ebene. Schließlich sei sein , die maximale für eine der Breadth - First - Durchsuchung von . $B_G$ $\alpha(B_G,i)$ $i$ $\alpha(B_G) = max_i\{\alpha(B_G,i)\}$ $\alpha(B_G)$ $\alpha(G)$ $\alpha(B_G)$ $n$ $G$

Erinnern wir uns die Amplitude von . $\alpha(G)$ $G$

Frage

Wie wächst der erwartete Wert von , wenn gegen unendlich tendiert? Daran erinnern , dass ist kubisch zufällig . Genauer gesagt möchte ich wirklich wissen, ob der erwartete Wert von zu . $\alpha(G)$ $n$ $G$ $\alpha(G)$ $o(n)$

Da ist, wird die Grenze berücksichtigt, so dass ich mich nicht für ungerade interessiere . $n$ $n$

graph-theory co.combinatorics Giorgio Camerani
quelle

(1) Bitte geben Sie an, aus welcher Wahrscheinlichkeitsverteilung Sie Ihren kubischen Graphen zeichnen. (2) Interessieren Sie sich für die Erwartung von als Funktion von oder etwas anderem? (3) Ich nehme an, ist gerade (ansonsten existiert kein kubischer Graph). Ich nehme an, das Limit wird berücksichtigt, damit Sie sich nicht für ungerade interessieren .

α (G)

$\alpha(G)$

n

$n$

n

$n$

n

$n$

Yoshio Okamoto

@YoshioOkamoto: (1) Aus -reg wie in stanford.edu/class/msande337/notes/… definiert ( ist gerade und zwei beliebige Graphen haben die gleiche Wahrscheinlichkeit). (2) Ich habe die Frage bereichert, um diesen Punkt zu klären. (3) Ja, ist gerade und die Grenze wird berücksichtigt, so dass ich mich nicht für ungerade interessiere .

G (n, 3

$G(n, 3$

)

$)$

3 n

$3n$

n

$n$

n

$n$

Giorgio Camerani

@ SureshVenkat: Danke, dass Sie die Lesbarkeit der Frage verbessert haben

;-)

Lassen Sie mich sagen, dass es sehr wahrscheinlich ist, dass Konzentrationsergebnisse für in zufälligen kubischen Graphen vorliegen, was bedeutet, dass der erwartete Wert, der Wert mit hoher Wahrscheinlichkeit usw. alle gleich sind. Wenn das OP nicht klarstellt, denke ich, dass eine Antwort auf eine dieser Fragen eine vernünftige Antwort auf diese Frage wäre.

α (G)

$\alpha(G)$

Peter Shor

@WalterBishop: Lassen Sie mich noch eine Frage stellen. Wie definieren Sie wenn ist?

α (G)

$\alpha(G)$

G

$G$

Yoshio Okamoto

Antworten:

Die Amplitude für Expandergraphen. Ein zufälliger 3-regulärer Graph ist asymptotisch fast sicher ein Expander-Graph (siehe Wikipedia) , daher ist die Erwartung der Amplitude , da die Wahrscheinlichkeit, dass es sich nicht um einen Expander-Graph handelt, auf geht, wenn auf . $\alpha(n) = \Theta(n)$ $\Theta(n)$ $0$ $n$ $\infty$

Für einen Expander Graph mit dem Parameter , für jeden Satz von Eckpunkt mit , es gibt Nachbarn des Satzes. Nun wollen wir die Anzahl der Ecken auf Ebene sein , mit . Wir haben dann aus der Erweiterungseigenschaft, dass solange nicht zu groß ist (dh wir haben noch nicht die Hälfte der Eckpunkte eingeschlossen) nun nach der Ebene die den Scheitelpunkt . Das heißt, also und $\beta$ $s$ $s \leq n/2$ $\beta s$ $j$ $\ell_j$ $\ell_0=1$ $j$

ℓ_{j} \geq β \sum_{i = 0}^{j - 1} ℓ_{i}

$\ell_j \geq \beta\, \sum_{i=0}^{j-1} \ell_{i}$

ℓ_{j}

$\ell_j$

\frac{n}{3}

$\frac{n}{3}$

\sum_{i = 0}^{j - 1} ℓ_{i} < n / 3

$\sum_{i=0}^{j-1} \ell_i < n/3$

\sum_{i = 0}^{j} ℓ_{i} \geq n / 3

$\sum_{i=0}^{j} \ell_i \geq n/3$ . Wenn diese Ebene groß ist, dh , sind wir fertig. Andernfalls hat die nächste Ebene die Größe und wir sind fertig.

ℓ_{j} \geq n / 6

$\ell_j \geq n/6$

ℓ_{j + 1} \geq β \sum_{i = 0}^{j} ℓ_{i} \geq β \frac{n}{3},

$\ell_{j+1} \geq \beta \, \sum_{i=0}^{j} \ell_{i} \geq \beta \frac{n}{3},$

Während dieser Beweis eher die Anzahl der Scheitelpunkte in einer Ebene als die Anzahl der Kanten (nach denen das OP gefragt hat) betrachtet, werden in Schritt immer mindestens so viele Kanten hinzugefügt wie Scheitelpunkte in Ebene , da jeder Scheitelpunkt erreicht werden muss durch eine Kante. $i$ $i$

Peter Shor
quelle

Danke für deine Antwort! Dies ist sehr überraschend (zumindest für mich): Selbst wenn die Gesamtzahl der Kanten und die Anzahl der Ebenen , am meisten Überfüllte Ebene hat noch Kanten. Daher sind die Kanten nicht gleichmäßig auf die Ebenen verteilt: Meine (empirische, falsche) Intuition war, dass es bis auf wenige Anfangsebenen und wenige Endebenen zentrale Ebenen geben sollte, unter denen sich die Kanten befinden würden wurden etwas gleichmäßig verstreut.

m = 1.5 \cdot n \in Θ (n)

$m = 1.5 \cdot n \in \Theta(n)$

Ω (l o g (n))

$\Omega(log(n))$

Θ (n)

$\Theta(n)$

Ω (l o g (n))

$\Omega(log(n))$

Giorgio Camerani

Mit "empirisch" meinen Sie, Sie haben tatsächlich Tests durchgeführt? ist ungefähr für kubische Zufallsgraphen, siehe ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/Bol88.pdf

β

$\beta$

0.1845

$0.1845$

didest

Ja, ich habe Tests von bis und die Menge gemessen . Wenn genähert als erhöht, würde dies empirische Beweise gegeben , dass . Um war ungefähr , während um , ungefähr (natürlich habe ich diese Zahlen nie als empirischen Beweis angesehen, da immer noch zu klein ist, um eine Asymptotik darzustellen). Als ich jedoch "empirische Intuition" sagte

n = 100

$n = 100$

n = 150000

$n = 150000$

k = \frac{α (G)}{m}

$k = \frac{\alpha(G)}{m}$

k

$k$

0

$0$

n

$n$

α (G) \in o (n)

$\alpha(G) \in o(n)$

n = 100

$n=100$

k

$k$

0.3

$0.3$

n = 150000

$n=150000$

k

$k$

0.26

$0.26$

n = 150000

$n = 150000$

Giorgio Camerani

... Ich meinte eher ein echtes (falsches) Gefühl als das Ergebnis der Tests: Ich hatte das Gefühl, dass diese BFS eine "Wurst" -Form haben müssen (dh an den Extremen winzig und in der Mitte konstant kitzlig). "Sie müssen so sein", dachte ich. Der obige Beweis zeigt, wie einfach falsch meine Intuition war. Trotzdem bin ich immer noch überrascht: Kanten, Ebenen, aber nicht Kanten auf jeder Ebene.

Θ (n)

$\Theta(n)$

Ω (l o g (n))

$\Omega(log(n))$

O (\frac{n}{l o g (n)})

$O(\frac{n}{log(n)})$

Giorgio Camerani

Die Antwort von Peter Shor ist wirklich gut, aber es gibt noch einen anderen Weg, dies zu beantworten: zu beweisen, dass die Baumbreite durch die doppelte Amplitude (die Scheitelpunktversion) begrenzt ist. Da wir wissen, dass 3-reguläre Expander eine lineare Baumbreite haben, sind wir fertig.

Sehen Sie sich die Konstruktion einer Baumzerlegung bei einem BFS-Baum an. Dies ist Folie 15 dieser Präsentation: http://www.liafa.jussieu.fr/~pierref/ALADDIN/MEETING2/soto.pdf

Es ist leicht zu erkennen, dass die Größe jeder Tasche durch das Zweifache der breitesten Ebene begrenzt ist.

tatest
quelle

Vielen Dank für Ihre Antwort, diese Präsentation war sehr hilfreich.

Giorgio Camerani