Stable stars, rank-one replacement and negative edge correlation in random forests

Pick a random spanning forest of a finite graph with probability proportional to the product of its positive edge weights. A conjecture of Kahn and of Grimmett and Winkler, in its weighted form, asserts that any two edges are nonpositively correlated. We prove this for every pair of edges sharing a vertex, on every finite graph and at all positive weights: the generating polynomial of the edges at any vertex is real stable, so every star is strongly Rayleigh and every vertex degree is a sum of independent Bernoulli variables. Two incident edges are strictly negatively correlated exactly when some cycle contains both, with an explicit lower bound. For disjoint edges we develop an exact replacement principle: a weighted background attached through activities of product form s_h r_v can be replaced by finitely many isolated vertices whose weights are the negated reciprocal roots of a real-rooted one-hub polynomial, preserving the joint law of all retained edges. This yields strict negative correlation of two disjoint edges whose four endpoints form a rank-one clique over an arbitrary weighted background, and hence strict negative correlation of every pair of edges of K_n with vertex-factor weights w_ij = t_i t_j, including every common activity. We also prove nonpositive pairwise correlation at all positive weights on every graph with a vertex cover of size at most three, on rank-one attachments whose replacement graph has at most seven vertices, and on graphs assembled by 2-sums from such pieces; these last results use Erickson's finite theorem for graphs on at most seven vertices.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-20
DOI
https://doi.org/10.5281/zenodo.24404884
Primary Topic
Advanced Combinatorial Mathematics
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Stable stars, rank-one replacement and negative edge correlation in random forests

Scott Schubr
8 links
Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
preprint

Stable stars, rank-one replacement and negative edge correlation in random forests

Scott Schubr
preprint en

Abstract

Pick a random spanning forest of a finite graph with probability proportional to the product of its positive edge weights. A conjecture of Kahn and of Grimmett and Winkler, in its weighted form, asserts that any two edges are nonpositively correlated. We prove this for every pair of edges sharing a vertex, on every finite graph and at all positive weights: the generating polynomial of the edges at any vertex is real stable, so every star is strongly Rayleigh and every vertex degree is a sum of independent Bernoulli variables. Two incident edges are strictly negatively correlated exactly when some cycle contains both, with an explicit lower bound. For disjoint edges we develop an exact replacement principle: a weighted background attached through activities of product form s_h r_v can be replaced by finitely many isolated vertices whose weights are the negated reciprocal roots of a real-rooted one-hub polynomial, preserving the joint law of all retained edges. This yields strict negative correlation of two disjoint edges whose four endpoints form a rank-one clique over an arbitrary weighted background, and hence strict negative correlation of every pair of edges of K_n with vertex-factor weights w_ij = t_i t_j, including every common activity. We also prove nonpositive pairwise correlation at all positive weights on every graph with a vertex cover of size at most three, on rank-one attachments whose replacement graph has at most seven vertices, and on graphs assembled by 2-sums from such pieces; these last results use Erickson's finite theorem for graphs on at most seven vertices.

Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon