Largest sparse subgraphs of random graphs
For the Erdo{double acute}s-Rényi random graph G n,p, we give a precise asymptotic formula for the size α̂t(Gn,p) of a largest vertex subset in G n,p that induces a subgraph with average degree at most t, provided that p = p (n) is not too small and t = t (n) is not too large. In the case of fixed t...
| Main Authors: | , , |
|---|---|
| 格式: | Journal article |
| 語言: | English |
| 出版: |
2014
|
| _version_ | 1826298455077683200 |
|---|---|
| author | Fountoulakis, N Kang, R McDiarmid, C |
| author_facet | Fountoulakis, N Kang, R McDiarmid, C |
| author_sort | Fountoulakis, N |
| collection | OXFORD |
| description | For the Erdo{double acute}s-Rényi random graph G n,p, we give a precise asymptotic formula for the size α̂t(Gn,p) of a largest vertex subset in G n,p that induces a subgraph with average degree at most t, provided that p = p (n) is not too small and t = t (n) is not too large. In the case of fixed t and p, we find that this value is asymptotically almost surely concentrated on at most two explicitly given points. This generalises a result on the independence number of random graphs. For both the upper and lower bounds, we rely on large deviations inequalities for the binomial distribution. © 2013 Elsevier Ltd. |
| first_indexed | 2024-03-07T04:47:06Z |
| format | Journal article |
| id | oxford-uuid:d3a84fb7-0c40-4ab6-afc0-82e5a29df997 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T04:47:06Z |
| publishDate | 2014 |
| record_format | dspace |
| spelling | oxford-uuid:d3a84fb7-0c40-4ab6-afc0-82e5a29df9972022-03-27T08:12:55ZLargest sparse subgraphs of random graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:d3a84fb7-0c40-4ab6-afc0-82e5a29df997EnglishSymplectic Elements at Oxford2014Fountoulakis, NKang, RMcDiarmid, CFor the Erdo{double acute}s-Rényi random graph G n,p, we give a precise asymptotic formula for the size α̂t(Gn,p) of a largest vertex subset in G n,p that induces a subgraph with average degree at most t, provided that p = p (n) is not too small and t = t (n) is not too large. In the case of fixed t and p, we find that this value is asymptotically almost surely concentrated on at most two explicitly given points. This generalises a result on the independence number of random graphs. For both the upper and lower bounds, we rely on large deviations inequalities for the binomial distribution. © 2013 Elsevier Ltd. |
| spellingShingle | Fountoulakis, N Kang, R McDiarmid, C Largest sparse subgraphs of random graphs |
| title | Largest sparse subgraphs of random graphs |
| title_full | Largest sparse subgraphs of random graphs |
| title_fullStr | Largest sparse subgraphs of random graphs |
| title_full_unstemmed | Largest sparse subgraphs of random graphs |
| title_short | Largest sparse subgraphs of random graphs |
| title_sort | largest sparse subgraphs of random graphs |
| work_keys_str_mv | AT fountoulakisn largestsparsesubgraphsofrandomgraphs AT kangr largestsparsesubgraphsofrandomgraphs AT mcdiarmidc largestsparsesubgraphsofrandomgraphs |