论文标题
树上的匹配和邻接矩阵：确定性观点
Matchings on trees and the adjacency matrix: A determinantal viewpoint
论文作者
论文摘要
令$ g $为有限的树。对于任何匹配的$ m $ $ g $，让$ u（m）$是$ m $所发现的一组顶点。令$ \ Mathcal {M} _g $为$ g $的均匀随机最大尺寸匹配。在本文中，我们分析了$ u（\ Mathcal {M} _G）$的结构。我们首先表明$ u（\ Mathcal {M} _G）$是确定过程。我们还表明，对于$ g $的大多数顶点，该顶点的一个小社区中的过程$ u（\ Mathcal {m} _g）$可以根据同一顶点的较大社区的较大社区来很好地近似。然后，我们证明，使用$ g $的本地结构也可以很好地近似$ u（\ Mathcal {M} _G）$的归一化香农熵。换句话说，在树木领域，$ u（\ Mathcal {M} _G）$的标准化香农熵 - 也就是说，$ G $的最大尺寸匹配数的归一化对数 - 是Benjamini-Schramm连续参数。 我们表明，通过在$ u（\ Mathcal {m} _g）$和$ g $的邻接矩阵之间建立新连接，$ u（\ Mathcal {M} _G）$是确定过程。该结果揭示了一个新的灯光，表明在树上，最大尺寸匹配所发现的顶点数量等于邻接矩阵的无效。 某些证明是基于引入新的扰动参数的良好方法，我们称之为温度，然后定义$ \ MATHCAL {M} _G $的正温度类似物，即所谓的单体二聚体模型，并让温度变为零。
Let $G$ be a finite tree. For any matching $M$ of $G$, let $U(M)$ be the set of vertices uncovered by $M$. Let $\mathcal{M}_G$ be a uniform random maximum size matching of $G$. In this paper, we analyze the structure of $U(\mathcal{M}_G)$. We first show that $U(\mathcal{M}_G)$ is a determinantal process. We also show that for most vertices of $G$, the process $U(\mathcal{M}_G)$ in a small neighborhood of that vertex can be well approximated based on a somewhat larger neighborhood of the same vertex. Then we show that the normalized Shannon entropy of $U(\mathcal{M}_G)$ can be also well approximated using the local structure of $G$. In other words, in the realm of trees, the normalized Shannon entropy of $U(\mathcal{M}_G)$ -- that is, the normalized logarithm of the number of maximum size matchings of $G$ -- is a Benjamini-Schramm continuous parameter. We show that $U(\mathcal{M}_G)$ is a determinantal process through establishing a new connection between $U(\mathcal{M}_G)$ and the adjacency matrix of $G$. This result sheds a new light on the well-known fact that on a tree, the number of vertices uncovered by a maximum size matching is equal to the nullity of the adjacency matrix. Some of the proofs are based on the well established method of introducing a new perturbative parameter, which we call temperature, and then define the positive temperature analogue of $\mathcal{M}_G$, the so called monomer-dimer model, and let the temperature go to zero.
