{"id":"5432f13a-8fd2-4d2b-b720-543fd92415ad","arxiv_id":"2411.18563","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"The lower-tail large deviation rate for triangle counts in the critical random graph is determined in closed form for part of the parameter plane, with phase transitions shown for small targets.","lead":"This paper computes the first exact formula for how unlikely it is for a random graph at a critical edge density to contain far fewer triangles than expected, including the case of no triangles at all. The result settles the leading exponential behavior in a regime where even the existence of the rate was open, and it shows that the problem undergoes phase transitions as the density varies.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.1's displayed formula is inconsistent with Lemma 3.11 and the proof; the W(2ζc²)^{3/2} term is missing a factor 1/(3√(2ζ)), so the stated rate function fails known small-c and large-c limits.","rationale":"The reader's weakest assumption was Lemma 6.1, a delicate point-probability estimate; I scrutinized Claims 6.3–6.7 and found the counting arguments and Freedman bound coherent, with no identified flaw. The more urgent issue is that the headline formula stated in Theorem 1.1 and the abstract is inconsistent with the paper's own Lemma 3.11 and with the proof's final line. The proof establishes the version with (W^{3/2}+3W^{1/2})/(3√(2ζ)) inside the bracket, not W^{3/2} alone. This is load-bearing because the main theorem's statement is the paper's central claim, and as printed it is mathematically false. The underlying argument appears sound up to this statement error, so the appropriate verdict is CONDITIONAL: the paper should be accepted only after the formula is corrected and the downstream figures and corollaries are checked against the corrected expression.","tokens_in":44675,"tokens_out":53291,"duration_ms":409013,"concrete_test":"Re-derive the small-c expansion of (1.1) using W(x)=x−x²+O(x³) and ζ→1−η. The printed formula has a linear term (√(2ζ)−1)c/2, while the corrected formula from the proof cancels the linear terms and gives −c³/6(1−η+η log η)+o(c³). Also compare the c→∞ limit: the printed formula gives a linear coefficient different from −(1/2)h(η^{1/3}) in Lemma 8.2, whereas the corrected formula matches. Checking these two asymptotic limits definitively distinguishes the two expressions.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central formula (1.1) as printed reads 1/2 [ W(2ζc²)^{3/2} + 3W(2ζc²)^{1/2}/(3√(2ζ)) − log(1−ζ)ηc³/3 − c ]. But Lemma 3.11 and the proof of Theorem 1.1 give log Z/n^{3/2} = (W(2ζc²)^{3/2} + 3W(2ζc²)^{1/2})/(6√(2ζ)), so after using Lemma 3.10 the rate function should be 1/2 [ (W^{3/2}+3W^{1/2})/(3√(2ζ)) − log(1−ζ)ηc³/3 − c ]. The first term's denominator 3√(2ζ) is missing in the statement. This is not cosmetic: expanding the printed formula as c→0 with ζ→1−η gives a spurious linear term (√(2ζ)−1)c/2, contradicting Janson's Poisson bound −c³/6(1−η+η log η). For large c the printed formula also disagrees with Lemma 8.2's replica-symmetric limit. The proof's derivation is internally consistent with the corrected formula, so the error appears to be in the statement only, but as written the central claim is false.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":44912,"tokens_out":57727,"duration_ms":493291,"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":[{"comment":"differentiating (1.2) gives a different denominator; the proof of the monotonicity claim needs correction.","section":"Section 3, Claim 3.1"},{"comment":"The transfer lemma used in the concentration argument has an invalid proof and is false as stated.","section":"Section 2.4, Lemma 2.9"}],"minor_comments":[{"comment":"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).","section":"Eq. (1.1), Lemma 3.11"},{"comment":"This is a harmless typo but should be corrected.","section":"Lemma 4.4 proof"},{"comment":"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.","section":"Section 6.1, Definition 6.5"}],"recommendation":"major_revision","confidential_remarks":"The core result appears correct and important, and the apparent factor error in Theorem 1.1 is a notation artifact rather than a mathematical inconsistency. The two proof issues I flagged are local and likely repairable, but they are load-bearing points in the argument as written, so the manuscript needs a careful revision before acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper delivers the thing that was actually open: an asymptotic formula for the log lower-tail probability of triangle counts at p = c/sqrt(n). Prior work had the rate up to constants; this gives the leading coefficient, including the previously mysterious triangle-free case for small c. That is a genuine advance, and the method is serious: local conditioning, cluster expansion for the anti-ferromagnetic Ising model, and Markov-chain concentration all work together in a modular way. The G(n,m) result and the phase-transition corollaries are also valuable and honestly flagged where they rely on external results like Zhao's variational bound.\n\nI owe you a correction to the reader's report: the stress-test note is right. Theorem 1.1's displayed formula, as written, drops the factor 1/(3 sqrt(2 zeta)) from the W^{3/2} term. The proof of Theorem 1.1 and Lemma 3.11 both give the correct expression with both terms over 6 sqrt(2 zeta), and the stated small-c and large-c limits only work with that factor. So this is a typo in the statement, not a flaw in the argument, but it is load-bearing as printed: a reader who applies Eq (1.1) without checking the proof gets a formula that fails the known Poisson and replica-symmetric limits. The authors need to fix the display, and the referee should confirm the fix is consistent.\n\nOther soft spots are proportional to their nature. Lemma 3.10's lower bound relies on the delicate point-probability estimate in Lemma 6.1; I did not verify every claim of Section 6.1 line by line, but the structure is coherent and the estimates are plausible. The concentration arguments in Section 4 are intricate but the contraction setup is standard and well executed. The reliance on Zhao's Lemma 8.3 for the phase-transition range is clearly stated, so there is no hidden circularity. Self-citation is not an issue here; the cited external bounds are from different groups and the dependence is explicit. I found no internal inconsistency beyond the typo, and no sign of fitted parameters: zeta is pinned down by a fixed-point equation, not tuned to match the answer.\n\nBottom line: this is an important paper that deserves a serious referee. Send it out, but insist that the statement of Theorem 1.1 be corrected to match the proof. After that fix, I would cite it and would bring it to the reading group.","headline":"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.","tokens_in":45536,"tokens_out":2005,"would_cite":true,"duration_ms":18647,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C30","60F10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves the first leading-order asymptotics for lower-tail triangle counts at p = c/√n, with a phase transition for small eta.","keywords":["lower tail large deviations","triangle counts","random graphs","critical window","partition function","cluster expansion","phase transition","Lambert W function"],"falsifier":"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.","tokens_in":1963,"feed_emoji":"🔺","tokens_out":2256,"duration_ms":111703,"temperature":0.7,"pith_summary":"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.","feed_headline":"First formula for rare triangle counts in critical random graphs","feed_subtitle":"It pins down the log-probability to leading order and finds a phase transition as density varies.","key_machinery":"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.","core_discovery":"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).","pith_inferences":["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."],"forward_implications":["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)$."],"supporting_citations":[{"why":"supplies the Janson-style exponential bound for low-density lower tails and the triangle-free rate in the regime the new formula must match.","marker":"[39]"},{"why":"gives the Poisson lower-tail asymptotics for c tending to 0 that the critical-window formula interpolates toward.","marker":"[38]"},{"why":"extends the Poisson lower-tail approximation and provides the c-to-0 benchmark used to compare the new formula.","marker":"[42]"},{"why":"provides the bipartite structural result for triangle-free random graphs at p=omega(n^{-1/2}) used as a lower bound to force a phase transition.","marker":"[51]"},{"why":"supplies the mean-field relative-entropy lower bound used in the phase-transition argument for G(n,p).","marker":"[46]"},{"why":"provides the two-block variational construction that beats replica symmetry for eta below about .0091, yielding the phase-transition range.","marker":"[69]"},{"why":"supplies the concentration inequalities for contractive Markov chains used to control edges, degrees, and triangles under the Gibbs measure.","marker":"[4]"},{"why":"supplies path coupling, the criterion used to prove contraction of the Glauber dynamics.","marker":"[13]"}],"fun_headline_variants":["Exact rare-triangle probabilities at critical density","Log-probability formula reveals phase transition in random graphs","Triangle lower tails: first sharp asymptotics in critical window","Phase transition in rare triangle counts at critical density","First explicit log-probability for rare triangles at criticality"],"cache_read_input_tokens":47488,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Exact rare-triangle probabilities at critical density","Log-probability formula reveals phase transition in random graphs","Triangle lower tails: first sharp asymptotics in critical window","Phase transition in rare triangle counts at critical density","First explicit log-probability for rare triangles at criticality"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00059,"raw_usage":{"total_tokens":2857,"prompt_tokens":1124,"completion_tokens":1733,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":740,"completion_tokens_details":{"reasoning_tokens":1655}},"tokens_in":740,"tokens_out":1733,"duration_ms":13113,"temperature":1.0,"reasoning_tokens":1655,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:06:51.528992+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Janson, T","cited_arxiv_id":null,"evidence_quote":"supplies the Janson-style exponential bound for low-density lower tails and the triangle-free rate in the regime the new formula must match."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the Poisson lower-tail asymptotics for c tending to 0 that the critical-window formula interpolates toward."},{"cited_title":"Janson and L","cited_arxiv_id":null,"evidence_quote":"extends the Poisson lower-tail approximation and provides the c-to-0 benchmark used to compare the new formula."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the bipartite structural result for triangle-free random graphs at p=omega(n^{-1/2}) used as a lower bound to force a phase transition."},{"cited_title":"Kozma and W","cited_arxiv_id":null,"evidence_quote":"supplies the mean-field relative-entropy lower bound used in the phase-transition argument for G(n,p)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the two-block variational construction that beats replica symmetry for eta below about .0091, yielding the phase-transition range."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the concentration inequalities for contractive Markov chains used to control edges, degrees, and triangles under the Gibbs measure."},{"cited_title":"Bubley and M","cited_arxiv_id":null,"evidence_quote":"supplies path coupling, the criterion used to prove contraction of the Glauber dynamics."}],"review_version":1}