Pith. sign in

REVIEW 2 major objections 3 minor 69 references

Lower tails for triangles inside the critical window

T0 review · 2 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves the first leading-order asymptotics for lower-tail triangle counts at p = c/√n, with a phase transition for small eta.

desk verdict Correct leading constant for lower-tail triangle counts in the critical window, but Theorem 1.1 as printed has a real typo that should be fixed before publication. read the letter →

arxiv 2411.18563 v1 pith:HAM2JALJ submitted 2024-11-27 math.PR math.CO

Matthew Jenssen , Will Perkins , Aditya Potukuchi , Michael Simkin This is my paper · ORCID
classification math.PRmath.CO MSC 05C8005C3060F10
keywords lowertaillargedeviationstrianglecountsrandomgraphscriticalwindowpartitionfunctionclusterexpansionphasetransitionLambertW
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves the first leading-order large-deviation formula for the probability that G(n,p) has at most eta times its expected number of triangles when p = c/√n, the critical window where both Poisson and dense-graph approximations fail. The rate function is given explicitly in terms of the Lambert-W function and a fixed-point parameter zeta, for all eta at least about .4993 and for small enough c otherwise. Triangle-freeness is included: for c < $e^{{-1/2}}$, the logarithm of the triangle-free probability is pinned to leading order. A corollary shows that the rate function is non-analytic in c for small eta, a phase transition, while no such transition occurs for eta at least .4993. The proof works through a statistical-physics partition function that penalizes triangles, analyzed by local conditioning, cluster expansion, and concentration from contractive Markov chains.

What carries the argument

The central object is the partition function $Z(\lambda,\zeta)=\sum_G \lambda^{|G|}(1-\zeta)^{X(G)}$, which penalizes but does not forbid triangles; the derivative of its logarithm in $\lambda$ gives the expected edge count. Local conditioning on the graph with one vertex removed turns the neighborhood distribution into an anti-ferromagnetic Ising model on a graph, a pairwise model whose expected edge and triangle densities can be computed by the cluster expansion. The resulting fixed-point equation for the typical degree is solved by the Lambert-W function $W(x)$, the inverse of $x e^x$ on the positive reals, and this yields the rate-function formula. Concentration for the Gibbs measures comes from proving that the associated Glauber dynamics are contractive and applying long-term concentration inequalities for contractive Markov chains.

What would settle it

The most direct check is Lemma 6.1: compute, for c=0.5 and eta=0.5, the probability under $\mu_{\lambda,\zeta}$ that a graph has exactly M edges and triangle count between T0 and T; if this probability is $\exp(-\Omega(n^{3/2}))$ rather than $\exp(-o(n^{3/2}))$, the lower-bound identity (3.9) collapses and Theorem 1.1 does not follow.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes Theorem 1.1: for fixed c > 0 and eta in [0,1) with c < c(eta), when p = (1+o(1))c/√n, the lower-tail probability satisfies $$\lim_{n\to\infty} \frac{1}{$n^{{3/2}}$} \log P_p(X\le \eta EX) = \frac12\left[ W(2\zeta $c^{2}$)^{3/2} + \frac{3W(2\zeta $c^{2}$)^{1/2}}{3\sqrt{2\zeta}} - \frac{\log(1-\zeta)\eta $c^{3}$}{3} - c\right],$$ where zeta is the unique solution of $(1-\zeta)(W(2\zeta c^2)/(2\zeta c^2))^{3/2}=\eta$. The formula is analytic in c where it applies, and for eta at least eta* it applies for all c; for eta below about .0091, an analytic-continuation argument forces a non-analytic point, i.e., a phase transition. The paper also shows that, conditioned on the lower-tail event, the graph converges in normalized cut metric to G(n,q) with explicit q, while the typical number of triangles does not match G(n,q).

Load-bearing premise

The formula for the lower tail only goes through if the partition-function calculation can be converted into a true probability lower bound; that conversion rests on a delicate estimate that a constant fraction, at least $e^{-c^2}/3$, of non-edges in the penalized Gibbs measure are open, meaning adding them creates no triangle.

Editorial extensions

