Upper tail for homomorphism counts in constrained sparse random graphs

DOI10.1002/rsa.21011zbMath1522.05414arXiv1909.03045OpenAlexW3139575447MaRDI QIDQ6074661

Amir Dembo, Sohom Bhattacharya

Publication date: 12 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1909.03045

zbMATH Keywords

large deviationsgraph homomorphism\(d\)-regular graphssparse random graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Exact enumeration problems, generating functions (05A15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Density (toughness, etc.) (05C42)

Related Items

Large deviation for uniform graphs with given degrees, Large deviations in random latin squares, Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime

Cites Work

• Unnamed Item
• The large deviation principle for the Erdős-Rényi random graph
• Small subgraphs of random regular graphs
• A generalization of Hölder's inequality and some probability inequalities
• The dimension-free structure of nonhomogeneous random matrices
• Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations
• Upper tails for subgraph counts in random graphs
• A large deviation principle for the Erdős-Rényi uniform random graph
• The structure of low-complexity Gibbs measures on product spaces
• Nonlinear large deviations: beyond the hypercube
• Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs
• Upper tails and independence polynomials in random graphs
• The deletion method for upper tail estimates
• Nonlinear large deviations
• On the Choice Number of Random Hypergraphs
• Large Deviations for Random Matrices
• The lower tail: Poisson approximation revisited
• The missing log in large deviations for triangle counts
• Upper tails for triangles
• Tight upper tail bounds for cliques
• On replica symmetry of large deviations in random graphs
• Divide and conquer martingales and the number of triangles in a random graph
• The infamous upper tail
• Upper Tail Large Deviations for Arithmetic Progressions in a Random Set
• Upper Tails for Edge Eigenvalues of Random Graphs
• On the Lower Tail Variational Problem for Random Graphs
• On the variational problem for upper tails in sparse random graphs