| Summary: | For a constant USD \gamma \in[0,1] USD and a graph USD G USD, let USD \omega_{\gamma}(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 \gamma\binom{k}{2} USD edges. We show that if USD 0<p<\gamma<1 USD then USD \omega_{\gamma}(G_{n,p}) USD is concentrated on a set of two integers. More
precisely, with
USD \alpha(\gamma,p)=\gamma\log\frac{\gamma}{p}+(1-\gamma)\log\frac{1-\gamma}{1-p} USD,
we show that USD \omega_{\gamma}(G_{n,p})$ USD is one of the two integers closest to
USD \frac{2}{\alpha(\gamma,p)}\big(\log n-\log\log
n+\log\frac{e\alpha(\gamma,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.
|
|---|