If this is right

  • The logarithm of the lower-tail probability is $n^{3/2}$ times a computable function, so the rate function can be compared directly with simulations and used as a benchmark.
  • For moderate lower tails with $\eta \ge \eta^*$, the rate function is analytic in $c$ for all $c>0$, so no phase transition occurs in the critical window.
  • For $\eta$ below about .0091, a phase transition occurs, and locating it exactly and proving uniqueness become concrete open problems.
  • Conditioned on the lower-tail event, the graph looks like $G(n,q)$ at cut scale but has a different typical triangle count, so cut-metric convergence does not imply subgraph-count convergence.
  • In the random graph $G(n,m)$ with $m=b n^{3/2}/2$, the lower-tail log probability matches a Poisson-type formula, and a phase transition occurs for every $\eta\in[0,1)$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • This goes beyond the paper: for $\eta$ between about .0091 and $\eta^*$, the proof covers only $c<c(\eta)$, so the analytic-continuation phase-transition argument does not settle whether a transition also occurs at or beyond the boundary $c(\eta)$; the formula alone does not rule out additional non-analyticities.
  • This goes beyond the paper: the $G(n,m)$ result suggests that in edge-conditioned random graph models, the lower-tail rate loses the Lambert-W optimization and follows the Poisson benchmark, a split that may hold for other balanced subgraphs, not just triangles.
  • This goes beyond the paper: the coexistence of cut-metric convergence to an Erdős-Rényi graph with failure of subgraph-count convergence may be a general signature of critical-window lower tails, worth testing for larger cliques and other subgraphs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper studies lower-tail large deviations for the number of triangles X in G(n,p) at the critical scale p = c/sqrt(n). The main theorem gives, for an explicit range of (c,eta), the first leading-order asymptotics of (1/n^{3/2}) log P_p(X <= eta E X) as an expression involving the Lambert-W function and an auxiliary parameter zeta defined by a fixed-point equation. The proof proceeds through a penalized partition function Z(lambda,zeta), estimates the expected edge and triangle counts under the associated Gibbs measure by local conditioning and the cluster expansion, and then transfers the partition-function estimate back to the lower-tail probability via point-probability estimates. The paper also derives structural results in the cut metric, establishes phase transitions for small eta in G(n,p) and for all eta in G(n,m), and discusses the absence of a transition for eta above about 0.4993.

Significance. If the central theorem is correct, it resolves the leading constant for triangle lower tails in the critical window for the first time, bridging the previously separate Poisson and replica-symmetric regimes. The proof is modular and mostly self-contained, with explicit hypotheses on c and eta and a clear separation between the statistical-physics estimates and the probabilistic transfer. The formula passes important consistency checks: as c -> 0 it recovers Janson's Poisson bound, and as c -> infinity it approaches Zhao's replica-symmetric bound. The structural cut-norm result and the contrasting G(n,m) phase-transition behaviour are valuable extensions.

major comments (2)
  1. [Section 3, Claim 3.1] differentiating (1.2) gives a different denominator; the proof of the monotonicity claim needs correction.
  2. [Section 2.4, Lemma 2.9] The transfer lemma used in the concentration argument has an invalid proof and is false as stated.
minor comments (3)
  1. [Eq. (1.1), Lemma 3.11] The same ambiguity affects sqrt(lambda n) log n in Section 4, which should be printed as sqrt(lambda n) * log n, not sqrt(lambda n log n).
  2. [Lemma 4.4 proof] This is a harmless typo but should be corrected.
  3. [Section 6.1, Definition 6.5] The point-probability estimates in Lemma 6.1 would also benefit from stating explicitly that mu(X in [T0,T]) is bounded below by the event |G|=M from Lemma 6.1; the current proof leaves this step implicit.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is self-contained and the auxiliary parameter zeta is derived, not fitted to the predicted probability.

full rationale

