23
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What is the motivation for the question? (i.e. why are interested in this problem?) $\endgroup$ – Kaveh Mar 10 '12 at 15:38
  • 6
    $\begingroup$ 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) $\endgroup$ – Kostas Mar 10 '12 at 18:28
  • 2
    $\begingroup$ 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. $\endgroup$ – Niel de Beaudrap Apr 23 '14 at 8:34
13
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.