Quelle est la variance de la largeur d'arbre d'un graphe aléatoire dans G (n, p)?

J'essaie de trouver à quel point et sont vraiment proches , quand et est une constante ne dépendant pas de n (donc ). Mon estimation est que whp, mais je n'ai pas pu le prouver. $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
la source

Quelle est la motivation de la question? (c'est-à-dire pourquoi ce problème vous intéresse?)

Kaveh

Eh bien ... je me demandais dans quelle mesure la connaissance de certains bords peut affecter la largeur estimée de l'arbre (la connaissance de l'existence de chaque bord peut affecter la largeur de l'arbre par au plus un), et cela m'a amené à cette question (qui est beaucoup plus intéressant)

Kostas

En particulier, cela a des implications pour les limites supérieures du comptage de modèles dans le régime satisfaisable pour les instances aléatoires de SAT (et quantum-SAT), dans la phase des graphiques Erdos-Renyi aléatoires ayant une grande composante connectée. Dans la mesure où nous nous soucions de la SAT aléatoire en tant que sujet d'informatique théorique, ainsi que des approches impliquant la largeur d'arbre pour délimiter la complexité de la #SAT et des problèmes similaires, cette question est bien motivée.

Niel de Beaudrap

Réponses:

Vous n'avez pas besoin de calculer la variance pour prouver la concentration de tw (G (n, p)) autour de son attente. Si deux graphes G 'et G diffèrent d'un sommet, leur largeur d'arbre diffère d'au plus un. Vous pouvez utiliser la méthode standard, l'inégalité Hoeffding-Azuma appliquée à la martingale d'exposition au sommet pour montrer, par exemple,

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

$t = n^{0.51}$

$G(n,p)$

Valentas
la source