Negative association in uniform forests

Status partial medium confidence

The conjecture that a uniformly random forest $F$ of a finite graph $G$ satisfies $\mathbb{P}(e \in F \mid f \in F) \le \mathbb{P}(e \in F)$ for any two edges $e, f$ remains open in full generality. Stark (2011) proved it for complete graphs $K_n$ when $n$ is sufficiently large via enumerative methods; Tang and Zhang (2026) extended pairwise negative correlation to families of uniform spanning subgraphs (forests with a fixed number of components, connected subgraphs with given excess) of $K_n$ for large $n$. The general case resists proof because the uniform forest measure is not strongly Rayleigh, so the Borcea–Brändén–Liggett framework that settles the spanning-tree variant does not apply.

Cited literature (3)

• partial The edge correlation of random forests (2011)
  Dudley Stark · Annals of Combinatorics · doi:10.1007/s00026-011-0104-7

  Proves pairwise negative correlation for the uniform random forest on $K_n$ for all sufficiently large $n$ using enumerative methods, confirming the conjecture in this special case.

• partial On Negative Correlation of Arboreal Gas on Some Graphs (2023)
  Xiangyu Huang · arXiv preprint · arXiv:2311.00965

  Establishes negative correlation for the arboreal gas (a $\beta$-weighted random forest model that specialises to the uniform forest at $\beta=1$) on specific graph families, while explicitly noting that the general conjecture remains open.

• partial Pairwise Negative Correlation for Uniform Spanning Subgraphs of the Complete Graph (2026)
  Pengfei Tang, Zibo Zhang · arXiv preprint · arXiv:2603.10738

  Proves pairwise negative correlation for uniform forests with exactly $k$ components and for uniform connected spanning subgraphs with given excess on $K_n$ for all sufficiently large $n$.

Reviewer notes. The Stark (2011) Springer page was inaccessible due to a paywall redirect; the result is confirmed via the Oxford Mathematical Institute seminar record (maths.ox.ac.uk/node/7029) and independent search summaries. The Grimmett–Winkler (RSA 2004) computational verification for small graphs, the Semple–Welsh (CPC 2008) infinite class of special cases, and the Borcea–Brändén–Liggett (JAMS 2009) strongly Rayleigh framework all predate or nearly coincide with the OPG posting and are not listed in since_posted; they are important context. The arboreal gas at $\beta=1$ coincides with the uniform forest measure, so Huang (2023) is directly relevant. Specific graphs in Huang (2023) could not be extracted from the abstract page alone. The problem is confirmed open as of November 2023 by Huang's explicit statement.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 07) (web search enabled).