Largest sparse subgraphs of random graphs
For the Erdős–Rényi random graph G<sub>n,p</sub>, we give a precise asymptotic formula for the size <em>â<sub>1</sub></em><em>(G<sub>n,p</sub></em>) of a largest vertex subset in G<sub>n,p</sub> that induces a subgraph with aver...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2012
|
| _version_ | 1826273232625336320 |
|---|---|
| author | Mcdiarmid, C Fountoulakis, N Kang, R |
| author_facet | Mcdiarmid, C Fountoulakis, N Kang, R |
| author_sort | Mcdiarmid, C |
| collection | OXFORD |
| description | For the Erdős–Rényi random graph G<sub>n,p</sub>, we give a precise asymptotic formula for the size <em>â<sub>1</sub></em><em>(G<sub>n,p</sub></em>) of a largest vertex subset in G<sub>n,p</sub> 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. |
| first_indexed | 2024-03-06T22:25:04Z |
| format | Journal article |
| id | oxford-uuid:5665df93-ebd4-4989-8b16-18cf0551e8c7 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T22:25:04Z |
| publishDate | 2012 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:5665df93-ebd4-4989-8b16-18cf0551e8c72022-03-26T16:49:58ZLargest sparse subgraphs of random graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:5665df93-ebd4-4989-8b16-18cf0551e8c7EnglishSymplectic Elements at OxfordElsevier2012Mcdiarmid, CFountoulakis, NKang, RFor the Erdős–Rényi random graph G<sub>n,p</sub>, we give a precise asymptotic formula for the size <em>â<sub>1</sub></em><em>(G<sub>n,p</sub></em>) of a largest vertex subset in G<sub>n,p</sub> 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. |
| spellingShingle | Mcdiarmid, C Fountoulakis, N Kang, R 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 mcdiarmidc largestsparsesubgraphsofrandomgraphs AT fountoulakisn largestsparsesubgraphsofrandomgraphs AT kangr largestsparsesubgraphsofrandomgraphs |