On the Upper Tail of Counts of Strictly Balanced Subgraphs
On the Upper Tail of Counts of Strictly Balanced Subgraphs
复制标题
关于严格平衡子图计数的上尾
DOI：
--
复制
发表时间：
2012
影响因子：
0.7
通讯作者：
Matas Šileikis
中科院分区：
文献类型：
--
作者：
Matas Šileikis
Let $X_G$ be the number of copies of $G$ in the Erdős-Renyi binomial random graph $\mathbb G(n,p)$. Janson, Oleszkiewicz and Rucinski 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 Rucinski for which the so called deletion method was used.
Let $X_G$ be the number of copies of $G$ in the Erdős-Renyi binomial random graph $\mathbb G(n,p)$. Janson, Oleszkiewicz and Rucinski 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 Rucinski for which the so called deletion method was used.