Wie groß ist die Varianz der Baumbreite eines Zufallsgraphen in G (n, p)?

Ich versuche herauszufinden, wie nahe und wirklich sind, wenn und eine Konstante ist, die nicht von n abhängt (also ). Meine Schätzung ist, dass whp, aber ich konnte es nicht beweisen. $tw(G)$ $E[tw(G)]$ $G \in G(n,p=c/n)$ $c>1$ $E[tw(G)] = \Theta(n)$ $tw(G) \leq E[tw(G)] + o(n)$

graph-theory co.combinatorics treewidth random-graphs Kostas
quelle

Was ist die Motivation für die Frage? (Warum interessieren Sie sich für dieses Problem?)

Kaveh

Nun, ich habe mich gefragt, inwieweit das Wissen über einige Kanten die geschätzte Baumbreite beeinflussen kann (das Wissen über die Existenz jeder Kante kann die Baumbreite um höchstens eins beeinflussen), und das hat mich zu dieser Frage geführt (die viel mehr ist) interessant)

Kostas

Dies hat insbesondere Auswirkungen auf die Obergrenzen der Modellzählung im erfüllbaren Regime für zufällige SAT-Instanzen (und Quanten-SAT) in der Phase zufälliger Erdos-Renyi-Graphen mit einer großen zusammenhängenden Komponente. In dem Maße, in dem wir uns mit zufälligem SAT als Thema der theoretischen Informatik befassen und auch mit Ansätzen, die die Komplexität von #SAT und ähnlichen Problemen einschränken, die Breite einbeziehen, ist diese Frage gut motiviert.

Niel de Beaudrap

Antworten:

Sie müssen die Varianz nicht berechnen, um die Konzentration von tw (G (n, p)) um seine Erwartung herum zu beweisen. Unterscheiden sich zwei Graphen G 'und G um einen Eckpunkt, so unterscheidet sich ihre Baumbreite um höchstens einen. Mit der Standardmethode, der Hoeffding-Azuma-Ungleichung, die auf das Vertex-Exposure-Martingal angewendet wird, können Sie beispielsweise Folgendes anzeigen:

, $\mathbb{P}( | tw(G(n,p)) - \mathbb{E} tw(G(n,p))| > t) \le 3 e^{- t^2/(2 n)}$

Die obige Wahrscheinlichkeit tendiert also zu 0, wenn beispielsweise . $t = n^{0.51}$

Die Methode wurde zuerst angewendet, um die Konzentration für die chromatische Zahl von zu beweisen . Siehe B. Bollobás, Zufallsgraphen. Springer New York, 1998, Seite 298. $G(n,p)$

Valentas
quelle