Nonlinear lower-tail large deviations at criticality

arXiv:2610.10233 · math.CO, cs.DM, math.PR · Submitted 2026-10-07 · Read on arXiv

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 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. 1

Where the paper says it

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.

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

Where the paper says it

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 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. p. 0
Where the paper says it

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.

341. In contrast, no such phase transition is observed for the probability that G is C 2-free for any fixed even cycle C 2. p. 0
Where the paper says it

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ℓ.

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

Where the paper says it

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 ))).

The critical regime is characterized by p having an order of magnitude related to the graph H, specifically p about n-1/d 2(H) or m about n 2/2 - 1/d 2(H) for hypergraphs. p. 0
Where the paper says it

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.

In this regime, a single formula describes the asymptotic H-freeness probability for all p in (0, 1):

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

Where the paper says it

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).

These theorems establish upper bounds on the lower tail probabilities, such as Theorem 1. p. 8
Where the paper says it

We can now state the promised general lower tail estimates. We start with upper bounds on the lower tail.

12 and Theorem 1. p. 0
Where the paper says it

[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.

13, which relate these probabilities to a minimum over a variational problem:

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

Where the paper says it

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.

341.

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

Where the paper says it

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 ))).

17) and order- n Latin squares with property N2 (Theorem 1. p. 0
Where the paper says it

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 ))).

20). The lower bound matching Theorem 1. p. 8
Where the paper says it

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.

20 for the number of order- n Latin squares with property N infinity is an open problem addressed in Section 5, leading to Theorem 5. p. 0
Where the paper says it

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 ))).

3 concerning subsets constrained to have prescribed sizes in a partition of the vertex set. p. 7
Where the paper says it

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).

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

Where the paper says it

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.

14 and 1.15, which provide matching lower bounds for the number of copies of H in random subsets R about Bin(V, p). p. 8
Where the paper says it

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).

These results are derived from a complex analysis involving entropic methods and Poisson approximation lemmas. p. 1
Where the paper says it

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.

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

    Where the paper says it

    2, in some special cases. The Sidorenko property.

    3, and analysis of objective functions via Lemmas 7. p. 6
    Where the paper says it

    8 1 c t Figure 2. Stationary points of the objective function F(r, t).

    4, 7.5, and 7.7 (for triangles). p. 0
    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

    Where 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.

    g., qxyz at most O(m/N)) and subsequently compute the required DKL terms, relying on Lemmas 8. p. 3
    Where 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. 0
    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

  1. 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.

  2. 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).

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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).

  8. 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.

  9. 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.

  10. 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

Related papers