Large deviations of subgraph counts for sparse Erdős-Rényi graphs (Q2196617)

This paper makes great progress on the problem of establishing a large deviations principle of the random variable that counts the number of copies of a given graph \(H=(V,E)\) in a \(G(n,p)\) random graph asymptotically as \(n\to \infty\). The authors focus on the random variable that counts the number of homomorphisms of \(H\) in \(G(n,p)\). More specifically, it establishes large deviation principle for \(p\ll 1\) but \(p \gg n^{- 1/2\Delta^*(H)}\) (up to a logarithmic factor), where \(\Delta^*(H)\) is \(\frac12 \max_{uv \in E(H)} \{\deg(v) + \deg(u)\}\). For this range of \(p\), the paper determines the rate function up to a \(1+o(1)\) factor. Furthermore, the paper gives large deviation results for homomorphism counts in Sidorenko graphs. These are graphs in which the homomorphism density of any graph \(H\) is at least the density of the host graph raised to the number of edges of \(H\). Also, large deviation results are obtained for the Schatten norm of the adjacency matrix.