Jak duża jest wariancja szerokości wykresu losowego w G (n, p)?

Staram się dowiedzieć, jak blisko i naprawdę są, gdy i jest stałą nie zależnie od n (tak ). Szacuję, że whp, ale nie byłem w stanie tego udowodnić. $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
źródło

Jaka jest motywacja pytania? (tzn. dlaczego są zainteresowani tym problemem?)

Kaveh

Cóż ... zastanawiałem się, w jakim stopniu znajomość niektórych krawędzi może wpłynąć na szacowaną szerokość (wiedza o istnieniu każdej krawędzi może wpłynąć na szerokość co najwyżej jeden), i to doprowadziło mnie do tego pytania (które jest znacznie więcej ciekawe)

Kostas,

W szczególności ma to wpływ na górne granice zliczania modeli w zadowalającym reżimie dla przypadkowych przypadków SAT (i kwantowej-SAT), w fazie losowych wykresów Erdosa-Renyi mających duży połączony komponent. W zakresie, w jakim zależy nam na losowym SAT jako temacie informatyki teoretycznej, a także podejściach polegających na rozwiązywaniu problemu złożoności #SAT i podobnych problemów, pytanie to jest dobrze umotywowane.

Niel de Beaudrap,

Odpowiedzi:

Nie trzeba obliczać wariancji, aby udowodnić stężenie tw (G (n, p)) wokół jego oczekiwań. Jeśli dwa wykresy G 'i G różnią się o jeden wierzchołek, wówczas ich szerokość różni się o co najwyżej jeden. Możesz użyć standardowej metody nierówności Hoeffdinga-Azumy zastosowanej do martingale ekspozycji wierzchołków, aby pokazać na przykład:

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

więc powyższe prawdopodobieństwo dąży do 0, jeśli powiedzmy . $t = n^{0.51}$

Metodę zastosowano po raz pierwszy w celu wykazania stężenia dla liczby chromatycznej . Patrz B. Bollobás, Losowe wykresy. Springer New York, 1998, strona 298. $G(n,p)$

Valentas
źródło