Matchings on trees and the adjacency matrix: A determinantal viewpoint

DOI10.1002/RSA.21167MaRDI QIDQ6076733zbMATH OpenOpenAlexFDO

Authors András Mészáros

Publication date 17 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2011.04012

zbMATH Keywords

local weak convergencedeterminantal measure

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Measures of information, entropy (94A17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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.

Recommendations

• On the Laplacian coefficients of trees with a perfect matching
• On the number of F-matchings in a tree
• On the \(k\)th eigenvalues of trees and perfect matchings
• On the number of matchings of a tree
• On the number of \(r\)-matchings in a tree
• Generalized matchings in trees
• On the \(k\)th Laplacian eigenvalues of trees with perfect matchings
• Matching complexes of trees and applications of the matching tree algorithm
• Inert matrices and matchings in partially oriented trees
• Matchings and \(\Delta\)-matroids

Cites work

• Alternating-sign matrices and domino tilings. I
• Asymptotic Enumeration of Spanning Trees
• Borel oracles. An analytical approach to constant-time algorithms
• Conformal invariance of domino tiling.
• Counting matchings in irregular bipartite graphs and random lifts
• Determinantal probability measures
• Dimer problem in statistical mechanics-an exact result
• Dominos and the Gaussian free field.
• Gibbs measures and phase transitions on sparse random graphs
• Limiting entropy of determinantal processes
• Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances
• Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy
• Matchings and walks in graphs
• Matchings in Benjamini-Schramm convergent graph sequences
• Matchings in vertex-transitive bipartite graphs
• Matchings on infinite graphs
• Processes on unimodular random networks
• Recurrence of distributional limits of finite planar graphs
• The rank of diluted random graphs
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice

This page was built for publication: Matchings on trees and the adjacency matrix: A determinantal viewpoint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6076733)