Nonlinear lower-tail large deviations at criticality
summary
The gist
We introduce general methods to derive lower tail large deviation principles for nonlinear problems of combinatorial interest…
In short
The work develops general methods for finding lower tail large deviation principles for nonlinear combinatorial problems near critical points. It uses an analytic variational problem to describe these rates, showing how probabilities behave in regimes where standard approximations fail. This framework yields new bounds on structures like Steiner triple systems and Latin squares.
Key concepts
- Lower Tail Large Deviation Principles
- These are mathematical tools used to estimate the probability of rare, unlikely events occurring in random combinatorial structures. In this context, they help determine the minimum rate at which a certain property (like being $H$-free) decays as the size of the structure grows.
- Variational Problem
- Instead of solving complex probability calculations directly, these methods reformulate the problem into finding an optimal solution to a continuous mathematical optimization problem. The solution to this problem determines the asymptotic rate function describing how quickly probabilities drop in critical regimes.
- Critical Regime
- This is a specific range of parameters where combinatorial effects are neither too sparse (allowing Poisson approximations) nor too dense (where simple counting dominates). It's a delicate regime, often characterized by parameters like $p o 0$ or $p o 1$ in a way that requires more sophisticated analysis.
- DKL Divergence
- This measures the difference between two probability distributions. In the large deviation context, minimizing this divergence helps find the most likely configuration of random variables that results in a very low probability event, directly linking it to the lower tail bounds.
Terminology used across episodes
This episode discusses
- Nonlinear lower-tail large deviations at criticality · Paper Radio
- Aristotle: IMO-level Automated Theorem Proving
- Latin squares without proper subsquares
- The Sunflower-Free Process
- Proof of the High Girth Existence Conjecture via Refined Absorption
- Lower tails for triangles inside the critical window
- Non-existence probabilities and lower tails in the critical regime via Belief Propagation
- The existence of designs
- An information theoretic approach to Sidorenko's conjecture
The paper
Nonlinear lower-tail large deviations at criticality · Read on arXiv
We introduce general methods to derive lower tail large deviation principles, for a variety of nonlinear problems of combinatorial interest. These methods are especially effective in "critical" regimes, where the nonlinearities are not sparse enough for Poissonian lower tails (e.g., Janson's inequality does not provide a sharp tail bound), but the situation is not so dense that combinatorial effects dominate (e.g., we cannot directly apply the theory of hypergraph containers or the relative entropy framework of Kozma-Samotij). In particular, these are regimes where one expects interesting phase transitions to occur. Our results have a number of consequences related to subgraphs in random graphs, answering various questions of Warnke and Jenssen-Perkins-Potukuchi-Simkin. For example, consider a random graph G about G(n,p), and let L(n,p)= [G is triangle-free]. The first-order asymptotics of L(n,p) have long been known in all parameter ranges except the critical regime where p has order of magnitude 1/sqrt n. We are able to fill this gap: for any fixed c>0, we show that n-3/2L(n,c/sqrt n) converges to a limit expressed in terms of a two-parameter variational problem, which has a single phase transition at c about 4.341. In contrast, we show that there is no such phase transition for the probability that G is C 2-free, for any fixed even cycle C 2. We also obtain some applications in combinatorial design theory. Addressing conjectures of Glock-Kühn-Lo-Osthus, Kelly, and Kwan-Sah-Sawhney-Simkin, we obtain new estimates on the number of order- n Steiner triple systems with no Pasch configuration and the number of order- n Latin squares with no 2 times 2 Latin subsquare (both tight up to a factor of (o(n 2))).
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "Nonlinear lower-tail large deviations at criticality".
Emmy: Here's the gist of the paper. We introduce general methods to derive lower tail large deviation principles for nonlinear problems of combinatorial interest, particularly in "critical" regimes where nonlinearities are neither sparse enough for Poissonian lower tails nor so dense that combinatorial effects dominate.
Ada: These methods allow describing the rate function in terms of the solution to an analytic variational problem.
Emmy: For a random graph G about G(n, p), the probability that G is triangle-free, denoted L(n, p) = P
G is triangle-free: , exhibits first-order asymptotics that change qualitatively around p = 1/sqrt n.
Ada: The authors demonstrate that for any fixed c > 0, the expression n-3/2 L(n, c/sqrt n) converges to a limit expressed through a two-parameter variational problem, which possesses a single phase transition at c about 4.341.
Paper summary: Ada: So to wrap up this paper Nonlinear lower-tail large deviations at criticality, it introduces general methods to find lower tail large deviation principles for nonlinear combinatorial problems in critical regimes where neither sparse enough for Poissonian tails nor dense enough for combinatorial effects to dominate.
Emmy: The main claim is that they can describe the rate function by solving an analytic variational problem, which allows them to handle these phase transitions that emerge in these critical settings.
Kolya: It matters because they apply this framework to show concrete results, like tight bounds on Steiner triple systems and Latin squares, and they establish new lower bounds for subgraph counts in random subsets.
Ada: The core implication is that for problems near a critical point, the behavior isn't simple; it’s governed by an underlying tradeoff between two entropic costs described by that variational problem.
Emmy: It shows that understanding those structural tradeoffs is key to predicting how these systems behave at the threshold where things get interesting.
Kolya: For anyone listening, this means when you’re dealing with complex nonlinear structures in random graphs or subsets, you need to use this specific variational structure to understand the asymptotic behavior.
Conclusion: Ada: So we've seen how they use these variational problems to tackle those hard nonlinear lower tail questions in random graphs and hypergraphs, right?
Emmy: Exactly, and I think the title itself captures that tension perfectly, "Nonlinear lower-tail large deviations at criticality". It signals a specific regime where things aren't behaving nicely anymore.
Kolya: From a probabilistic standpoint, what this means is that we can actually describe the probability of seeing extremely rare events—the very tails of the distribution—by solving this specific mathematical structure.
Ada: So it’s not just about counting how many triangles or cycles there are; it's about finding the underlying analytic problem that governs those rarest occurrences.
Emmy: It suggests that for these complex systems, the randomness isn't just noise; there’s a deep geometric structure, a shape in the space of possibilities that dictates where those rare tails go.
Kolya: And what this means for applications is that we can get tighter bounds on things like Steiner triple systems and Latin squares without just using some loose approximation.
Ada: We're moving from general statements to actually having formulas that give us concrete limits, even in these tricky critical zones where the behavior changes depending on a small parameter.
Emmy: It opens up a whole new way of thinking about how structure emerges when you push randomness right to its edge.
More episodes
- 2509.05860-Concentration Inequalities for Branching Random Walks
- 2509.19309-Small Prime Primitive Roots in Arithmetic Progressions
- 2509.21830-Noncollapsing for Curvature Flows with Inhomogeneous Speeds
- 2510.08346-Separability and Submetrizability in Locally Convex Spaces
- 2510.27290-Borel Combinatorics of Schreier Graphs of Z-actions
- 2511.13500-Sampling Density for Gabor Phase Retrieval
- 2511.19161-Linear dynamics of random products of weighted shifts
- 2511.21548-Metastability of diffusion processes in narrow tubes
- 2512.01536-Abelian approximations for bicrossed products
- 2601.02524-Lagrangian slice disks with symplectomorphic exteriors