On the upper tail of star counts in random graphs
Abstrakt
Let X count the number of r-stars in the random binomial graph G (n,p). We determine, for fixed r and ε > 0, the asymptotics of log P (X ≥ (1 + ε)EX) assuming only EX→∞ and p→0 thus giving a first class of irregular graphs for which the upper tail problem for subgraph counts (stated by Janson and Ruciński in 2004) is solved in the sparse setting.