2022/02/12 by Do, Tuan Anh, Erde, Joshua, Kang, Mihyun
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2202.06087
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= (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 → ∞. 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 ε.