Determinantal random subgraphs
Abstract
We define two families of determinantal random spanning subgraphs of a finite connected graph, one supported by acyclic spanning subgraphs (spanning forests) with fixed number of connected components, the other by connected spanning subgraphs with fixed number of independent cycles. Each family generalizes the uniform spanning tree and the generating functions of these probability measures generalize the classical Kirchhoff and Symanzik polynomials. We call Symanzik spanning forests the elements of the acyclic spanning subgraphs family, and single out a particular determinantal mixture of these, having as kernel a normalized Laplacian on $1$-forms, which we call the Laplacian spanning forest. Our proofs rely on a set of integral and real or complex (which we call geometric) multilinear identies involving cycles, coboundaries, and forests on graphs. We prove these identities using classical pieces of the algebraic topology of graphs and the exterior calculus applied to finite determinantal point processes, both of which we treat in a self-contained way. We emphasize the matroidal nature of our constructions, thereby showing how the above two families of random spanning subgraphs are dual to one another, as well as possible generalisations.
Related
- Large induced subgraphs with k vertices of maximum degree
- Decomposing multigraphs into two Class I subgraphs with prescribed maximum degrees
- A proof of Vince's conjecture on the average order of connected induced subgraphs
- A Note on Vertex-Critical Induced Subgraphs of Shift Graphs
- On the solution to the Erdős-Hajnal problem on high-girth high-chromatic subgraphs
BibTeX
@article{kassel2026determinantal,
title = {{Determinantal random subgraphs}},
author = {Adrien Kassel and Thierry Lévy},
journal = {Combinatorial Theory},
year = {2026},
month = aug,
doi = {10.5070/c6.68667},
eprint = {2212.06819},
archivePrefix = {arXiv},
url = {https://hal.science/hal-03899489v5},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Determinantal random subgraphs
AU - Adrien Kassel
AU - Thierry Lévy
PY - 2026
DA - 2026/08/20
JO - Combinatorial Theory
DO - 10.5070/c6.68667
UR - https://hal.science/hal-03899489v5
AB - We define two families of determinantal random spanning subgraphs of a finite connected graph, one supported by acyclic spanning subgraphs (spanning forests) with fixed number of connected components, the other by connected spanning subgraphs with fixed number of independent cycles. Each family generalizes the uniform spanning tree and the generating functions of these probability measures generalize the classical Kirchhoff and Symanzik polynomials. We call Symanzik spanning forests the elements of the acyclic spanning subgraphs family, and single out a particular determinantal mixture of these, having as kernel a normalized Laplacian on $1$-forms, which we call the Laplacian spanning forest. Our proofs rely on a set of integral and real or complex (which we call geometric) multilinear identies involving cycles, coboundaries, and forests on graphs. We prove these identities using classical pieces of the algebraic topology of graphs and the exterior calculus applied to finite determinantal point processes, both of which we treat in a self-contained way. We emphasize the matroidal nature of our constructions, thereby showing how the above two families of random spanning subgraphs are dual to one another, as well as possible generalisations.
SN - 2766-1334
ER -