Local limit theorems for subgraph counts

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 Erdős-Rényi 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 Z/nZ 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.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).