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
- Scott Schubr (ORCID: https://orcid.org/0009-0009-7357-4439)
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