On the upper tail of counts of strictly balanced subgraphs

Matas Šileikis

The electronic journal of combinatorics, Tome 19 (2012) no. 1

Résumé

Let $X_G$ be the number of copies of $G$ in the Erdős-Rényi binomial random graph $\mathbb G(n,p)$. Janson, Oleszkiewicz and Ruciński proved that for every $t > 1$\begin{equation*}\exp \{-O_t( M^*_G \ln (1/p))\} \leq \mathbb{P}\{X_G \geq t\,\mathbb{E} X_G\} \leq \exp\{-\Omega_t(M^*_G)\},\end{equation*}where $M^*_G$ is a certain function of $n$ and $p$. For $G = K_3$ the logarithmic gap between the bounds was closed by Chatterjee and, independently, DeMarco and Kahn. We provide matching bounds for strictly balanced $G$, when $\mathbb{E} X_G \leq \ln n$. Also, we give matching bounds for $C_4$, $K_4$, and stars $K_{1,k}$ in a broader range of $\mathbb{E} X_G$. In particular, this improves some results of Janson and Ruciński for which the so called deletion method was used.

Détail

DOI : 10.37236/10

Classification : 05C80
Mots-clés : matching bounds for strictly balanced graphs, deletion method