Computer Science/Discrete Mathematics Seminar I

The motivating question for this talk is: What does a sparse Erdős–Rényi random graph, conditioned to have twice the number of triangles than the expected number, typically look like? Motivated by this question, In 2014, Chatterjee and Dembo introduced a framework for obtaining Large Deviation Principles (LDP) for nonlinear functions of Bernoulli random variables (this followed an earlier work of Chatterjee-Varadhan which used limit graph theory to answer this question in the dense regime). The aforementioned framework relies on a notion of "low complexity" functions on the discrete cube, defined in terms of the covering numbers of their gradient. The central lemma used in their proof provides a method of estimating the log-normalizing constant $\log \sum_{x \in \{-1,1\}^n} e^{f(x)}$, which applies for functions attaining low complexity and some additional smoothness properties. In this talk, we will introduce a new notion of complexity for measures on the discrete cube, namely the mean-width of the gradient of the log-density. We prove a general structure theorem for such measures which goes beyond the discrete cube. In particular, we show that a measure $\nu$ attaining low complexity (with no extra smoothness assumptions needed) are close to a product measure in the following sense: there exists a measure $\tilde \nu$ a small "tilt" of $\nu$ in the sense that their log-densities differ by a linear function with small slope, such that $\tilde \nu$ is close to a product measure in transportation distance. An easy corollary of our result is a strengthening of the framework of Chatterjee-Dembo, which in particular simplifies the derivation of LDPs for subgraph counts, and improves the attained bounds.