I’m stuck on a problem I’ve found in a book on random graphs. Appreciate any help:
Let $G_{n,p}$ be a random graph with $p=\frac{c}{n}$ for some positive $c$. Show that with high probability there is a vertex with degree at least $\sqrt{\log n}$.
Asked
Active
Viewed 142 times
1 Answers
0
A much stronger result is shown in this paper:
Riordan, Oliver; Selby, Alex, The maximum degree of a random graph, Comb. Probab. Comput. 9, No. 6, 549-572 (2000). ZBL0971.05101.
Igor Rivin
- 25,994
- 1
- 19
- 40
-
Thank you! Although I am trying to solve the question using basic tools (it is suppose to be a relatively simple exercise). – Nick A. R. Nov 25 '22 at 08:58
-
@NickA.R. Yes, I understand, but I find it is often helpful to know what the "truth" is. – Igor Rivin Nov 25 '22 at 13:27