<p>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,</p>

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

<p>so the above probability tends to 0, if, say $t = n^{0.51}$.</p>

<p>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.</p>

CC BY-SA 3.0
2014-04-23T07:45:26.267Z
2014-04-23T08:14:59.247Z
2014-04-23T08:14:59.247Z
Valentas
<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.</p>

CC BY-SA 3.0
2012-03-10T15:38:51.500Z
What is the motivation for the question? (i.e. why are interested in this problem?)
Kaveh
CC BY-SA 3.0
2012-03-10T18:28:46.000Z
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)
Kostas
CC BY-SA 3.0
2014-04-23T08:34:42.333Z
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.
Niel de Beaudrap
<graph-theory><co.combinatorics><treewidth><random-graphs>
How big is the variance of the treewidth of a random graph in G(n,p)?
Kostas
# How big is the variance of the treewidth of a random graph in G(n,p)?

(Asked by: username_0 on 2012-03-10)

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.

**Tags:** graph-theory, co.combinatorics, treewidth, random-graphs
> **Comments:**
> **username_1**: What is the motivation for the question? (i.e. why are interested in this problem?)  
> **username_0**: 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)  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2014-04-23. Score: 13

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))| > 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.


---

