Matchings on trees and the adjacency matrix: A determinantal viewpoint

Mészáros, András (2023) Matchings on trees and the adjacency matrix: A determinantal viewpoint. RANDOM STRUCTURES & ALGORITHMS, 63 (3). pp. 753-778. ISSN 1042-9832

Preview

Text RandomStructAlgorithms-2023-Meszaros-MatchingsontreesandtheadjacencymatrixAdeterminantalviewpoint.pdf - Published Version Available under License Creative Commons Attribution. Download (1MB) | Preview

Abstract

Let (Figure presented.) be a finite tree. For any matching (Figure presented.) of (Figure presented.), let (Figure presented.) be the set of vertices uncovered by (Figure presented.). Let (Figure presented.) be a uniform random maximum size matching of (Figure presented.). In this paper, we analyze the structure of (Figure presented.). We first show that (Figure presented.) is a determinantal process. We also show that for most vertices of (Figure presented.), the process (Figure presented.) 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 (Figure presented.) can be also well approximated using the local structure of (Figure presented.). In other words, in the realm of trees, the normalized Shannon entropy of (Figure presented.) —that is, the normalized logarithm of the number of maximum size matchings of (Figure presented.) —is a Benjamini-Schramm continuous parameter.

Actions (login required)

Edit Item