Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2202.06087 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- In this note, we consider the width of a supercritical random graph according to some commonly studied width measures. We give short, direct proofs of results of Lee, Lee and Oum, and of Perarnau and Serra, on the rank- and tree-width of the random graph $G(n,p)$ when $p= \frac{1+ε}{n}$ for $ε> 0$ constant. Our proofs avoid the use, as a black box, of a result of Benjamini, Kozma and Wormald on the expansion properties of the giant component in this regime, and so as a further benefit we obtain explicit bounds on the dependence of these results on $ε$. Finally, we also consider the width of the random graph in the weakly supercritical regime, where $ε= o(1)$ and $ε^3n \to \infty$. In this regime, we determine, up to a constant multiplicative factor, the rank- and tree-width of $G(n,p)$ as a function of $n$ and $ε$.