Upper tail for homomorphism counts in constrained sparse random graphs. Issue 3 (5th April 2021) - Bhattacharya, Sohom; Dembo, Amir
Abstract: Consider the upper tail probability that the homomorphism count of a fixed graph H within a large sparse random graph G n exceeds its expected value by a fixed factor 1 + δ . Going beyond the Erdős–Rényi model, we establish here explicit, sharp upper tail decay rates for sparse random d n ‐regular graphs (provided H has a regular 2‐core), and for sparse uniform random graphs. We further deal with joint upper tail probabilities for homomorphism counts of multiple graphs H 1, …, H k (extending the known results for k = 1 ), and for inhomogeneous graph ensembles (such as the stochastic block model), we bound the upper tail probability by a variational problem analogous to the one that determines its decay rate in the case of sparse Erdős–Rényi graphs.