On giant components and treewidth in the layers model

Uriel Feige, Jonathan Hermon, Daniel Reichman

Given an undirected $n$-vertex graph $G(V,E)$ and an integer $k$, let $T_k(G)$ denote the random vertex induced subgraph of $G$ generated by ordering $V$ according to a random perm…