Uniform versus torsion-squared higher spanning trees

Definitions and mathematical statement

Let $\Delta$ be a finite simplicial complex of dimension $d\geq1$, supplied by an explicit list of its faces. Choose arbitrary orientations of its $d$- and $(d-1)$-faces, and let $\partial_d$ be the associated integer boundary matrix. A $d$-dimensional spanning tree, in the homological sense used here, is a subcomplex $T$ containing the entire $(d-1)$-skeleton of $\Delta$ whose selected $d$-face columns form a basis for the column space of $\partial_d$ over $\mathbb Q$. In particular, the selected columns are linearly independent and have the same rank as the full matrix. Changing orientations does not affect this definition.

Equivalently, $H_d(T;\mathbb Q)=0$ and the inclusion preserves the dimension of $H_{d-1}(\Delta;\mathbb Q)$. When that latter homology vanishes, $T$ has vanishing rational homology in both relevant degrees; integral torsion in the lower degree is still allowed. For connected graphs this recovers ordinary spanning trees.

Is there an exact randomized algorithm that, for every such explicitly given complex, outputs each spanning tree with the same probability, with expected running time polynomial in the input length? Random bits and bit operations count toward running time, and termination is required with probability one. The distribution sought is uniform on distinct sets of top-dimensional faces. Sampling with probabilities proportional to squared torsion orders, or merely approximating the uniform distribution, is a different task and does not by itself answer the stated question.

Short English statement

Find an efficient exact uniform sampler for higher-dimensional spanning trees, including complexes whose trees have different integral torsion.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20000991 (AIM-COMBINATORICS-0116), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, Generalizations of chip-firing and the critical group, item 26. Original workshop question underlying AIM-COMBINATORICS-0116. https://aimath.org/pastworkshops/chipfiringproblems.pdf.