Journal article icon

Journal article

Largest sparse subgraphs of random graphs.

Abstract:
For the Erdos-Rényi random graph Gn,p, we consider the order of a largest vertex subset that induces a subgraph with average degree at most t. For the case when both p and t are fixed, 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. © 2011 Elsevier B.V.

Actions


Access Document


Publisher copy:
10.1016/j.endm.2011.09.057

Authors


Fountoulakis, N More by this author
McDiarmid, C More by this author
Journal:
Electronic Notes in Discrete Mathematics
Volume:
38
Pages:
349-354
Publication date:
2011
DOI:
EISSN:
1571-0653
ISSN:
1571-0653
URN:
uuid:489cd046-6fd1-4075-9ee6-cb050a7e2291
Source identifiers:
221458
Local pid:
pubs:221458

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP