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?


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.

  • 1
    $\begingroup$ I guess $O(n^{1/50})$ was enough for the authors--just a bit sloppy to state it like that. $\endgroup$
    – kodlu
    Jun 30 '16 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.