Dense subgraphs in random graphs
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...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2019
|
| _version_ | 1797097987524001792 |
|---|---|
| author | Balister, P Bollobás, B Sahasrabudhe, J Veremyev, A |
| author_facet | Balister, P Bollobás, B Sahasrabudhe, J Veremyev, A |
| author_sort | Balister, P |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T05:03:12Z |
| format | Journal article |
| id | oxford-uuid:d903cc27-1ff6-4d7d-ad05-07704404a8d0 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T05:03:12Z |
| publishDate | 2019 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:d903cc27-1ff6-4d7d-ad05-07704404a8d02022-03-27T08:52:57ZDense subgraphs in random graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:d903cc27-1ff6-4d7d-ad05-07704404a8d0EnglishSymplectic ElementsElsevier2019Balister, PBollobás, BSahasrabudhe, JVeremyev, AFor 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. |
| spellingShingle | Balister, P Bollobás, B Sahasrabudhe, J Veremyev, A Dense subgraphs in random graphs |
| title | Dense subgraphs in random graphs |
| title_full | Dense subgraphs in random graphs |
| title_fullStr | Dense subgraphs in random graphs |
| title_full_unstemmed | Dense subgraphs in random graphs |
| title_short | Dense subgraphs in random graphs |
| title_sort | dense subgraphs in random graphs |
| work_keys_str_mv | AT balisterp densesubgraphsinrandomgraphs AT bollobasb densesubgraphsinrandomgraphs AT sahasrabudhej densesubgraphsinrandomgraphs AT veremyeva densesubgraphsinrandomgraphs |