Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6424195 | European Journal of Combinatorics | 2014 | 13 Pages |
Abstract
For the ErdÅs-Rényi random graph Gn,p, we give a precise asymptotic formula for the size αËt(Gn,p) of a largest vertex subset in Gn,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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Nikolaos Fountoulakis, Ross J. Kang, Colin McDiarmid,