On the upper tail of counts of strictly balanced subgraphs
type: Item
instance of: scholarly article
title: On the upper tail of counts of strictly balanced subgraphs
zbMATH Open document ID: 1243.05222
author: M. Şileikis
published in: The Electronic Journal of Combinatorics
publication date: 2012-06-12T00:00:00Z
full work available at URL: v19i1p4
review text: Summary: Let \(X_G\) be the number of copies of \(G\) in the Erdős-Rényi binomial random graph \(\mathbb G(n,p)\). \textit{S. Janson}, \textit{K. Oleszkiewicz} and \textit{A. Ruciński} [Isr. J. Math. 142, 61--92 (2004; Zbl 1055.05136)] proved that for every \(t > 1\) \[ \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), \] where \(M^*_G\) is a certain function of \(n\) and \(p\). For \(G = K_3\) the logarithmic gap between the bounds was closed by \textit{S. Chatterjee} [Random Struct. Algorithms 40, No. 4, 437--451 (2012)] and, independently, \textit{B. DeMarco} and \textit{J. Kahn} [ibid. 40, No. 4, 452--459 (2012)]. 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 \textit{S. Janson} and \textit{A. Ruciński} [ibid. 20, No. 3, 317--342 (2002; Zbl 0996.60023)] for which the so called deletion method was used.
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 6045628
zbMATH Keywords: matching bounds for strictly balanced graphs
zbMATH Keywords: deletion method
MaRDI profile type: Publication
Recommended article: Q3333079
Recommended article: Q4316717
Recommended article: Upper tails for subgraph counts in random graphs
Recommended article: Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs
Recommended article: Q3781137
Recommended article: Upper bounds for the \(k\)-subdomination number of graphs
Recommended article: Upper bounds on the balanced \(\langle \mathbf{r}, \mathbf{s} \rangle\)-domination number of a graph
Recommended article: Q4294576
Recommended article: Upper tail for homomorphism counts in constrained sparse random graphs
description: scientific article; zbMATH DE number 6045628