Local limit theorems for subgraph counts

DOI10.1112/JLMS.12523MaRDI QIDQ6176774zbMATH OpenWikidataFDO

Authors Ashwin Sah, Mehtaab Sawhney

Publication date 24 August 2023

Published in Journal of the London Mathematical Society (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

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

zbMATH Keywords

arithmetic progressionlocal limit theoremnumber of subgraphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Random graphs (graph-theoretic aspects) (05C80) Boolean functions (06E30) Central limit and other weak theorems (60F05)

Abstract: We introduce a general framework for studying anticoncentration and local limit theorems for random variables, including graph statistics. Our methods involve an interplay between Fourier analysis, decoupling, hypercontractivity of Boolean functions, and transference between ``fixed-size and ``independent models. We also adapt a notion of ``graph factors due to Janson. As a consequence, we derive a local central limit theorem for connected subgraph counts in the ErdH{o}s-Renyi random graph $G(n,p)$, building on work of Gilmer and Kopparty and of Berkowitz. These results improve an anticoncentration result of Fox, Kwan, and Sauermann and partially answers a question of Fox, Kwan, and Sauermann. We also derive a local limit central limit theorem for induced subgraph counts, as long as $p$ is bounded away from a set of ``problematic densities, partially answering a question of Fox, Kwan, and Sauermann. We then prove these restrictions are necessary by exhibiting a disconnected graph for which anticoncentration for subgraph counts at the optimal scale fails for all constant $p$, and finding a graph $H$ for which anticoncentration for induced subgraph counts fails in $G(n,1/2)$. These counterexamples resolve anticoncentration conjectures of Fox, Kwan, and Sauermann in the negative. Finally, we also examine the behavior of counts of $k$-term arithmetic progressions in subsets of $mathbbZ/nmathbbZ$ and deduce a local limit theorem wherein the behavior is Gaussian at a global scale but has nontrivial local oscillations (according to a Ramanujan theta function). These results improve on results of and answer questions of the authors and Berkowitz, and answer a question of Fox, Kwan, and Sauermann.

Recommendations

• Anti-concentration for subgraph counts in random graphs
• Anticoncentration for subgraph statistics
• Subgraph counts in random graphs using incomplete U-statistics methods
• A local central limit theorem for triangles in a random graph
• Combinatorial anti-concentration inequalities, with applications

Cites work

• A central limit theorem for decomposable random variables with applications to random graphs
• A graph Fourier transform and proportional graphs
• A local central limit theorem for triangles in a random graph
• Additive combinatorics
• An example of a superproportional graph
• Analysis of Boolean Functions
• Anti-concentration for polynomials of independent random variables
• Anti-concentration for subgraph counts in random graphs
• Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices
• Asymptotic properties of labeled connected graphs
• Fundamentals of Stein's method
• Graph decomposition and parity
• scientific article; zbMATH DE number 3173143 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 909705 (Why is no real title available?)
• Number of arithmetic progressions in dense random subsets of \(\mathbb{Z}/n\mathbb{Z}\)
• On a local limit theorem of the theory of probability
• On the Kolmogorov-Rogozin inequality for the concentration function
• Orthogonal decompositions and functional limit theorems for random graph statistics
• Random graphs and the parity quantifier
• Subgraph counts in random graphs using incomplete U-statistics methods
• The lower tail: Poisson approximation revisited
• The order of the giant component of random hypergraphs
• Triangles in random graphs
• Upper tail large deviations for arithmetic progressions in a random set
• Upper tails for arithmetic progressions in random subsets
• Upper tails via high moments and entropic stability
• When are small subgraphs of a random graph normally distributed?

Cited in

(6)

• Compound Poisson approximations of subgraph counts in random graphs
• On local weak limit and subgraph counts for sparse random graphs
• The complexity of the Approximate Multiple Pattern Matching Problem for random strings
• Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
• A limit theorem for small cliques in inhomogeneous random graphs
• Local central limit theorem for triangle counts in sparse random graphs

This page was built for publication: Local limit theorems for subgraph counts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6176774)