Released by
Kun Chen, Institute of Theoretical Physics, Chinese Academy of Sciences
Contact email
chenkun0228@gmail.com
Method
Other
Challenge issue
Background
Let $G=(V,E)$ be a finite undirected graph. Give every labelled edge $h$ a strictly positive exact weight $\beta_h$. The arboreal-gas measure samples every acyclic edge set, or forest, with probability
$$w_{\boldsymbol\beta}(F)=\prod_{h\in F}\beta_h,\qquad
Z=\sum_{\substack{F\subseteq E\\F\text{ forest}}}w_{\boldsymbol\beta}(F),
\qquad
\mathbb{P}_{\boldsymbol\beta}(F)=\frac{w_{\boldsymbol\beta}(F)}{Z}.$$
The empty forest is included with weight one. Setting all weights to one gives the uniform forest model.
For distinct edges $e,f$, define
$$Z_e=\sum_{F\ni e}w(F),\qquad
Z_f=\sum_{F\ni f}w(F),\qquad
Z_{ef}=\sum_{F\supseteq\{e,f\}}w(F).$$
Pairwise edge negative correlation is
$$\mathbb{P}[e,f]\le \mathbb{P}[e]\mathbb{P}[f],$$
equivalently $Z_{ef}Z\le Z_eZ_f$. Despite the intuition that the acyclicity constraint makes edges compete, this universal claim is still open even for the uniform forest model on arbitrary finite graphs.
Research objective
Find one explicit finite graph, a strictly positive exact weight for every edge, and two distinct designated edges $e,f$ such that
$$Z_{ef}Z>Z_eZ_f.$$
The target is the full forest measure, mixing every component count. A fixed-component forest measure, spanning-tree measure, connected-subgraph measure, bunkbed inequality, or factor-two approximate correlation result does not answer this challenge. Loops are excluded; if parallel labelled edges are used, a parallel pair is a two-edge cycle.
Success and verification gate
A complete submission contains:
- the complete finite graph, including all labelled edges;
- exact strictly positive weights, preferably rational;
- two distinct designated edges $e,f$; and
- the exact values of $Z$, $Z_e$, $Z_f$, and $Z_{ef}$ proving the strict reversed inequality.
The independent verifier is straightforward:
read the graph, exact weights, e, and f
reject malformed graphs, nonpositive weights, or invalid designated edges
for every edge subset:
retain it iff union-find reports no cycle
accumulate Z, Ze, Zf, and Zef using exact rational arithmetic
accept iff Zef * Z > Ze * Zf
The worst-case cost is exponential in the number of edges, but a witness with roughly twenty edges is normally checked in seconds. The solver's search history and derivation are irrelevant: the finite weighted graph is the result.
Why this may lead to research output
This is a longstanding foundational negative-dependence problem for random forests. The all-positive-weights formulation is related to monotonicity in every edge weight and to generalized product inequalities; negative correlation is also used in studying infinite-volume arboreal-gas measures. A single counterexample would refute the universal pairwise claim and unrestricted negative association for the same measure, while identifying a boundary that future monotonicity and infinite-volume arguments must respect.
Current status and references
The problem was audited on 28 July 2026 and assessed as confirmed open with high confidence. Later work proves restricted graph, activity, and edge-configuration cases, but a March 2026 paper still states even the uniform-weight arbitrary-graph subcase as a conjecture.
- R. Bauerschmidt et al., Random Spanning Forests and Hyperbolic Symmetry.
- X. Huang, On Negative Correlation of Arboreal Gas on Some Graphs.
- A. Ayyer, S. Linusson, and A. Ravichandran, The bunkbed problem and the random cluster model.
- Pairwise Negative Correlation for Uniform Spanning Subgraphs of the Complete Graph.
Released by
Kun Chen, Institute of Theoretical Physics, Chinese Academy of Sciences
Contact email
chenkun0228@gmail.com
Method
Other
Challenge issue
Background
Let$G=(V,E)$ be a finite undirected graph. Give every labelled edge $h$ a strictly positive exact weight $\beta_h$ . The arboreal-gas measure samples every acyclic edge set, or forest, with probability
The empty forest is included with weight one. Setting all weights to one gives the uniform forest model.
For distinct edges$e,f$ , define
Pairwise edge negative correlation is
equivalently$Z_{ef}Z\le Z_eZ_f$ . Despite the intuition that the acyclicity constraint makes edges compete, this universal claim is still open even for the uniform forest model on arbitrary finite graphs.
Research objective
Find one explicit finite graph, a strictly positive exact weight for every edge, and two distinct designated edges$e,f$ such that
The target is the full forest measure, mixing every component count. A fixed-component forest measure, spanning-tree measure, connected-subgraph measure, bunkbed inequality, or factor-two approximate correlation result does not answer this challenge. Loops are excluded; if parallel labelled edges are used, a parallel pair is a two-edge cycle.
Success and verification gate
A complete submission contains:
The independent verifier is straightforward:
The worst-case cost is exponential in the number of edges, but a witness with roughly twenty edges is normally checked in seconds. The solver's search history and derivation are irrelevant: the finite weighted graph is the result.
Why this may lead to research output
This is a longstanding foundational negative-dependence problem for random forests. The all-positive-weights formulation is related to monotonicity in every edge weight and to generalized product inequalities; negative correlation is also used in studying infinite-volume arboreal-gas measures. A single counterexample would refute the universal pairwise claim and unrestricted negative association for the same measure, while identifying a boundary that future monotonicity and infinite-volume arguments must respect.
Current status and references
The problem was audited on 28 July 2026 and assessed as confirmed open with high confidence. Later work proves restricted graph, activity, and edge-configuration cases, but a March 2026 paper still states even the uniform-weight arbitrary-graph subcase as a conjecture.