Question on a paper by Benjamini/Kozma/Wormald about a “well known fact”

Question

In "The mixing time of the giant component of a random graph" by the aforementioned authors, in the last proof on page 19 it says something along the lines of

"It is well known and easy to verify that, since $m=O(n)$ , asymptotically almost surely the maximum degree occurring in $\mathcal{C}_3(n,m)$ is $o(n^{0.02})$"

where $\mathcal{C}(n,m)$ denotes a random graph with $n$ vertices, $m$ edges, uniformly sampled among such graphs, and $\mathcal{C}_3(n,m)$ denotes the variable conditioned on minimum degree 3 (which shouldn't influence the above statement).

I am wondering where the $n^{0.02}$ comes from, and how this is "well known". Can someone provide an original source for this statement or this kind of statement?

Answer 1

I have no idea where the figure $n^{0.02}$ comes from. I would usually say it's well known that the maximum degree is $O(\log n)$ (actually even this is an overestimate). It's for example found in an Erd\H{o}s-R\'enyi paper with a title about random matrices, I think; or surely in any of the 'Random Graphs' books.

In any case, it is very easy to prove. One (lazy) way is: generate $G(n,p)$ with $p=1000(\log n)/n$. Standard applications of the Chernoff bound give you that a.a.s. this has all vertex degrees between $500\log n$ and $1500\log n$. Take a uniform random subgraph of this with $m$ edges and minimum degree three. Over both levels of randomness this is uniformly distributed, so it's $C_3(n,m)$: done.