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&gt;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.
You don't need to calculate the variance to prove the concentration of tw(G(n,p)) around its expectation. If two graphs G' and G differ by one vertex then their treewidth differs by at most one. You can use the standard method, the Hoeffding-Azuma inequality applied to the vertex exposure martingale to show, for example,

$\mathbb{P}( | tw(G(n,p)) - \mathbb{E} tw(G(n,p))| &gt; 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.