Matchings on trees and the adjacency matrix: A determinantal viewpoint

DOI10.1002/RSA.21167zbMATH Open1522.05384arXiv2011.04012OpenAlexW3106018864MaRDI QIDQ6076733FDOQ6076733

Authors: András Mészáros 

Publication date: 17 October 2023

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

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.

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

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

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)

Cites Work

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

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)