Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423902 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
Abstract
For the ErdÅs-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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Nikolaos Fountoulakis, Ross J. Kang, Colin McDiarmid,