The derivation is self-contained and no load-bearing step reduces to its own inputs by construction. The auxiliary parameter zeta is not fitted to the quantity being predicted: it is defined as the unique solution of (1.2), and Claim 3.1 proves uniqueness and the bound e zeta c^2 < 1 needed for the cluster expansion. The central estimates in Lemma 3.2 are derived from local conditioning, the cluster expansion (Lemma 3.5, proved via Lemmas 5.1 and 5.4 with Lemma 2.5 proved in Appendix A), and Markov-chain concentration (Lemmas 3.7, 4.4, and 4.5), rather than assumed. Lemma 3.11 obtains log Z by integrating E_{theta,zeta}|G|/theta, and Lemma 3.10 converts this into the lower-tail probability through an upper bound and a lower bound that uses the point-probability estimate Lemma 6.1, whose proof in Claims 6.3-6.7 contains non-trivial counting content. The only self-citations are non-load-bearing: Lemma 2.5 is stated as similar to [43, Lemma 4.1] but is proved in Appendix A, and [44] appears only in the future-directions discussion. External results from Janson, Kozma-Samotij, and Zhao are used as independent benchmarks or as the external lower bound in Corollary 1.3, not to define the predicted formula. The possible typographical inconsistency in the displayed formula (1.1) raised by a skeptical reading is a correctness concern about the statement, not a circularity of the derivation, since the proof of Theorem 1.1 and Lemma 3.11 use the internally consistent form. Score 0.

Assumptions & free parameters 1 free parameters · 7 assumptions · 0 invented entities

No numbers are fitted to data. The input parameters c, eta, b are fixed by the problem; the auxiliary parameter zeta is the unique solution of the fixed point equation (1.2), determined by the constraint E_{mu_{lambda,zeta}} X approximately eta E_p X, so it carries no free degree of freedom. No new particles, forces, conserved quantities, dimensions, or ledger entities are introduced. The Gibbs measures mu_{lambda,zeta} and nu_{H,lambda,zeta} are standard statistical physics models on graphs.

free parameters (1)
  • zeta (Gibbs penalty parameter) = unique solution of (1-zeta)(W(2 zeta c^2)/(2 zeta c^2))^{3/2} = eta
    Auxiliary tilting parameter in the partition function Z(lambda,zeta). It is not fitted to observed data: it is determined by the constraint that the expected triangle count under mu_{lambda,zeta} equals the target eta E_p X. Listed for completeness; it carries no free degree of freedom beyond the problem inputs c and eta.
assumptions (7)
  • standard math Vu's concentration inequality for subgraph counts in G(n,p) [65]
    Invoked in Corollary 3.8 to bound the number of short cycles in H=G-v drawn from the conditional Gibbs measure; it transfers to mu_{lambda,zeta} through stochastic domination (Lemma 2.2).
  • standard math Penrose's tree-graph bound (Lemma A.1)
    Used in Appendix A to prove the cluster expansion convergence bound (Lemma 2.5), which controls the error in the tree approximation of the Ising partition function.
  • standard math Kozma-Samotij mean-field lower bound (Lemma 8.1)
    Used in the proof of Corollary 1.3 to lower-bound the rate function phi_eta(c) by the variational quantity Phi_{n,p}(eta-epsilon) for large c.
  • standard math Zhao's Theorem 2.6 (Lemma 8.3) on the strict gap between mean-field and replica symmetric bounds for eta < eta_l ~ 0.0091
    Load-bearing for the phase-transition conclusion for 0<eta<eta_l; the paper quotes it from [69] and does not reprove it.
  • standard math Standard concentration tools: Chernoff bound, Azuma's inequality, Freedman's martingale inequality
    Used in Corollary 2.3, Claim 4.6, Claim 6.6 and elsewhere to control degrees and triangle counts.
  • standard math Uniqueness of analytic continuation
    Underpins Corollaries 1.3, 1.4 and 1.10: a rate function that is analytic and agrees with an analytic formula on an interval would have to agree everywhere, so a contradiction with a lower bound forces a non-analytic point.
  • domain assumption Domain assumption: the Erdős-Rényi null model and the lower-tail event {X <= eta E X}
    The entire problem is posed in G(n,p) with p=c/sqrt(n) and in G(n,m) with m=b n^{3/2}/2; results are only meaningful under these model assumptions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Lower tails for triangles inside the critical window." pith.science (2026). https://pith.science/paper/HAM2JALJ

@misc{pith2026241118563,
  author       = {Pith},
  title        = {Pith review of: Lower tails for triangles inside the critical window},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HAM2JALJ}},
  note         = {Machine review of arXiv:2411.18563}
}
abstract

