Product approximations for uniform spanning trees and determinantal processes

Abstract

We prove that for every finite connected simple graph G on n vertices with minimum degree k≥ 2, there is a coupling of its uniform spanning tree and its random $1$-out subgraph under which the expected number of differing edges is O(nlog (k)/√k). More generally, we establish analogous couplings between a wide class of determinantal processes and their corresponding $1$-out processes, including Kalai's determinantal hypertrees, with expected symmetric difference negligible compared to the size of the determinantal set. While the graphical case admits a surprisingly short and elegant proof, the more general result requires establishing an asymptotic equipartition property for the determinantal measures in this class, from which we also derive exponential growth rates for the homology torsion of determinantal hyperforests in higher-dimensional regular high-degree complexes.

Determinantal linear spanning forests
Adrien Kassel, Thierry Levy
HAL12 Oct 2026PreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematics ProbabilityHALarXiv
Decay of Correlations for Multiplicative Functionals of Determinantal Point Processes
Alexander I. Bufetov
arXiv1 Nov 2026PreprintCC BY 4.0Full textAnalysis & PDEs Dynamical systemsarXiv
Large deviation principle for determinantal point processes on Stein manifolds
Kiyoon Eum
arXiv13 Oct 2026PreprintCC BY 4.0Full textAnalysis & PDEs ProbabilityarXiv
Reducing the domain of discrete multi-time determinantal point processes
Tom Claeys, Felix Gideonse
arXiv28 Aug 2026PreprintarXiv licenceFull textAnalysis & PDEs Mathematical physicsarXiv
Incremental Column Subset Selection via Conditional Determinantal Point Processes
Laura Grigori, Zhipeng Xue
arXiv17 Sep 2026PreprintCC BY 4.0Full textNumerical analysis & scientific computingarXiv

Cite

BibTeX RIS

BibTeX

@misc{meszaros2026product,
  title = {{Product approximations for uniform spanning trees and determinantal processes}},
  author = {András Mészáros and Yuval Peled},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.11554},
  eprint = {2610.11554},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.11554},
}

RIS

TY  - UNPB
TI  - Product approximations for uniform spanning trees and determinantal processes
AU  - András Mészáros
AU  - Yuval Peled
PY  - 2026
DA  - 2026/10/08
PB  - arXiv
DO  - 10.48550/arxiv.2610.11554
UR  - https://arxiv.org/abs/2610.11554
AB  - We prove that for every finite connected simple graph G on n vertices with minimum degree k≥ 2, there is a coupling of its uniform spanning tree and its random $1$-out subgraph under which the expected number of differing edges is O(nlog (k)/√k). More generally, we establish analogous couplings between a wide class of determinantal processes and their corresponding $1$-out processes, including Kalai's determinantal hypertrees, with expected symmetric difference negligible compared to the size of the determinantal set. While the graphical case admits a surprisingly short and elegant proof, the more general result requires establishing an asymptotic equipartition property for the determinantal measures in this class, from which we also derive exponential growth rates for the homology torsion of determinantal hyperforests in higher-dimensional regular high-degree complexes.
ER  -

Abstract

Related

Cite