Determinantal random subgraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911252050083840 |
|---|---|
| author | Kassel, Adrien Lévy, Thierry |
| author_facet | Kassel, Adrien Lévy, Thierry |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_06819 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Determinantal random subgraphs Kassel, Adrien Lévy, Thierry Probability Mathematical Physics Combinatorics 60C05, 05C31, 15A75, 05B35 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. |
| title | Determinantal random subgraphs |
| topic | Probability Mathematical Physics Combinatorics 60C05, 05C31, 15A75, 05B35 |
| url | https://arxiv.org/abs/2212.06819 |