We study the probability that the random graph $G(n,p)$ is triangle-free. When $p =o(n^{-1/2})$ or $p = \omega(n^{-1/2})$ the asymptotics of the logarithm of this probability are known via Janson's inequality in the former case and via regularity or hypergraph container methods in the latter case. We prove for the first time an asymptotic formula for the logarithm of this probability when $p = c n^{-1/2}$ for $c$ a sufficiently small constant. More generally, we study lower-tail large deviations for triangles in random graphs: the probability that $G(n,p)$ has at most $\eta$ times its expected number of triangles, when $p = c n^{-1/2}$ for $c$ and $\eta \in [0,1)$ constant. Our results apply for all $c$ if $\eta \ge .4993$ and for $c$ small enough otherwise. For $\eta$ small (including the case of triangle-freeness), we prove that a phase transition occurs as $c$ varies, in the sense of a non-analyticity of the rate function, while for $\eta \ge .4993$ we prove that no phase transition occurs. On the other hand for the random graph $G(n,m)$, with $m = b n^{3/2}$, we show that a phase transition occurs in the lower-tail problem for triangles as $b$ varies for \emph{every} $\eta \in [0,1)$. Our method involves ingredients from algorithms and statistical physics including the cluster expansion and concentration inequalities for contractive Markov chains.

Figures

Figures reproduced from arXiv: 2411.18563 by the authors.

