A Note on Treewidth in Random Graphs

We show that in Erdos-Renyi random graph G(n, p) with high probability, when p = c/n and c is a constant, the treewidth is upper bounded by In for some constant t < 1 which may depend on c, but when p >> 1/n, the treewidth is lower bounded by n - o(n). The upper bound refutes a conjecture that treewidth in G(n,p = c/n) is a.s large as n - o(n), and the lower bound provides further theoretical evidence on hardness of some random constraint satisfaction problems called Model RB and Model RD.Computer Science, Theory & MethodsEngineering, Electrical & ElectronicEICPCI-S(ISTP)