{"id":"8680903a-31ba-4336-86c0-c9dab73148ec","arxiv_id":"2506.12752","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For correlated Erdős-Rényi graphs with constant average degree, strong detection is information-theoretically possible if and only if the subsampling probability s exceeds min{1/√λ, √α}, with α≈0.338.","lead":"The paper pinpoints the exact condition under which a statistician can tell two correlated random graphs apart from two independent random graphs, when the graphs have constant average degree. The threshold is s > min{1/√λ, √α}, where λ is the average degree of the parent graph, s is the subsampling probability, and α≈0.338 is Otter's constant.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower-bound proof assumes λ²s < 1−ε in (2.1), while the theorem's lower regime only guarantees λs² < 1−ε; for λ>1 these differ, so the claimed range is unproved unless (2.1) is corrected to λs².","rationale":"The central claim is a sharp threshold, with the upper bound imported from [11,31]; the real burden is the lower bound in Section 2. My main concern is not the use of Otter's constant: that is a classical asymptotic, and the weaker form f_k = O(α^{−k}/k^{1.5}) used in Lemma 2.5 is enough to make the forest generating function converge for t < α. The soft spot is the mismatch between the theorem's lower regime and the standing assumption (2.1). The theorem requires TV = 1 − Ω(1) whenever s < min{1/√λ, √α} − ε, but the proof begins by assuming λ²s < 1−ε. For λ > 1, the former does not imply the latter, and the missing interval is nonempty for all λ > 1 (e.g., λ = 2, s = 0.5). Lemma 2.1, the only place where a positive-probability event is created, needs the expected number of cycles in Hπ* to be bounded away from 1; that condition is λs² < 1−ε, not λ²s < 1−ε, and all later estimates use only λs². Hence the printed proof is internally inconsistent with the theorem: either (2.1) should be λs² < 1−ε, or an additional argument is needed for λ²s ≥ 1−ε. Since the correction seems mechanical and no visible step requires the stronger bound, I do not think the result is wrong; but a conditional verdict is appropriate until the typo is confirmed and the proof is checked with the corrected assumption. The reader's Otter-based concern is real but secondary, since the external asymptotic is standard and its use is only to ensure convergence of the forest generating function.","tokens_in":11279,"tokens_out":26302,"duration_ms":323385,"concrete_test":"Check whether every use of (2.1) in Section 2 remains valid after replacing it by λs² < 1−ε, the cycle condition implied by s < min{1/√λ, √α} − ε. Concretely, re-derive Lemma 2.1 and the product bound leading to (2.17) with λs² in place of λ²s; if the argument goes through verbatim, then (2.1) is a typo and the theorem stands. If some step genuinely requires λ²s < 1, the proof must supply a separate treatment of the remaining interval.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 2 begins with \"we may assume λ²s < 1−ε and s < √α − ε\" (2.1), but Theorem 1.1's lower-bound hypothesis is s < min{1/√λ, √α} − ε. For a constant λ > 1 this does not imply λ²s < 1−ε; for example λ = 2, s = 0.5 satisfies s < √α and s < 1/√λ, yet λ²s = 2. Consequently Lemma 2.1's positive-probability event A (which needs P*(A) > c from the cycle count in Hπ* ~ G(n, λs²/n)) is not established on the full lower regime, and Proposition 2.2 is only proven under the stricter condition λ²s < 1−ε. Tracing the proof, the only cycle-smallness actually used is λs² < 1−ε: Lemma 2.1 estimates cycles with edge probability λs²/n, Lemma 2.4 uses λs²/n for full orbits, and the short-orbit factor in (2.16)–(2.17) has exponent λs²(2s−1)/n. No displayed estimate requires the stronger λ²s < 1. Thus the printed assumption looks like a typo for λs² < 1−ε, but as written the proof leaves the interval s ∈ (1/λ², min{1/√λ, √α}) uncovered for every λ > 1. That is load-bearing because the theorem explicitly asserts impossibility throughout that interval; a reader cannot verify the central claim without either a corrected (2.1) or an additional argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the information-theoretic detection problem between a pair of correlated Erdős-Rényi graphs formed by subsampling a common parent G(n, λ/n) with probability s, and a pair of independent Erdős-Rényi graphs with matching marginals. The main result, Theorem 1.1, asserts a sharp threshold: strong detection is possible if and only if s > min{1/√λ, √α}, where α ≈ 0.338 is Otter's constant. The paper proves the lower bound (impossibility below threshold) by a conditional second-moment calculation: it conditions on the acyclic event A in the intersection graph, decomposes the likelihood ratio over permutation orbits, and reduces the second moment to a forest-counting sum that converges below the Otter threshold. The upper bound (achievability) is not proved in the paper but is cited to [11] and [31].","tokens_in":11662,"tokens_out":23328,"duration_ms":255897,"significance":"If the proof is repaired, the result closes a constant gap in the detection threshold for constant-degree correlated Erdős-Rényi graphs, improving the previous lower bound of [44] (s < min{1/√λ, 0.1}) to the conjectured sharp value. The lower-bound argument is self-contained and parameter-free, using FKG, Cauchy-Schwarz, and Otter's tree enumeration, and it exposes the detection-recovery and information-computation gaps discussed in Section 1.1. However, as submitted the proof contains a load-bearing typo in the running assumption and a few incorrect intermediate estimates, so the theorem is not yet verified as written.","major_comments":[{"comment":"The proof assumes λ²s < 1−ε and s < √α − ε, but the lower-bound hypothesis of Theorem 1.1 is s < min{1/√λ, √α} − ε. For λ > 1 these conditions are not equivalent: taking λ = 2 and s = 0.5 gives s < √α and s < 1/√λ, yet λ²s = 2. The only smallness condition actually needed by the proof is λs² < 1−ε, which appears in Lemma 2.1 (the event A requires cycle probability λs²/n), in Lemma 2.4, and in the short-orbit factor of (2.16)–(2.17). As printed, the proof leaves the interval s ∈ (1/λ², min{1/√λ, √α}) uncovered for every λ > 1, so the claimed impossibility range is unproved. The assumption should be corrected to λs² < 1−ε, and the proof re-verified under that condition.","section":"§2, Eq. (2.1)"},{"comment":"The bound for |O| ≥ 2 is stated as 1 + O(n^{-2}). Expanding (2.10) to first order gives 1 − 2|O| s^{2|O|} λ(1−s)/n + O(n^{-2}), which is strictly smaller than 1 for large n, not 1 + O(n^{-2}). The displayed inequality is therefore false as written. Since the exact formula (2.10) actually implies the factor is < 1 for all |O| ≥ 2, the subsequent step can be repaired by bounding the product over non-full long orbits by 1, but the current text needs correction.","section":"§2, Lemma 2.3, Eq. (2.11)"},{"comment":"The passage from the conditional expectation to (2.16) is not valid as written. For a permutation σ with many fixed edges (e.g., σ = identity), |O1(J)| can be Θ(n²), and the product ∏_{O1}(1 + λs²(2s−1)/n) in (2.16) can be exponential in n when s > 1/2; this cannot be absorbed into the leading O(1) factor. The proof should multiply the O1 factor by the corresponding (1 − λs²/n)^{|O1|} from Lemma 2.4 before discarding it; the combined per-orbit factor is 1 − 2λs²(1−s)/n + O(n^{-2}) ≤ 1, so the final bound (2.17) is still within reach. As written, however, the intermediate inequality (2.16) does not follow from (2.15) and Lemma 2.4.","section":"§2, Eqs. (2.16)–(2.17)"}],"minor_comments":[{"comment":"The null model is described as two independent Erdős-Rényi graphs G(n, λ/n), but the body correctly defines Q as two independent G(n, λs/n) graphs; the abstract should be corrected.","section":"Abstract"},{"comment":"The parameters are introduced as λ, s ∈ (0, 1), but Theorem 1.1 allows λ > 1; the notation should read λ > 0, s ∈ (0, 1).","section":"Introduction, first paragraph"},{"comment":"The phrase \"in the second inequality\" should be \"in the second equality\", since the passage is an equality.","section":"§2, just before Eq. (2.13)"},{"comment":"The indexing in the list of unlabeled trees is written as \"1 ≤ i ≤ k\"; it should be \"1 ≤ i ≤ f_k\".","section":"Lemma 2.5"},{"comment":"Otter's asymptotic for unlabeled free trees is usually quoted with exponent k^{-5/2}; the displayed k^{-3/2} is harmless for the convergence argument, but the reference should be checked for accuracy.","section":"Lemma 2.5"},{"comment":"\"Cauchy-Schwartz\" should be \"Cauchy-Schwarz\".","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper's upper bound is entirely quoted from [11] and [31]; the novel part is the lower bound. The lower-bound strategy is sound in outline and the errors identified in the major comments appear to be repairable without changing the theorem statement. My recommendation of major revision is driven by the need to correct Eq. (2.1) and the estimates in Lemma 2.3 and Eqs. (2.16)–(2.17); these are exactly the load-bearing steps. No concerns about attribution or scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper closes the constant gap for strong detection in correlated Erdős-Rényi graphs with constant average degree, proving the sharp threshold min{1/√λ, √α}. The lower bound is the new piece, and it looks right. The proof uses a conditional second moment on the event that the intersection graph is acyclic, which has positive probability when λs² < 1. The orbit decomposition and the forest-counting via Otter's constant are handled carefully, and the self-contained lower-bound argument is sound. The upper bound is properly credited to prior work, so there is no circularity or fitted parameter here.\n\nThe soft spots are mostly typographical but they matter. Assumption (2.1) in Section 2 is printed as λ²s < 1−ε, while every displayed estimate in the proof uses λs²/n, and Lemma 2.1's positive-probability constant requires λs² < 1−ε. The theorem's hypothesis s < min{1/√λ, √α}−ε gives λs² < 1−ε for small ε, so the intended condition is clearly λs² < 1−ε. As printed, the proof would not cover the region s > 1/λ² for λ > 1, so this is a real error to correct, not a mere cosmetic one. It is, however, a typo, not a flaw in the argument. The abstract also misstates the null model as G(n,λ/n) instead of G(n,λs/n). Both fixes are straightforward.\n\nThe reliance on Otter's tree count is standard and correctly cited. I did not find any deeper issue with the second-moment step, the FKG argument, or the forest generating function bound. The paper is narrow in scope but it answers an open gap that several groups have been circling, and the technique—especially the treatment of short orbits—is clean enough to be reused.\n\nWho should read it: anyone working on graph matching, correlation detection, or hypothesis testing on sparse random graphs. It deserves a serious referee; I would send it out and accept after minor revision.","headline":"A sharp and essentially correct resolution of the strong detection threshold for sparse correlated Erdős-Rényi graphs, held back only by two typos that must be fixed.","tokens_in":12143,"tokens_out":5534,"would_cite":true,"duration_ms":59126,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","60C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that strong detection between two graphs subsampled from a common parent and two independent graphs with the same marginals is information-theoretically possible exactly when the subsampling probability exceeds…","keywords":["correlated Erdős-Rényi graphs","strong detection","information-theoretic threshold","Otter's constant","second moment method","total variation distance","graph matching","constant average degree"],"falsifier":"For a fixed constant $\\lambda$ such as $\\lambda=2$, simulate graph pairs at $s$ just below and just above $\\sqrt{\\alpha}\\approx 0.581$ and estimate the total variation distance; the theorem predicts $\\mathrm{TV}(P,Q)$ stays bounded away from $1$ below the boundary and tends to $1$ above it. A more direct check is to estimate the truncated second moment $\\mathbb{E}_P[(P/Q)\\mathbf{1}_A]$: the proof requires it to stay $O(1)$ for $s<\\min\\{1/\\sqrt{\\lambda},\\sqrt{\\alpha}\\}$ and to diverge above, so a single parameter value that violates this would refute the claimed threshold.","tokens_in":11102,"feed_emoji":"🔗","tokens_out":13597,"duration_ms":141638,"temperature":0.7,"pith_summary":"Two sparse random graphs that are subsampled from a single parent graph carry a hidden shared origin; the statistical question is whether an observer who sees only the two copies can tell that they are correlated rather than independent with the same edge density. This paper establishes the exact boundary for that question in the constant-average-degree regime: strong detection is possible if and only if the subsampling probability $s$ exceeds $\\min\\{1/\\sqrt{\\lambda}, \\sqrt{\\alpha}\\}$, where $\\alpha\\approx 0.338$ is Otter's constant, the growth rate of unlabeled trees. The result closes a constant-factor gap between previously known upper and lower bounds. The proof contributes a conditional second-moment technique that controls the likelihood ratio on a high-probability acyclic event, which should be useful for other sparse alignment problems.","feed_headline":"Sharp detection threshold found for correlated Erdős-Rényi graphs","feed_subtitle":"Resolves the constant-factor gap between prior upper and lower bounds.","key_machinery":"The proof is carried by the permutation-averaged likelihood ratio $L(A,B)=\\frac{1}{n!}\\sum_{\\pi}\\prod_e \\ell(A_e,B_{\\pi(e)})$, where $\\ell$ is the per-edge likelihood ratio. Fixing the latent alignment $\\pi^*$ and writing $\\sigma=(\\pi^*)^{-1}\\circ\\pi$, the product splits over the edge orbits of $\\sigma$; the short orbits, of length one, require a sharper estimate than previous work, which removes the earlier constant slack. On the event that the intersection graph is acyclic, the truncated second moment of the likelihood ratio collapses to a weighted forest count: each forest $J$ contributes $s^{2|E(J)|}$. Otter's constant $\\alpha\\approx 0.338$ is the radius of convergence of the unlabeled-tree generating function, and the classical asymptotic $f_k=O(\\alpha^{-k}/k^{1.5})$ makes the forest series converge precisely for $s^2<\\alpha$; the $1/\\sqrt{\\lambda}$ term in the threshold comes from requiring $\\lambda s^2<1$ so the intersection graph is subcritical and the acyclic event has positive probability.","core_discovery":"The central discovery is a sharp phase transition for the total variation distance between the correlated model $P$ and the independent model $Q$ with the same marginals. For any constant $\\epsilon>0$, if $s<\\min\\{1/\\sqrt{\\lambda},\\sqrt{\\alpha}\\}-\\epsilon$ then $\\mathrm{TV}(P,Q)=1-\\Omega(1)$, so no test can strongly distinguish the two distributions; if $s>\\min\\{1/\\sqrt{\\lambda},\\sqrt{\\alpha}\\}+\\epsilon$ then $\\mathrm{TV}(P,Q)=1-o(1)$, so strong detection is possible. The upper direction is assembled from existing statistics, densest subgraphs when $\\lambda s^2>1$ and tree counting when $s^2>\\alpha$. The lower direction is new: conditioning on the event $A$ that the intersection graph, the edges present in both copies under the latent alignment, is a forest, which occurs with probability bounded below by a constant, the proof shows $\\mathbb{E}_P[(P/Q)\\mathbf{1}_A]=O(1)$, which forces $\\mathrm{TV}(P,Q)=1-\\Omega(1)$. The calculation reduces to a weighted sum over forests $J$ of $s^{2|E(J)|}$, and Otter's asymptotic $f_k=O(\\alpha^{-k}/k^{1.5})$ for unlabeled trees makes this series converge exactly when $s^2<\\alpha$; the condition $s<1/\\sqrt{\\lambda}$ enters through the positivity of the acyclic event.","pith_inferences":["The conditional-second-moment technique, which works on a positive-probability acyclic event rather than a high-probability one, is likely transferable to other alignment problems on sparse random graphs, such as partially correlated Erdős-Rényi graphs where only constant-factor bounds are currently known.","The appearance of Otter's constant in the statistical limit for all $\\lambda<1/\\alpha$ suggests that tree counting is not just an algorithmic heuristic but captures the fundamental information-theoretic boundary whenever the intersection graph is subcritical; a testable extension is whether decorated-tree statistics can close the remaining gap for $\\lambda>1/\\alpha$.","Because the paper shows the impossibility region extends to $s<\\sqrt{\\alpha}$ for $\\lambda<1/\\alpha$, it implies that any future robust detector that survives $o(n)$ edge corruptions would have to beat the tree-counting statistic in the window $1/\\sqrt{\\lambda}<s<\\sqrt{\\alpha}$, or the robust and non-robust thresholds must separate there.","The same min-formula might generalize to other correlated latent-permutation models with binomial edges, such as sparse correlated stochastic block models, where the analogous threshold would be determined by the subcriticality of the shared-edge graph and the tree-counting radius."],"forward_implications":["The constant-factor gap between the previous best upper and lower bounds is closed: the sharp threshold is the minimum of $1/\\sqrt{\\lambda}$ and $\\sqrt{\\alpha}$.","For $\\lambda>1/\\alpha\\approx 2.96$, the detection threshold $1/\\sqrt{\\lambda}$ is smaller than $\\sqrt{\\alpha}$, so strong detection becomes possible exactly when partial recovery of the latent matching becomes possible.","For $\\lambda<1/\\alpha$, detection is possible once $s>\\sqrt{\\alpha}$ while recovery of the matching remains impossible until $s>1/\\sqrt{\\lambda}$, leaving a constant-factor detection-recovery gap.","Above the threshold, known efficient algorithms succeed (densest subgraphs when $\\lambda s^2>1$, tree counting when $s^2>\\alpha$); below it, no algorithm, efficient or not, can strongly detect the correlation.","In the regime $n^{-1+o(1)}\\le \\lambda=o(1)$, the threshold reduces to $\\sqrt{\\alpha}$, matching the tree-counting upper bound."],"supporting_citations":[{"why":"Supplies the upper bound for $\\lambda s^2>1$ via densest subgraphs and the basic second-moment approach that the proof follows.","marker":"[11]"},{"why":"Gives the partial-recovery threshold $s>1/\\sqrt{\\lambda}$, used to highlight the detection-recovery gap.","marker":"[12]"},{"why":"Supplies the upper bound for $s^2>\\alpha$ via tree counting.","marker":"[31]"},{"why":"Provides the asymptotic $f_k=O(\\alpha^{-k}/k^{1.5})$ for unlabeled trees that fixes the radius of convergence of the forest generating function.","marker":"[36]"},{"why":"Gives the previous lower bound and the orbit-decomposition technique (its Proposition 3) that the proof adapts.","marker":"[44]"}],"fun_headline_variants":["Exact limit for detecting correlated Erdős-Rényi graphs","Sharp phase transition for correlated graph detection","Constant gap resolved in correlated graph detection","Otter's constant sets correlated graph detection limit","Correlated Erdős-Rényi: exact detection threshold"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof imports the classical asymptotic $f_k=O(\\alpha^{-k}/k^{1.5})$ for the number of unlabeled trees, and the entire lower bound rests on the forest generating function converging at the radius this asymptotic dictates; if that asymptotic were inaccurate, the threshold $\\min\\{1/\\sqrt{\\lambda},\\sqrt{\\alpha}\\}$ would shift.","fun_headline_variants_meta":{"raw":{"variants":["Exact limit for detecting correlated Erdős-Rényi graphs","Sharp phase transition for correlated graph detection","Constant gap resolved in correlated graph detection","Otter's constant sets correlated graph detection limit","Correlated Erdős-Rényi: exact detection threshold"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001192,"raw_usage":{"total_tokens":4948,"prompt_tokens":1004,"completion_tokens":3944,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":620,"completion_tokens_details":{"reasoning_tokens":3872}},"tokens_in":620,"tokens_out":3944,"duration_ms":28233,"temperature":1.0,"reasoning_tokens":3872,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:45:30.813655+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a fixed constant $\\lambda$ such as $\\lambda=2$, simulate graph pairs at $s$ just below and just above $\\sqrt{\\alpha}\\approx 0.581$ and estimate the total variation distance; the theorem predicts $\\mathrm{TV}(P,Q)$ stays bounded away from $1$ below the boundary and tends to $1$ above it. A more direct check is to estimate the truncated second moment $\\mathbb{E}_P[(P/Q)\\mathbf{1}_A]$: the proof requires it to stay $O(1)$ for $s<\\min\\{1/\\sqrt{\\lambda},\\sqrt{\\alpha}\\}$ and to diverge above, so a single parameter value that violates this would refute the claimed threshold.","supporting_citations":[{"cited_title":"Ding and H","cited_arxiv_id":null,"evidence_quote":"Supplies the upper bound for $\\lambda s^2>1$ via densest subgraphs and the basic second-moment approach that the proof follows."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the upper bound for $s^2>\\alpha$ via tree counting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the asymptotic $f_k=O(\\alpha^{-k}/k^{1.5})$ for unlabeled trees that fixes the radius of convergence of the forest generating function."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the previous lower bound and the orbit-decomposition technique (its Proposition 3) that the proof adapts."}],"review_version":1}