论文标题
确定性随机子图
Determinantal random subgraphs
论文作者
论文摘要
我们定义了有限连接图的确定性随机跨度子图的两个家族，一个由固定数量的连接组件支撑，由无环跨度子图（跨越森林）支撑，另一个由连接的跨越子绘图，带有固定数量的独立循环。每个家庭都将统一的跨性树概括，这些概率的生成函数概括了经典的Kirchhoff和Symanzik多项式。 我们称跨越森林的Symanzik为跨越子图系的元素，并挑出这些元素的特定决定性混合物，作为核心为$ 1 $ forms，我们称之为laplacian span spanning Forest。 我们的证明依赖于一组积分，真实或复杂的（我们称之为几何）多线性识别，这些识别涉及图表上的周期，串联和森林。我们使用图形代数拓扑的经典片段和应用于有限确定点过程的外部演算证明了这些身份，这两种过程都以独立的方式对待。 我们强调了我们的结构的矩形性质，从而表明了上述两个随机子图的家族如何彼此双重以及可能的概括。
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.
