Upper tail behavior of the number of triangles in random graphs with constant average degree (Q6607835)

Let \(N\) be the number of triangles in an Erdős-Rényi random graph \(G(n,d/n)\) for fixed \(d\). It is intuitively reasonable, and a result of \textit{B. Bollobás} [Math. Proc. Camb. Philos. Soc. 90, 197--206 (1981; Zbl 0475.05074)], that \(N\) converges weakly to a Poisson distribution with parameter \(d^{3}/6\) as \(n\rightarrow\infty\). This implies that for any bounded sequence \((k_{n})\) we have \(\vert \mathbb{P}(N\geq k_{n}) - \mathbb{P}(\mathrm{Poi}(d^{3}/6\geq k_{n})\vert\) will tend to 0 as \(n\rightarrow\infty\) where \(\mathrm{Poi}(\lambda)\) denotes a Poisson random variable with parameter \(\lambda\). The question thus arises of trying to determine what growth rate of \((k_{n})\) is such that this is no longer true.\par The important paper under review provides a clear answer to this question. The first main result is that there exists a constant \(c\), depending only on \(d\), such that if \(\delta>0\) is a suitably small constant, then we have firstly that for \(k_{n}^{1/3}\log(k_{n})<(((3/\sqrt{2})^{2/3}-\delta)\log(n)\) (the \lq subcritical regime\rq) we have for sufficiently large \(n\) that \(e^{k_{n}\log(k_{n})-ck_{n}}\leq P(N\geq k_{n})\ \leq e^{k_{n}\log(k_{n})+ck_{n}}\). That is, in this regime, the Poisson approximation holds. However in the supercritical regime, we get qualitatively different behaviour. The precise statement is that letting \(\delta>0\) and \(0<\mu<1/10\) be constants, we have for \(k_{n}^{1/3}\log(k_{n})>((3/\sqrt{2})^{2/3}-\delta)\log(n)\) and \(k_{n}<n^{1/10-\mu}\) that, for any \(\epsilon>0\) and large enough \(n\) we have \(n^{-(3/\sqrt{2})^{2/3}+\epsilon)k^{2/3}} \leq \mathbb{P}(N\geq k_{n})\leq n^{-(3/\sqrt{2})^{2/3}-\epsilon)k^{2/3}}\). The authors note at least technical issues about extending their ideas to giving the critical behaviour.\par The authors also prove a structure theorem for the graph conditional on \(N\geq k_{n}\), answering a question of Aldous. We omit the precise statement but the essence is that in the subcritical regime, conditional on \(N \geq k_{n}\), the probability of having at least \((1-\epsilon)k\) vertex disjoint triangles tends to 1 as \(n\rightarrow\infty\) whereas for the supercritical regime, conditional on \(N\geq k_{n}\), the probability of an \lq almost clique\rq\, which accounts for most of the surplus triangles, tends to 1 as \(n\rightarrow\infty\). Here an almost clique is the event \(\mathcal{C}_{\epsilon}\) that there is a set \(V^{\prime}\) of vertices of order at most \((1+\epsilon)6^{1/3}k^{1/3}\) and for which the number of triangles with all vertices in \(V^{\prime}\) is at least \((1-\epsilon)k\) - i.e. about as large as it could be.\par The authors discuss the overlap of their results with ones in \textit{S. Chakraborty} et al. [``Sparse random graphs with many triangles'', Preprint, arXiv:2112.06526 [math. PR] (2021)] and also note that subsequent work in \textit{M. B. R. Chowdhury} [``Universality in prelimiting tail behavior for regular subgraph counts in the Poisson regime'', Preprint, arXiv:2304.01162 [math. PR] (2023)] makes progress on similar questions for all regular graphs. \par To say a little about proof techniques, note two natural ways for a graph to have \(k\) triangles - either have \(k\) vertex disjoint ones, or a clique of order (about) \((6k)^{1/3}\); by second moment method arguments these lead to lower bounds on \(\mathbb{P})(N\geq k)\). The work of the paper is thus on corresponding upper bounds. This leads to results of potentially independent interest, for example bounding above the probability that the graph contains a so-called triangle induced graph. The proof of this in turn depends on estimating the probability that there is a connected graph induced by \(\ell\) triangles. If this has \(v\) vertices and \(r\) edges, a crucial lemma shows \(r-v\) can be lower bounded in terms of the number of triangles.