Nonlinear lower-tail large deviations at criticality
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∼ 𝔾(n,p), and let L△(n,p)=logPr[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. 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, we show that there is no such phase transition for the probability that G is C2ℓ-free, for any fixed even cycle C2ℓ. 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(n2))).
Related
- Upper tail large deviations of the directed landscape
- Large and Moderate Deviations for Conservative Tail-Index Estimation
- Upper tail large deviations of regular subgraph counts in sparse random regular graphs
- Absolute deviations of the binomial about a prescribed centre: the tail expansion in closed form
- From Cauchy to Gaussian: Sharp Lower Deviations and Ehrhard-Type Inequality
BibTeX
@misc{kwan2026nonlinear,
title = {{Nonlinear lower-tail large deviations at criticality}},
author = {Matthew Kwan and Huy Tuan Pham},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10233},
eprint = {2610.10233},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10233},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Nonlinear lower-tail large deviations at criticality
AU - Matthew Kwan
AU - Huy Tuan Pham
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10233
UR - https://arxiv.org/abs/2610.10233
AB - 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∼ 𝔾(n,p), and let L_△(n,p)=logPr[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. 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, 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× 2 Latin subsquare (both tight up to a factor of exp(o(n^2))).
ER -