Name
Abstract | ||
|---|---|---|
For the Erdos-Renyi random graph G"n","p, we give a precise asymptotic formula for the size @a@?"t(G"n","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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.ejc.2013.06.012 | Eur. J. Comb. |
Keywords | DocType | Volume |
large deviations,random graphs | Journal | 35, |
ISSN | Citations | PageRank |
Eur. J. Comb. 35 (2014), 232-244 | 0 | 0.34 |
References | Authors | |
2 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nikolaos Fountoulakis | 1 | 185 | 18.04 |
| Ross J. Kang | 2 | 86 | 18.12 |
| Colin McDiarmid | 3 | 1071 | 167.05 |