Dense subgraphs in random graphs - Balister, P; Bollobás, B; Sahasrabudhe, J; Veremyev, A (Elsevier, 2019)
For a constant USD γ \in[0,1] USD and a graph USD G USD, let USD ω_{γ}(G) USD be the largest integer USD k USD for which there exists a USD k USD-vertex subgraph of USD G USD with at least USD γ\binom{k}{2} USD edges. We show that if USD 0<p<γ<1 USD then USD ω_{γ}(G_{n,p}) USD is concentrated on a set of two integers. More precisely, with USD α(γ,p)=γ\log\frac{γ}{p}+(1-γ)\log\frac{1-γ}{1-p} USD, we show that USD ω_{γ}(G_{n,p})$ USD is one of the two integers closest to USD \frac{2}{α(γ,p)}\big(\log n-\log\log n+\log\frac{eα(γ,p)}{2}\big)+\frac{1}{2} USD, with high probability. While this situation parallels that of cliques in random graphs, a new technique is required to handle the more complicated ways in which these "quasi-cliques" may overlap.