# How big is the variance of the treewidth of a random graph in G(n,p)?

I am trying to find how close $tw(G)$ and $E[tw(G)]$ really are, when $G \in G(n,p=c/n)$ and $c>1$ is a constant not depending on n (so $E[tw(G)] = \Theta(n)$). My estimate is that $tw(G) \leq E[tw(G)] + o(n)$ w.h.p, but i haven't been able to prove it.

• What is the motivation for the question? (i.e. why are interested in this problem?) Mar 10 '12 at 15:38
• Well...i was wondering of how much the knowledge of some edges can affect the estimated treewidth (the knowledge of the existence of each edge can affect treewidth by at most one), and that led me to this question (which is much more interesting) Mar 10 '12 at 18:28
• In particular, this has implications for upper bounds of model-counting in the satisfiable regime for random instances of SAT (and quantum-SAT), in the phase of random Erdos-Renyi graphs having a large connected component. To the extent that we care about random SAT as a topic of theoretical computer science, and also approaches involving treewidth for bounding the complexity of #SAT and similar problems, this question is well-motivated. Apr 23 '14 at 8:34

$\mathbb{P}( | tw(G(n,p)) - \mathbb{E} tw(G(n,p))| > t) \le 3 e^{- t^2/(2 n)}$,
so the above probability tends to 0, if, say $t = n^{0.51}$.
The method was first applied to prove concentration for the chromatic number of $G(n,p)$. See B. Bollobás, Random graphs. Springer New York, 1998, page 298.