Upper tail for homomorphism counts in constrained sparse random graphs. Issue 3 (5th April 2021)

• Record Type: Journal Article
• Authors: Bhattacharya, Sohom; Dembo, Amir
• Is Part Of: Random structures & algorithms. Volume 59:Issue 3(2021)
• Page Start: 315
• Page End: 338
• Publication Date: 2021-04-05
• Subjects: d‐regular graphs -- graph homomorphism -- large deviations -- sparse random graph; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21011
• Languages: English
• ISSNs: 1042-9832

Abstract

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.