On the upper tail of star counts in random graphs

Abstract

Let $X$ count the number of $r$-stars in the random binomial graph $\mathbb{G}(n,p)$. We determine, for fixed $r$ and $\epsilon >0$, the asymptotics of $\log \mathbb{P}(X\ge (1+\epsilon )\mathbb{E}X)$ assuming only $\mathbb{E}X\to \infty$ and $p\to 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.