Combinatorial Theory

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.

Mathematics Subject Classifications: 60C05, 05C31, 15A75, 05B35

Keywords: Determinantal probability measures, uniform spanning tree, cycle-rooted spanning forest, circular matroid, bicircular matroid, Laplacian determinant, matrix-tree theorem, Symanzik polynomials, Kirchhoff polynomials, graph polynomial, subgraph enumeration, measured matroid