Negative association in uniform forests

Negative association in uniform forests

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple undirected graph. A forest edge set is a subset $F\subseteq E$ for which the spanning graph $(V,F)$ has no undirected cycle. Isolated vertices are allowed. Let $\mathcal F(G)=\{F\subseteq E:(V,F)\text{ is a forest}\}$ and choose $F$ uniformly from this finite nonempty collection. Forests of all sizes, including the empty forest, receive equal probability.

For every pair of distinct edges $e,f\in E$, the conjectured inequality is \[ \mathbb P(e\in F\mid f\in F) \le\mathbb P(e\in F). \] The conditional probability is defined because the singleton forest $\{f\}$ occurs with positive probability. Equivalently, \[ \mathbb P(e,f\in F)\le \mathbb P(e\in F)\mathbb P(f\in F). \] If $N=|\mathcal F(G)|$, and $N_e,N_f,N_{ef}$ count forests containing the indicated edges, the exact counting target is $N\,N_{ef}\le N_eN_f$.

The requirement that $e$ and $f$ be distinct is essential: an event is positively correlated with itself unless its probability is zero or one. Also, this distribution is not the uniform spanning-tree distribution and is not uniform over isomorphism types. The catalogue title uses "negative association", but its displayed target is specifically pairwise negative correlation of edge indicators; it does not additionally demand inequalities for every pair of increasing events depending on disjoint edge sets.

Short English statement

For a uniformly chosen forest edge set, does knowing that one edge is present never increase the probability that a different edge is present?

Research attempt

Scope and process.

GPT-6 Astra Ultra, 2 October 2026. The canonical formulation above is retained. This attempt uses a primary-source literature audit, independent restricted proofs, and adversarial checks. Reproved results are not claimed as new. Numerical tests below are reproducible in scripts/check_attempt_batch03_extremal_2026_10_02.py.

Literature and probability space.

The desired pairwise inequality is explicitly posed by Grimmett--Winkler [S3]. Tang--Zhang [S4] prove results for complete hosts and specified families, including forests with a fixed number of components for sufficiently large order. Such results do not automatically give the present uniform distribution over all forests of an arbitrary host. The calculation below proves the catalogue inequality for every cactus graph, then exposes why a tempting determinant argument concerns a different measure.

Exact proof for cactus graphs.

A cactus is a graph in which distinct simple cycles share at most one vertex. Its edge set splits into bridge edges and cycle blocks. A subset of its edges is a forest exactly when it fails to contain all edges of each cycle block. Indeed, any cycle of the chosen subgraph would be one of the host's cycles. The set of admissible subsets is therefore a Cartesian product: a bridge may be chosen or omitted freely, and a cycle of length $\ell$ admits all its $2^\ell-1$ proper edge subsets. Uniform choice from this product makes the block choices independent.

If distinct $e,f$ lie in a common cycle of length $\ell\ge3$, counting proper subsets gives \[ \Pr[e\in F]=\frac{2^{\ell-1}-1}{2^\ell-1},\qquad \Pr[e,f\in F]=\frac{2^{\ell-2}-1}{2^\ell-1}. \] Subtracting the square of the first expression from the second yields \[ \operatorname{Cov}(1_e,1_f) =-\frac{2^{\ell-2}}{(2^\ell-1)^2}<0. \] When the edges are in different blocks, their indicators are independent and covariance is zero. The same holds for two bridges. These cases exhaust every edge pair, including disconnected cacti and isolated vertices, and prove the desired nonpositive covariance throughout that class.

A precise general counting reformulation.

For any graph, partition its forests into four classes: neither marked edge present ($A$ forests), only $e$ present ($B$), only $f$ present ($C$), and both present ($D$). These letters denote counts, not sets in the following formula. The catalogue inequality becomes \[ (A+B+C+D)D\le(B+D)(C+D), \quad\text{equivalently}\quad AD\le BC. \] Thus an injection from ordered pairs in the first and fourth classes into ordered pairs in the second and third would suffice. Directly moving $e$ from the second forest of such a pair into the first need not preserve acyclicity. For example, take triangle $012$ with an extra pendant edge $23$, let $e=01,f=23$, and use forests $\{02,12\}$ and $\{01,23\}$. Moving $01$ into the first creates the triangle. A valid injection would need additional path exchanges and a recoverable rule; merely switching the marked edge is insufficient.

Why the matrix-forest shortcut changes the question.

The matrix-forest determinant $\det(I+L_G)$ counts rooted forests [S5], weighting an unrooted forest by the product of its component orders. This is not constant across forests. For the three-vertex path, the four unrooted edge subsets are all forests and all have probability $1/4$. Their rooted multiplicities are $1,2,2,3$, with total eight. Under the uniform unrooted measure a fixed path edge has probability $1/2$; under the rooted measure it has probability $(2+3)/8=5/8$. The determinant therefore cannot be substituted for the catalogue's forest count without a separate argument transferring the inequality. The distinction already appears on a graph where both inequalities happen to hold.

Verification and first gap.

The script enumerates forest subsets of several cacti, including two cycles sharing a vertex, and compares all pair covariances with the exact formulas. It checks the failed single-edge exchange and the rooted path multiplicities. These finite checks supplement the product proof; they do not justify treating arbitrary overlapping cycles as independent blocks. The missing general step is an inequality or reversible exchange proving $AD\le BC$ when cycles share edges.

Final status.

Every cactus host is covered, with exact covariance values. The arbitrary-host uniform-forest statement is UNRESOLVED by this attempt.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3309 (OPG-1757), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Negative association in uniform forests. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/negative_association_in_uniform_forests.
• S3 G. R. Grimmett and S. N. Winkler, Negative association in uniform forests and connected graphs $2003$, formulation for distinct edge indicators. https://arxiv.org/abs/math/0302185.
• S4 P. Tang and Z. Zhang, Pairwise Negative Correlation for Uniform Spanning Subgraphs of the Complete Graph, arXiv:2603.10738v1, 11 March 2026. Host and component-count restrictions are essential to interpreting the result. https://arxiv.org/abs/2603.10738.
• S5 P. Chebotarev and E. Shamis, Matrix-Forest Theorems, arXiv:math/0602575 (2006 version of the authors' earlier manuscript). The determinant counts rooted spanning forests. https://arxiv.org/abs/math/0602575.