{"id":"0009766e-2c86-4deb-898e-1040eae65bb7","arxiv_id":"2608.06816","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For i.i.d. atomless edge weights, any two edges in a random minimum spanning tree satisfy P(both) ≤ 8 P(first)P(second), and on K_n the stronger P(both) ≤ P(first)P(second) holds for every n at least 3.","lead":"Random minimum spanning trees are shown to have bounded positive correlation between edges: for any graph with independent identical atomless edge weights, the probability two edges appear together is at most 8 times the product of their separate probabilities. On complete graphs the bound improves to true negative correlation at every size, and an exact identity connects this to the classical expected tree weight.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"I examined the proof chain for Theorem A end-to-end. The conditional negative correlation step (Lemma 3.3) is a correct Harris application after the coordinate change (U,1-V); the deletion sandwich (Lemma 3.4) gives both the upper bound a<=A,b<=B and the lower bounds a,b>=A/2; and the tail submultiplicativity (Lemma 3.1) correctly yields E[T^2]<=2(ET)^2. The chain E[c]<=E[ab]<=E[AB]<=2E[A]E[B]<=8P(e)P(f) has no missing constants and handles loops, bridges, parallel edges, and disconnected H. For the complete graph, Lemma 5.1's claim that cross-edge clocks are untouched and memoryless is correct, so the multiplicative coalescent transition (10) is valid. Lemma 5.4's conditional expectation of the degree functional uses uniformity of endpoints within components, which Lemma 5.1 provides; the expectation depends only on component sizes, so the history-level equality (11) is sound. The chronological bound (Lemma 5.5) is pathwise and sharp for combs; the reciprocal budget (Lemma 5.7) is an expectation bound, and its strictness for n>=4 follows because the post-first-merger state (2,1,...,1) violates the equality case of Lemma 5.6. Lemma 6.1's identification of H with nE[L_n] via the compensator of the accepted-merger jump process is a standard and valid martingale argument. The identity Proposition D1 then follows algebraically and agrees with small-n checks. The reader's weakest-assumption identification is reasonable: the i.i.d. common-law hypothesis is the theorem's boundary, and Theorem C proves it cannot be relaxed. But because the central theorems assume that hypothesis explicitly, this is not a flaw in the paper's claims. I found no load-bearing mathematical concern, so the recommendation is unchanged from the reader's ACCEPT.","tokens_in":1046,"tokens_out":1235,"duration_ms":253729,"concrete_test":"Run an exact rational brute-force check of Theorem A on all connected multigraphs with at most five vertices and seven edges (or, if exhaustive enumeration is too large, a random exact sample of such graphs), computing P(e,f in MST)/(P(e in MST)P(f in MST)) for every distinct edge pair by enumerating all edge orders; if any ratio exceeds 8, the deletion-sandwich or moment-bound step has a hidden flaw. The Appendix currently checks only graphs with at most four vertices and six edges, so extending the range one step would independently confirm the constant 8.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. The central claims (Theorem A, Theorems B1/B2, Proposition D1) are supported by internally consistent arguments. The i.i.d. common-law assumption is the most delicate premise: Section 1.4 and Theorem C show it is essential, since without it no universal constant exists even on K4. However, the theorems state this assumption explicitly, so the boundary is not an internal gap. The proof chain for Theorem A is sound: conditional Harris (Lemma 3.3), the deletion sandwich (Lemma 3.4), and the submultiplicative-tail moment bound (Lemma 3.1) fit together without hidden hypotheses, and multigraph degeneracies are covered in Section 3.5. The complete-graph proof is also coherent: Lemma 5.1 correctly identifies the accepted-merger coalescent, the pathwise accounting in Lemmas 5.3/5.5 is valid for every merger history, and the one-step convexity inequality of Lemma 5.6 is used only through the expectation bound in Lemma 5.7, so the absence of a pathwise upper bound for J (Remark 5.8) is not problematic. Lemma 6.1's martingale identity E[H]=nE[L_n] is legitimate. The only external inputs are the asymptotic expansions of [6] and [13], which are used exclusively for Corollary D3 and the rate statements in Corollary 6.3, not for the finite theorems.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies pairwise correlations of edge-inclusion indicators in the minimum spanning tree of a finite connected multigraph with independent identically distributed atomless edge weights. It proves Theorem A, a universal bound p_ef ≤ 8 p_e p_f; on K_n, Theorems B1 and B2 establish strict pairwise negative correlation for adjacent and disjoint pairs for every n≥3 and n≥4, respectively. The key exact identity is Proposition D1, E[deg(x)^2] = 10(n−1)/n − 4E[L_n], which reduces the complete-graph pair probabilities to the expected MST weight and yields the PWIT second-moment limit. The paper also gives explicit positive-correlation examples, including a simple graph, computes the maximum in a parallel-bundle family, and proves Theorem C that no universal constant survives when the edge laws are independent but not identical. The proofs are analytic; finite exact computations are documented in an appendix with a companion repository.","tokens_in":19557,"tokens_out":24823,"duration_ms":195110,"significance":"The universal factor 8 answers an open question of R. Lyons recorded by Tang and Zhang and appears to be the first uniform multiplicative bound for MST edge correlations. The complete-graph negative correlation at every size closes the adjacent-pair case left open in [19] and gives an effective proof of the disjoint-pair property without local weak convergence or Fatou's lemma. Proposition D1 is a clean finite identity with independent interest, and Corollary D3 identifies the degree second-moment limit with 10−4ζ(3). The paper is unusually careful: the central theorems are derived without fitted parameters, the finite theorems are cleanly separated from the asymptotic external inputs, and the computational appendix provides exact rational cross-checks, including several documented failed strengthenings. The main limitation, that Theorem A requires one common atomless law, is explicitly delimited by Theorem C rather than hidden.","major_comments":[],"minor_comments":[{"comment":"The harmonic-number expressions are ambiguous as submitted: Lemma 5.5 should state J≥H_n−1, and the strengthened lower bound in Corollary D2 should be 1+(H_n−1)/n−1/n^2. If H_{n−1} is read instead, the claimed equality at n=2 fails, so the typesetting should make the distinction explicit.","section":"§5.3, Lemma 5.5, Corollary D2"},{"comment":"The displayed identity H=n−1/n+J should be typeset as H=n−1/n+J (that is, n minus 1/n) and similarly in the proof of Theorem B1. In plain text the current notation can easily be misread as (n−1)/n, which would make the identity false; the surrounding algebra shows the intended meaning, but the ambiguity should be removed.","section":"§1.5, §5.3, Lemma 5.3"},{"comment":"Since Propositions 4.2–4.4 and Table 1 rely on exact rational computations, the companion repository and the archived DOI should be checked for permanence and versioning, and the manuscript should state which repository files reproduce each table row and certificate.","section":"Appendix A"},{"comment":"The asymptotic expansion R(t)=4t/45+46/75+O(t^{−1}) is mathematically correct, but a reader may expect O(1) after a growing main term; one sentence clarifying that the expansion is to constant order would improve readability.","section":"§4.4, Theorem C"}],"recommendation":"minor_revision","confidential_remarks":"The mathematical content is sound and the verification appendix strengthens confidence. I support publication after typographical corrections to the harmonic-number notation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: this paper settles the main open questions on pairwise edge correlations in random MSTs. Theorem A gives a universal factor 8 for i.i.d. atomless edge weights on finite connected multigraphs, answering the question from Tang-Zhang/Lyons. Theorems B1/B2 prove pairwise negative correlation on K_n for every n, including the adjacent case they had left open, and Proposition D1 ties the degree second moment to the expected MST weight. These are real results, and the proofs hold up.\n\nWhat is genuinely good: the structure is transparent. Conditional negative correlation on the frozen environment, then two bottleneck-distance sandwiches and a submultiplicative-tail second-moment bound, give the factor 8 with each factor accounted for. The complete-graph argument via the accepted-merger coalescent is the right frame, and the split between a pathwise lower bound and an expectation-only upper bound on J is careful; Remark 5.8 shows why the upper bound really needs the multiplicative law. The K4 family in Theorem C is a clean demonstration that the i.i.d. assumption is essential, and Remark 4.5 correctly explains why subdivision does not turn it into a counterexample to Theorem A. The exact computations are cross-checked by several routes, and code and data are public.\n\nSoft spots: the constant 8 is not optimal, and the paper says so; the optimal constant is only bracketed. The asymptotic corollaries inherit o(1) terms from cited expansions, so they are not effective; the paper flags this. Neither is a load-bearing flaw. I also want to note the finite-range claims in Section 4 (e.g., the hub-family maximum) are computer-assisted, but the certificates are exact and independent enumerations agree; I do not see a reproducibility problem. I did not rerun everything myself, but the evidence is solid.\n\nWho should read it: anyone working on minimum spanning trees, negative correlation of random subgraphs, or the multiplicative coalescent. The identity E[deg^2] = 10(n-1)/n - 4E[L_n] is a useful bridge and I expect it to be used. It should get a serious referee; my recommendation is to send it out, not desk reject. It is a strong accept for a good probability journal.","headline":"A clean, self-contained paper that settles the main open questions on MST pair correlations; the proofs are solid and the results are worth serious refereeing.","tokens_in":20154,"tokens_out":2822,"would_cite":true,"duration_ms":23935,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"pith_extraction":{"msc":["60C05","05C80","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"For any two edges of a random minimum spanning tree, the probability that both are in the tree is at most 8 times the product of their individual probabilities, and on the complete graph the naive negative-correlation inequality holds…","keywords":["minimum spanning tree","negative correlation","pair correlation","multiplicative coalescent","universal bound","complete graph","bottleneck distance","random edge weights"],"falsifier":"Run an exact dynamic program over edge orders, or sample exhaustively, on finite connected multigraphs with independent uniform edge weights and look for a pair of distinct edges with $\\mathbf{P}(e,f\\in T)>8\\,\\mathbf{P}(e\\in T)\\mathbf{P}(f\\in T)$; the paper's own exhaustive census over all small graphs finds ratios no larger than about $1.0048$, so any ratio above $8$ would refute Theorem A. Alternatively, compute $p_1$ on $K_n$ for large $n$: any $n\\geq 3$ with $p_1\\geq 4/n^2$, or any $n\\geq 4$ with $p_2\\geq 4/n^2$, would refute Theorems B1 and B2.","tokens_in":19129,"feed_emoji":"🌳","tokens_out":17580,"duration_ms":128274,"temperature":0.7,"pith_summary":"Random minimum spanning trees are not negatively correlated in general, but this paper proves that positive correlation is uniformly bounded: for any two distinct edges $e$ and $f$, the probability that both lie in the tree is at most 8 times the product of their individual probabilities, provided all edges receive independent weights from one common distribution with no atoms. On the complete graph $K_n$, the opposite conclusion holds: for every $n \\geq 3$ the naive inequality $\\mathbf{P}(e,f \\in T) \\leq \\mathbf{P}(e \\in T)\\mathbf{P}(f \\in T)$ is true, strictly, for adjacent pairs and for disjoint pairs when $n \\geq 4$, so the tree measure has full pairwise negative correlation at every size. The engine of the complete-graph result is an exact identity $\\mathbf{E}[\\deg(x)^2] = 10(n-1)/n - 4\\mathbf{E}[L_n]$ connecting the second moment of a vertex degree to the expected total weight $L_n$ of the minimum spanning tree; its asymptotic limit $10 - 4\\zeta(3)$ answers an open question. The paper also shows the common-law assumption is essential: once edges are allowed different laws, already on $K_4$ the correlation ratio tends to infinity, so no fixed constant can work.","feed_headline":"Factor 8 cap holds for every random minimum spanning tree","feed_subtitle":"On complete graphs, every edge pair is strictly negatively correlated at every size.","key_machinery":"For the universal bound, freeze all weights except the two marked edges $e,f$; conditionally on this environment, the indicators $\\mathbf{1}_{\\{e\\in T\\}}$ and $\\mathbf{1}_{\\{f\\in T\\}}$ are monotone in opposite directions, so a correlation inequality for monotone functions on product spaces gives conditional negative correlation pointwise. The remaining environmental covariance is controlled by the bottleneck distances $A$ and $B$ between the endpoints of $e$ and $f$ in the graph with both edges deleted (the smallest weight threshold at which the endpoints become connected): the conditional inclusion probability sits between $A/2$ and $A$, and the tail of such a distance is submultiplicative, $\\mathbf{P}(A>s+t)\\le \\mathbf{P}(A>s)\\mathbf{P}(A>t)$, which yields $\\mathbf{E}[A^2]\\le 2(\\mathbf{E}A)^2$. For the complete graph, the mechanism is the accepted-merger coalescent: giving every edge an independent rate-one exponential clock and accepting edges greedily produces the multiplicative coalescent, in which two blocks of sizes $a,b$ merge with probability proportional to $ab$. The identity $\\mathbf{E}[\\deg(x)^2] = 10(n-1)/n - 4\\mathbf{E}[L_n]$ emerges from the functional $H=\\sum(1/a+1/b)$ over the $n-1$ mergers, via the pathwise relation $H=(n-1)/n+J$; a chronological lower bound $J\\ge H_{n-1}$ gives the adjacent-pair theorem, and a one-step convexity bound $\\mathbf{E}[J]\\le (n-1)(n+2)/(4n)$ gives the disjoint-pair theorem.","core_discovery":"The paper establishes three intertwined results. Theorem A states that for every finite connected multigraph with independent and identically distributed atomless edge weights and distinct edges $e,f$, $\\mathbf{P}(e,f\\in T)\\leq 8\\,\\mathbf{P}(e\\in T)\\mathbf{P}(f\\in T)$, and the constant arises from a clean decomposition: conditional negative correlation for the two edge indicators given all other weights, plus a second-moment bound on the bottleneck distances between their endpoints. Theorems B1 and B2 state that on $K_n$, with $p_1$ and $p_2$ the joint inclusion probabilities of two fixed adjacent and two fixed disjoint edges, $p_1<4/n^2$ for all $n\\geq 3$ and $p_2<4/n^2$ for all $n\\geq 4$, settling the adjacent case left open and giving strict pairwise negative correlation at every size. Proposition D1, the key finite identity $\\mathbf{E}[\\deg(x)^2] = 10(n-1)/n - 4\\mathbf{E}[L_n]$, reduces both inequalities to bounds on the expected MST weight; combining it with known expansions yields $\\lim_n \\mathbf{E}[\\deg(x)^2] = 10 - 4\\zeta(3) = 5.1917723873616\\ldots$ and the limits $2-\\zeta(3)$ and $1$ for the adjacent and disjoint correlation ratios. Theorem C closes the picture by showing that if the independence assumption is kept but identical laws are dropped, no universal constant exists: on $K_4$ with two edges of law $x^t$ and four uniform edges, the ratio grows like $4t/45$.","pith_inferences":["The factor-8 proof is modular: pointwise conditional negative correlation plus a second-moment bound on bottleneck distances. The same module should apply to other greedy, order-driven random structures (random greedy matchings, random priority trees), where the bottleneck distance becomes a percolation first-passage time with submultiplicative tail.","Because Proposition D1 rewrites the conjectured large-$n$ decrease of $\\mathbf{E}[L_n]$ as a lower bound on differences of degree second moments, a direct coupling between the coalescent at sizes $n$ and $n+1$ might prove that monotonicity without asymptotic expansions.","The non-identical counterexample uses a max-of-$t$ law on two edges, suggesting that what destroys the universal bound is the loss of exchangeability rather than the shape of the marginal law; an automorphism-invariant family with distinct laws assigned over orbits might still admit a finite constant.","Exhaustive search over small simple graphs and the hub construction together suggest that the true supremum for simple graphs is close to $1.0048$ rather than near $8$; a focus on hub-like or split graphs may be the fastest route to the optimal constant."],"forward_implications":["The true optimal constant in the universal bound lies between $13938405/13872419$ (a three-hub simple graph) and $8$, with the factor improving to $2+o(1)$ when both edge probabilities tend to zero.","For every $n\\geq 3$, the minimum spanning tree measure on $K_n$ is pairwise negatively correlated, so the positive-correlation phenomenon seen on small non-complete graphs never appears in the complete graph.","The identity $\\mathbf{E}[\\deg(x)^2] = 10(n-1)/n - 4\\mathbf{E}[L_n]$ converts any estimate of the expected MST weight into an estimate of the degree second moment; asymptotically it yields $10-4\\zeta(3)$ for the second moment and the limiting pair ratios $2-\\zeta(3)$ and $1$.","The expected MST weight on $K_n$ satisfies explicit all-$n$ bounds $\\mathbf{E}[L_n]\\geq 1 + H_{n-1}/n - 1/n^2$ and $\\mathbf{E}[L_n]\\leq (n-1)(5n+6)/(4n^2)$, supplying an effective finite-range estimate of a quantity previously treated mostly asymptotically.","No universal constant exists for independent but non-identically distributed weights, so the common-law hypothesis is not a technical convenience but a necessary condition for the bound."],"supporting_citations":[{"why":"Gives the monotone-functions covariance bound used to prove the pointwise conditional negative-correlation lemma (Lemma 3.3), the first step of Theorem A.","marker":"[11]"},{"why":"Supplies the original two-bundle example of positively correlated edges, which the paper quantifies in Section 4.2 and improves to a simple-graph witness.","marker":"[15]"},{"why":"Records the universal-factor question and the open adjacent-pair case on $K_n$; Theorems A, B1, and Corollary D3 answer those questions.","marker":"[19]"},{"why":"Establishes the multiplicative coalescent as the component-merger process; its transition probabilities are the key input for the complete-graph argument in Lemma 5.1.","marker":"[2]"},{"why":"Provides the asymptotic expansion of the expected MST weight whose transfer (via [13]) yields the limit $10 - 4\\zeta(3)$ and the $n^{-1}$ rates.","marker":"[6]"},{"why":"Transfers the uniform-weight expansion to exponential weights (equation (18)), the quantitative step behind Corollary D3 and Corollary 6.3.","marker":"[13]"},{"why":"Supplies computed values of $\\mathbf{E}[L_n]$ and the conjectured monotonicity that Proposition D1 re-expresses as a degree-second-moment difference.","marker":"[10]"},{"why":"Defines the wired minimal spanning forest model whose root-degree second moment matches the limit $10 - 4\\zeta(3)$, confirming the complete-graph limit.","marker":"[16]"}],"fun_headline_variants":["8x cap on edge correlations in all random MSTs","Complete graphs show strict negative edge correlation","Random MST edge correlations: universal 8 bound, K_n negative","No uniform constant if edge laws differ, K_4 shows"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the single premise that all edge weights come from one common distribution with no atoms; the paper shows that if independent weights are allowed to have different laws, a $K_4$ example already drives the correlation ratio to infinity, so no constant of the theorem can survive.","fun_headline_variants_meta":{"raw":{"variants":["8x cap on edge correlations in all random MSTs","Complete graphs show strict negative edge correlation","Random MST edge correlations: universal 8 bound, K_n negative","No uniform constant if edge laws differ, K_4 shows"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000175,"raw_usage":{"total_tokens":1387,"prompt_tokens":1151,"completion_tokens":236,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":767,"completion_tokens_details":{"reasoning_tokens":170}},"tokens_in":767,"tokens_out":236,"duration_ms":2461,"temperature":1.0,"reasoning_tokens":170,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:29:17.832020+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an exact dynamic program over edge orders, or sample exhaustively, on finite connected multigraphs with independent uniform edge weights and look for a pair of distinct edges with $\\mathbf{P}(e,f\\in T)>8\\,\\mathbf{P}(e\\in T)\\mathbf{P}(f\\in T)$; the paper's own exhaustive census over all small graphs finds ratios no larger than about $1.0048$, so any ratio above $8$ would refute Theorem A. Alternatively, compute $p_1$ on $K_n$ for large $n$: any $n\\geq 3$ with $p_1\\geq 4/n^2$, or any $n\\geq 4$ with $p_2\\geq 4/n^2$, would refute Theorems B1 and B2.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the monotone-functions covariance bound used to prove the pointwise conditional negative-correlation lemma (Lemma 3.3), the first step of Theorem A."},{"cited_title":"Lyons, Y","cited_arxiv_id":null,"evidence_quote":"Supplies the original two-bundle example of positively correlated edges, which the paper quantifies in Section 4.2 and improves to a simple-graph witness."},{"cited_title":"Aldous.Brownian excursions, critical random graphs and the multiplicative coalescent","cited_arxiv_id":null,"evidence_quote":"Establishes the multiplicative coalescent as the component-merger process; its transition probabilities are the key input for the complete-graph argument in Lemma 5.1."},{"cited_title":"Cooper, A","cited_arxiv_id":null,"evidence_quote":"Provides the asymptotic expansion of the expected MST weight whose transfer (via [13]) yields the limit $10 - 4\\zeta(3)$ and the $n^{-1}$ rates."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Transfers the uniform-weight expansion to exponential weights (equation (18)), the quantitative step behind Corollary D3 and Corollary 6.3."},{"cited_title":"Gamarnik.The expected value of random minimal length spanning tree of a complete graph","cited_arxiv_id":null,"evidence_quote":"Supplies computed values of $\\mathbf{E}[L_n]$ and the conjectured monotonicity that Proposition D1 re-expresses as a degree-second-moment difference."},{"cited_title":"Nachmias and P","cited_arxiv_id":null,"evidence_quote":"Defines the wired minimal spanning forest model whose root-degree second moment matches the limit $10 - 4\\zeta(3)$, confirming the complete-graph limit."}],"review_version":2}