Nonlinear lower-tail large deviations at criticality
Listen
Radio episode about this paper
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.
math.CO, cs.DM, math.PR
Submitted: 2026-10-07
Updated: 2026-11-08
Code: https://github.com/mkwn/triangle-free-probability
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 92/100
The gist: We introduce general methods to derive lower tail large deviation principles for nonlinear problems of combinatorial interest…
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
Summary
We introduce general methods to derive lower tail large deviation principles for nonlinear problems of combinatorial interest, particularly in In this paper we introduce general methods to study “critical” lower tail large deviation problems of
the above type. For such problems, our methods allow one to describe the rate function in terms of the
solution to an analytic variational problem.critical
regimes where nonlinearities are neither sparse enough for Poissonian lower tails nor so dense that combinatorial effects dominate. These methods allow describing the rate function in terms of the solution to an analytic variational problem. p. 1Where the paper says it
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. p. 0 Introduction
What is the probability that an Erdős–Rényi random graph G ∼ G(n, p) is triangle-free? Curiously,
the answer to this question changes qualitatively around p = 1/
√
n. 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/
√
n. We are able to fill this gap: for any fixed c > 0, we show that n−3/2L△(n, c/√
n) converges to
a limit expressed in terms of a two-parameter variational problem, which has a single phase transition
at c ≈ 4. We are able to fill this gap: for any fixed c > 0, we show that n−3/2L△(n, c/√
n) converges to
a limit expressed in terms of a two-parameter variational problem, which has a single phase transition
at c ≈ 4. In contrast, we show that there is no such phase transition for the probability that G is
C2ℓ-free, for any fixed even cycle C2ℓ.Where the paper says it
Where the paper says it
Where the paper says it
These general methods are applied to yield new estimates in combinatorial design theory, providing tight bounds 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))). p. 0 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 × 2 Latin subsquare (both tight up to a factor of exp(o(n
2
))). For example, consider a random graph
G ∼ G(n, p), and let L△(n, p) = log 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/
√
n.Where the paper says it
Where the paper says it
P[G is H-free] = (1 + o(1)) (1 - p)p times s in[0, 1] p n/2 (s s - s + 1) + EX H(G) times s e(H).
The paper also presents general theorems for lower tails in random subsets of hypergraphs, characterized by boundedness conditions on the hypergraph H. p. 7 In this section we state some general theorems
about lower tails in random subsets of hypergraphs. Namely, given a hypergraph satisfying certain
“boundedness” conditions (of the type appearing in hypergraph container theorems [7, 77] or in the
random greedy hypergraph independent set process [11]), we characterise the lower tail large deviation
rate function of the number of hyperedges in a random vertex subset (either a random subset of a fixed
size, or a binomial random subset where each vertex is included independently with some probability). We can now state the promised general lower tail estimates. We start with upper bounds on the lower
tail. [45]), only using that XK3
(G) is a sum of
random variables with “not too much dependence”. On the other hand, in the supercritical regime, the
probability is described by extremal graph theory considerations: recall that Mantel’s theorem (see e.Where the paper says it
Where the paper says it
Where the paper says it
P[H[R] at most L] at most - q vector DKL(q vector | p) + phi L(H(q vector)) + epsilon pN
for binomial random subsets R about Bin(V, p).
The authors solve certain special cases of these variational problems, including the triangle-freeness problem for K 3, characterizing its asymptotic value as psi Bin(K 3, c, 0) = r,t in[0,1] (r r - r + 1) + (t t - t + 1)/2 + c 2/(4rt 2), which exhibits a phase transition at c about 4. p. 1 For such problems, our methods allow one to describe the rate function in terms of the
solution to an analytic variational problem. For example (very roughly speaking, before we’ve had a
chance to properly introduce the relevant concepts), in the critical regime for triangle-freeness described
above, the asymptotic value of log P[G is triangle-free] is determined by the optimal tradeoff between two
“entropic costs” that we can “pay” to make our graph triangle-free: on one hand, we can pay some cost
to change the edge-profile of our random graph in an inhomogeneous way (that may indirectly result in
fewer triangles), and given the resulting inhomogeneous random graph we can pay some Poissonian cost
to suppress the number of triangles down to zero.Where the paper says it
Furthermore, the work addresses applications to Steiner triple systems and Latin squares, yielding upper bounds on the number of order- n anti-Pasch Steiner triple systems (Theorem 1. p. 0 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 × 2 Latin subsquare (both tight up to a factor of exp(o(n
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 × 2 Latin subsquare (both tight up to a factor of exp(o(n
2
))). Then, for R ∼ Unif(V, m) and L ≥ 0,
log P
|H[R]| ≤ L
≥ − min
⃗q
DKL(⃗q ∥ m/N) + ΦL(H(⃗q))
− εm,
where the minimum is over all ⃗q ∈ [0, 1]V whose sum of entries is exactly m. We believe that it should not really be necessary to have stronger assumptions for the lower
bound than the upper bound: the assumptions of Theorem 1. 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 × 2 Latin subsquare (both tight up to a factor of exp(o(n
2
))). In this section we state some general theorems
about lower tails in random subsets of hypergraphs. Namely, given a hypergraph satisfying certain
“boundedness” conditions (of the type appearing in hypergraph container theorems [7, 77] or in the
random greedy hypergraph independent set process [11]), we characterise the lower tail large deviation
rate function of the number of hyperedges in a random vertex subset (either a random subset of a fixed
size, or a binomial random subset where each vertex is included independently with some probability).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The paper concludes by showing how to deduce lower bounds on lower tails using biased random processes and techniques related to the Laplace transform, resulting in Theorems 1. p. 7 Namely, given a hypergraph satisfying certain
“boundedness” conditions (of the type appearing in hypergraph container theorems [7, 77] or in the
random greedy hypergraph independent set process [11]), we characterise the lower tail large deviation
rate function of the number of hyperedges in a random vertex subset (either a random subset of a fixed
size, or a binomial random subset where each vertex is included independently with some probability). By defining appropriate hypergraphs, we will be able to use the general theorems in this section to deduce
all the results in Section 1. Then, for R ∼ Unif(V, m) and L ≥ 0,
log P
|H[R]| ≤ L
≤ − min
⃗q
DKL(⃗q ∥ m/N) + ΦL(H(⃗q))
+ εm,
where the minimum is over all ⃗q ∈ [0, 1]V whose sum of entries is exactly m. Next, we state matching lower bounds on the lower tail, which require slightly stronger assumptions
(roughly speaking, we need to make a quantitative assumption on how fast λ decays with N). For such problems, our methods allow one to describe the rate function in terms of the
solution to an analytic variational problem. For example (very roughly speaking, before we’ve had a
chance to properly introduce the relevant concepts), in the critical regime for triangle-freeness described
above, the asymptotic value of log P[G is triangle-free] is determined by the optimal tradeoff between two
“entropic costs” that we can “pay” to make our graph triangle-free: on one hand, we can pay some cost
to change the edge-profile of our random graph in an inhomogeneous way (that may indirectly result in
fewer triangles), and given the resulting inhomogeneous random graph we can pay some Poissonian cost
to suppress the number of triangles down to zero.Where the paper says it
Where the paper says it
Where the paper says it
The detailed proof structure involves:
-
Proof of Theorem 1.15: Relies on minimizing DKL(q vector | m/N) + phi L(H(q vector)) over a constrained set, utilizing partitioning techniques (P 0) and convexity arguments (Theorem 5.3).
-
Proof of Theorem 1.14: Establishes matching lower bounds by considering the case where q vector has a small sum of entries (sum q vector at most delta pN), and then rescaling q vector to an integer sum m, relating the probability bound back to the original variational problem.
-
Basic Reductions (Lemmas 6.2 and 6.3): Show correspondences between various objective functions (Q and W) relevant to subgraph counts in random graphs, confirming that minimizers of related variational problems satisfy | q vector| infinity = O(m/N).
-
Solving Variational Problems: Proves propositions and theorems for subgraph counts using Lemma 7.2 (Sidorenko property), Lemma 6. p. 5
3, and analysis of objective functions via Lemmas 7. p. 6Where the paper says it
2, in some special cases. The Sidorenko property.
4, 7.5, and 7.7 (for triangles). p. 0Where the paper says it
8 1 c t Figure 2. Stationary points of the objective function F(r, t).
Where the paper says it
Curiously, the answer to this question changes qualitatively around p = 1/ √ n. Indeed, writing XK3 (G) for the number of triangles in G, it is well-known that log P[G is triangle-free] = −(1 + o(1)) EXK3 (G) if p ≪ 1/ √ n, (1.
-
Proof of Theorem 1.8: Employs the Erdős–Stone–Simonovits theorem to show that minimizers W are close in cut metric to balanced complete k-partite graphons, concluding with a convexity argument showing the existence of a minimizer where partition sizes are equal and functions are constant.
-
Proofs for Theorems 1.17 and 1.20: These proofs utilize Lemma 5.4 to bound specific terms (e. p. 3
g., qxyz at most O(m/N)) and subsequently compute the required DKL terms, relying on Lemmas 8. p. 3Where the paper says it
In a certain regime where the “activity parameter” of the model is below the so-called Gibbs uniqueness threshold for a certain tree associated with H, such marginals can be estimated via a fixed point of a belief propagation operator. This uniqueness threshold dictates the upper bound on p or m in terms of H and z that is required for the arguments in [48, 49] to work.
4 and 8.10 to establish the final inequalities for PH[R]. p. 0Where the paper says it
In a certain regime where the “activity parameter” of the model is below the so-called Gibbs uniqueness threshold for a certain tree associated with H, such marginals can be estimated via a fixed point of a belief propagation operator. This uniqueness threshold dictates the upper bound on p or m in terms of H and z that is required for the arguments in [48, 49] to work.
Where the paper says it
In the subcritical regime, the probability is of “Poisson type” (note that a Poisson(µ) random variable is zero with probability exp(−µ)), and the bound in (1. 1) can be proved by quite generic large deviation inequalities (see e.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
General method for deriving lower tail large deviation principles in nonlinear problems can be applied to study critical regimes where nonlinearities are not sparse enough for Poissonian lower tails but combinatorial effects do not dominate. This allows for characterizing rate functions in terms of solutions to analytic variational problems, which is useful when explicit solutions are intractable.
-
The system can perform phase transition analysis by solving the associated analytic variational problem, as demonstrated by the single phase transition at c approximately equal to 4.341 for triangle-free probability in a random graph G(n, p).
-
The AI can solve specific instances of these variational problems using computational tools like interval arithmetic and AI techniques to find dual certificate functions, enabling the confirmation of sharp phase transitions.
-
It can derive asymptotic bounds for subgraph counts in random graphs by interpreting them as special cases of a general framework concerning lower tail large deviations for the number of hyperedges in a random vertex subset of a hypergraph.
-
The system can solve combinatorial problems related to Steiner triple systems and Latin squares by applying the derived methods, leading to new estimates on anti-Pasch configurations and 2 times 2 Latin subsquares.
-
The AI can use the general theorems for hypergraph lower tails (Theorems 1.12 to 1.15) to characterize the lower tail large deviation rate function of a random vertex subset of a hypergraph under various conditions on the graph structure and degree-boundedness.
-
The system can solve variational problems in Corollary 1.2 by solving them in special cases, such as for triangle-free graphs (Theorem 1.6) and edge-critical graphs (Theorem 1.8), providing explicit solutions to these problems for specific configurations of the optimizer W(r, t).
-
The AI can handle complex sequential enumeration problems by breaking down the lower-tail event into typical statistics of length two paths, which are related to Hthreats H(k), allowing for a decomposition based on copies of these graphs.
-
It can deduce lower bounds on the number of order n Latin squares with property N2 by applying Theorem 1.20, which is a Poisson-type tail bound derived from the general framework.
-
The system can prove lower bounds on the number of independent sets in a hypergraph for specific test functions, such as uniform test hypergraphs, by utilizing Theorem 5.3 and its associated machinery involving book hypergraphs.
Abstract
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))).
Sources
- 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
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- An involution on Dyck paths in the region at most (,) that interchanges area and dinv