Figure 1
Figure 1. The RHS of Theorem 1.1 for η = 1/2 (blue) plotted as a function of c against the Poisson bound (orange) and the replica symmetric bound (green), with all three functions scaled by a factor c −2 . Then we say a phase transition occurs at some c ∗ > 0 if the function φη(c) is non-analytic at c = c ∗ . Corollary 1.3. A phase transition for triangle-freeness in G(n, p) occurs at p = c ∗/ √ n for some c ∗ ∈ [1/ √ e, 4.34… view at source ↗
Figure 2
Figure 2. The RHS of Corollary 1.2 (blue) plotted against the lower bound of −c/4 (orange) on φ0(c) defined in (1.3). After these functions cross, the formula in Corollary 1.2 cannot hold. For dense graphs (p constant), the result of Chatterjee and Varadhan [17] states that whp G(n, p) conditioned on the large deviation event in question is close in cut metric to a graphon achieving the optimum of the variational problem ment… view at source ↗
Figure 3
Figure 3. The edge density q (scaled by p −1 ) of the conditional distribution for the lower-tail event when η = 1/2 as a function of c (in blue); the horizontal lines mark the edge density of the unconditioned random graph (in orange) and of the random graph achieving the target number of triangles (in green). This gives another visualization of the interpolation between the Poisson and replica symmetric bounds shown in [PI… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

69 extracted references · 68 canonical work pages

  1. [1]

    F. Augeri. Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erd˝ os–R´ enyi graphs. The Annals of Probability , 48(5):2404–2448, 2020. 2

    work page 2020

  2. [2]

    Balogh, R

    J. Balogh, R. Morris, and W. Samotij. Independent sets in hypergraphs. Journal of the American Math- ematical Society, 28(3):669–709, 2015. 9, 11

    work page 2015

  3. [3]

    Balogh, R

    J. Balogh, R. Morris, and W. Samotij. The method of hypergraph containers. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018 , pages 3059–3092. World Scientific, 2018. 2

    work page 2018

  4. [4]

    A. D. Barbour, G. R. Brightwell, and M. J. Luczak. Long-term concentration of measure and cut-off. Stochastic Processes and their Applications , 2019. 10, 17

    work page 2019

  5. [5]

    Bayati, D

    M. Bayati, D. Gamarnik, and P. Tetali. Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. The Annals of Probability , 41(6):4080–4115, 2013. 11

    work page 2013

  6. [6]

    B. B. Bhattacharya, S. Ganguly, E. Lubetzky, and Y. Zhao. Upper tails and independence polynomials in random graphs. Advances in Mathematics , 319:313–347, 2017. 2

    work page 2017

  7. [7]

    B. B. Bhattacharya, S. Ganguly, X. Shao, and Y. Zhao. Upper tail large deviations for arithmetic pro- gressions in a random set. International Mathematics Research Notices , 2020(1):167–213, 2020. 2

    work page 2020

  8. [8]

    Biskup, L

    M. Biskup, L. Chayes, and S. A. Smith. Large-deviations/thermodynamic approach to percolation on the complete graph. Random Structures & Algorithms , 31(3):354–370, 2007. 8

    work page 2007

Show all 69 references
  1. [9]

    Bollob´ as

    B. Bollob´ as. Threshold functions for small subgraphs. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 90, pages 197–206. Cambridge University Press, 1981. 2

    1981

  2. [10]

    Bollob´ as, C

    B. Bollob´ as, C. Borgs, J. T. Chayes, J. H. Kim, and D. B. Wilson. The scaling window of the 2-SAT transition. Random Structures & Algorithms , 18(3):201–256, 2001. 8

    2001

  3. [11]

    Borgs, J

    C. Borgs, J. T. Chayes, H. Kesten, and J. Spencer. The birth of the infinite cluster: finite-size scaling in percolation. Communications in Mathematical Physics , 224:153–204, 2001. 8

    2001

  4. [12]

    Borgs and R

    C. Borgs and R. Koteck` y. A rigorous theory of finite-size scaling at first-order phase transitions. Journal of Statistical Physics , 61:79–119, 1990. 8

    1990

  5. [13]

    Bubley and M

    R. Bubley and M. Dyer. Path coupling: A technique for proving rapid mixing in Markov chains. In Proceedings 38th Annual Symposium on Foundations of Computer Science , pages 223–231. IEEE, 1997. 16, 19

    1997

  6. [14]

    Chatterjee

    S. Chatterjee. The missing log in large deviations for triangle counts. Random Structures & Algorithms , 40(4):437–451, 2012. 2

    2012

  7. [15]

    Chatterjee

    S. Chatterjee. Large deviations for random graphs. Lecture Notes in Mathematics , 2197, 2017. 6

    2017

  8. [16]

    Chatterjee and A

    S. Chatterjee and A. Dembo. Nonlinear large deviations. Advances in Mathematics , 299:396–450, 2016. 2, 3 LOWER TAILS FOR TRIANGLES INSIDE THE CRITICAL WINDOW 47

    2016

  9. [17]

    Chatterjee and S

    S. Chatterjee and S. S. Varadhan. The large deviation principle for the Erd˝ os-R´ enyi random graph. European Journal of Combinatorics , 32(7):1000–1017, 2011. 1, 3, 6

    2011

  10. [18]

    B. Chin. Structure of lower tails in sparse random graphs. arXiv preprint arXiv:2312.12673 , 2023. 6

    2023 arXiv

  11. [19]

    Cook and A

    N. Cook and A. Dembo. Large deviations of subgraph counts for sparse Erd˝ os–R´ enyi graphs. Advances in Mathematics , 373:107289, 2020. 2

    2020

  12. [20]

    N. A. Cook, A. Dembo, and H. T. Pham. Regularity method and large deviation principles for the Erd˝ os–R´ enyi hypergraph.Duke Mathematical Journal , 173(5):873–946, 2024. 2

    2024

  13. [21]

    Davies, M

    E. Davies, M. Jenssen, W. Perkins, and B. Roberts. Independent sets, matchings, and occupancy fractions. Journal of the London Mathematical Society , 96(1):47–66, 2017. 10

    2017

  14. [22]

    Davies, M

    E. Davies, M. Jenssen, W. Perkins, and B. Roberts. On the average size of independent sets in triangle-free graphs. Proceedings of the American Mathematical Society, 146(1):111–124, 2018. 10

    2018

  15. [23]

    DeMarco and J

    R. DeMarco and J. Kahn. Tight upper tail bounds for cliques. Random Structures & Algorithms , 41(4):469–487, 2012. 2

    2012

  16. [24]

    Dembo, A

    A. Dembo, A. Montanari, and N. Sun. Factor models on locally tree-like graphs.The Annals of Probability, pages 4162–4213, 2013. 23

    2013

  17. [25]

    Duminil-Copin

    H. Duminil-Copin. Lectures on the Ising and Potts models on the hypercubic lattice. In PIMS-CRM Summer School in Probability , pages 35–161. Springer, 2017. 11

    2017

  18. [26]

    Dyer and A

    M. Dyer and A. Frieze. Randomly coloring graphs with lower bounds on girth and maximum degree. Random Structures & Algorithms , 23(2):167–179, 2003. 16

    2003

  19. [27]

    R. Eldan. Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large devi- ations. Geometric and Functional Analysis , 28(6):1548–1596, 2018. 2, 3

    2018

  20. [28]

    Erd˝ os, D

    P. Erd˝ os, D. Kleitman, and B. Rothschild. Asymptotic enumeration of Kn-free graphs. Colloquio Inter- nazionale sulle Teorie Combinatorie (Rome, 1973) , (17):19–27, 1973. 2, 12

    1973

  21. [29]

    Erd˝ os and A

    P. Erd˝ os and A. R´ enyi. On the evolution of random graphs.Publ. Math. Inst. Hung. Acad. Sci, 5(1):17–60,

  22. [30]

    W. G. Faris. Combinatorics and cluster expansions. Probability Surveys, 7:157–206, 2010. 15, 48

    2010

  23. [31]

    D. A. Freedman. On Tail Probabilities for Martingales. The Annals of Probability , 3(1):100 – 118, 1975. 39

    1975

  24. [32]

    Friedli and Y

    S. Friedli and Y. Velenik. Statistical Mechanics of Lattice Systems: a Concrete Mathematical Introduction. Cambridge University Press, 2017. 4

    2017

  25. [33]

    Galvin and J

    D. Galvin and J. Kahn. On phase transition in the hard-core model on Zd. Combinatorics, Probability and Computing , 13(2):137–164, 2004. 34

    2004

  26. [34]

    Galvin, G

    D. Galvin, G. McKinley, W. Perkins, M. Sarantis, and P. Tetali. On the zeroes of hypergraph independence polynomials. Combinatorics, Probability and Computing , 33(1):65–84, 2024. 11

    2024

  27. [35]

    Guerra and F

    F. Guerra and F. L. Toninelli. The thermodynamic limit in mean field spin glass models. Communications in Mathematical Physics , 230:71–79, 2002. 11

    2002

  28. [36]

    Harel, F

    M. Harel, F. Mousset, and W. Samotij. Upper tails via high moments and entropic stability. Duke Math- ematical Journal, 171(10):2089–2192, 2022. 2

    2022

  29. [37]

    V. Jain, F. Koehler, and A. Risteski. Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 1226–1236, 2019. 44

    2019

  30. [38]

    S. Janson. Poisson approximation for large deviations. Random Structures & Algorithms , 1(2):221–229,

  31. [39]

    Janson, T

    S. Janson, T. Luczak, and A. Ruci´ nski. An exponential bound for the probability of nonexistence of a specified subgraph in a random graph. In J. J. M. Karon´ nski and A.Ruci´ nski, editors, Random graphs 87, Pozn´ an, pages 73–87, 1987. 2, 8, 11, 12

    1987

  32. [40]

    Janson, K

    S. Janson, K. Oleszkiewicz, and A. Ruci´ nski. Upper tails for subgraph counts in random graphs. Israel Journal of Mathematics , 142:61–92, 2004. 2

    2004

  33. [41]

    Janson and A

    S. Janson and A. Ruci´ nski. The infamous upper tail. Random Structures & Algorithms , 20(3):317–342,

  34. [42]

    Janson and L

    S. Janson and L. Warnke. The lower tail: Poisson approximation revisited. Random Structures & Algo- rithms, 48(2):219–246, 2016. 3, 4, 8, 11

    2016

  35. [43]

    Jenssen, W

    M. Jenssen, W. Perkins, and A. Potukuchi. On the evolution of structure in triangle-free graphs. arXiv preprint arXiv:2312.09202, 2023. 6, 8, 9, 12, 15

    2023 arXiv

  36. [44]

    Jenssen, W

    M. Jenssen, W. Perkins, A. Potukuchi, and M. Simkin. Sampling, counting, and large deviations for triangle-free graphs near the critical density. In Foundations of Computer Science (FOCS 2024) , 2024. 12 48 LOWER TAILS FOR TRIANGLES INSIDE THE CRITICAL WINDOW

    2024

  37. [45]

    J. H. Kim and V. H. Vu. Concentration of multivariate polynomials and its applications. Combinatorica, 20(3):417–434, 2000. 2

    2000

  38. [46]

    Kozma and W

    G. Kozma and W. Samotij. Lower tails via relative entropy. The Annals of Probability , 51(2):665–698,

  39. [47]

    Y. P. Liu and Y. Zhao. On the upper tail problem for random hypergraphs. Random Structures & Algorithms, 58(2):179–220, 2021. 2

    2021

  40. [48]

    Lov´ asz.Large Networks and Graph Limits , volume 60

    L. Lov´ asz.Large Networks and Graph Limits , volume 60. American Mathematical Soc., 2012. 6

    2012

  41. [49]

    Lubetzky and Y

    E. Lubetzky and Y. Zhao. On the variational problem for upper tails in sparse random graphs. Random Structures & Algorithms , 50(3):420–436, 2017. 2, 45

    2017

  42. [50]

    M. Luczak. Concentration of measure and mixing for Markov chains. In Discrete Mathematics & Theo- retical Computer Science, pages 95–120, 2008. 10, 17

    2008

  43. [51]

    T. Luczak. On triangle-free random graphs. Random Structures & Algorithms , 16(3):260–276, 2000. 2, 6, 8, 11

    2000

  44. [52]

    E. McShane. Extension of range of functions. Bulletin of the American Mathematical Society , 40(12):837– 842, 1934. 29

    1934

  45. [53]

    Mousset, A

    F. Mousset, A. Noever, K. Panagiotou, and W. Samotij. On the probability of nonexistence in binomial subsets. Annals of Probability, 48(1):493–525, 2020. 9, 12

    2020

  46. [54]

    Ollivier

    Y. Ollivier. Ricci curvature of metric spaces. Comptes Rendus Mathematique , 345(11):643–646, 2007. 16

    2007

  47. [55]

    Osthus, H

    D. Osthus, H. J. Pr¨ omel, and A. Taraz. For which densities are random triangle-free graphs almost surely bipartite? Combinatorica, 23(1):105–150, 2003. 12

    2003

  48. [56]

    D. Paulin. Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electronic Journal of Probability , 20:1 – 32, 2015. 17

    2015

  49. [57]

    O. Penrose. Convergence of fugacity expansions for classical systems. Statistical Mechanics: Foundations and Applications, page 101, 1967. 48, 49

    1967

  50. [58]

    H. J. Pr¨ omel and A. Steger. On the asymptotic structure of sparse triangle free graphs.Journal of Graph Theory, 21(2):137–151, 1996. 2, 12

    1996

  51. [59]

    D. Ruelle. Statistical Mechanics: Rigorous Results . World Scientific, 1999. 4

    1999

  52. [60]

    Saxton and A

    D. Saxton and A. Thomason. Hypergraph containers. Inventiones mathematicae , 201(3):925–992, 2015. 11

    2015

  53. [61]

    A. D. Scott and A. D. Sokal. The repulsive lattice gas, the independent-set polynomial, and the Lov´ asz local lemma. Journal of Statistical Physics , 118(5-6):1151–1261, 2005. 15

    2005

  54. [62]

    Sly and N

    A. Sly and N. Sun. Counting in two-spin models on d-regular graphs. Annals of Probability, 42(6):2383– 2416, 2014. 23

    2014

  55. [63]

    Srinivasan

    A. Srinivasan. Concentration of measure for the analysis of randomized algorithms by devdatt p. dubhashi and alessandro panconesi cambridge university press, 2009. SIGACT News, 41(1):28–30, Mar. 2010. 32

    2009

  56. [64]

    Stark and N

    D. Stark and N. Wormald. The probability of non-existence of a subgraph in a moderately sparse random graph. Combinatorics, Probability and Computing , 27(4):672–715, 2018. 12

    2018

  57. [65]

    V. H. Vu. A large deviation result on the number of small subgraphs of a random graph. Combinatorics, Probability and Computing , 10(1):79–94, 2001. 24

    2001

  58. [66]

    N. C. Wormald. The perturbation method and triangle-free random graphs. Random Structures & Algo- rithms, 9(1-2):253–270, 1996. 12

    1996

  59. [67]

    Yang and T.-D

    C.-N. Yang and T.-D. Lee. Statistical theory of equations of state and phase transitions. I. theory of condensation. Physical Review, 87(3):404, 1952. 4

    1952

  60. [68]

    S. Zhang. A note on the zero-free region of hypergraph independence polynomials. arXiv preprint arXiv:2305.17822, 2023. 11

    2023 arXiv

  61. [69]

    Y. Zhao. On the lower tail variational problem for random graphs. Combinatorics, Probability and Com- puting, 26(2):301–320, 2017. 2, 3, 4, 5, 6, 44, 45 Appendix A. Proof of Lemma 2.5 We use the tree–graph bound of Penrose [57]; see [30, Section 4] for a discussion. LOWER TAIL...

    2017

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.