Matchings in vertex-transitive bipartite graphs

DOI10.1007/S11856-016-1375-9zbMATH Open1352.05149OpenAlexW1485502831MaRDI QIDQ502979FDOQ502979

Authors Péter Csikvári 

Publication date 11 January 2017

Published in Israel Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Benjamini-Schramm convergent graph sequenceSchrijver's theorem

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: A theorem of A. Schrijver asserts that a $d$-regular bipartite graph on $2n$ vertices has at least ${\displaystyle }$left(frac{(d-1)^{d-1}}{d^{d-2}} ight)^n${\displaystyle }$ perfect matchings. L. Gurvits gave an extension of Schrijver's theorem for matchings of density $p$. In this paper we give a stronger version of Gurvits's theorem in the case of vertex-transitive bipartite graphs. This stronger version in particular implies that for every positive integer $k$, there exists a positive constant $c(k)$ such that if a $d$-regular vertex-transitive bipartite graph on $2n$ vertices contains a cycle of length at most $k$, then it has at least ${\displaystyle }$left(frac{(d-1)^{d-1}}{d^{d-2}}+c(k) ight)^n${\displaystyle }$ perfect matchings. We also show that if $(G_i)$ is a Benjamini--Schramm convergent graph sequence of vertex-transitive bipartite graphs, then ${\displaystyle }$frac{ln pm(G_i)}{v(G_i)}${\displaystyle }$ is convergent, where $pm(G)$ and $v(G)$ denote the number of perfect matchings and the number of vertices of $G$, respectively. We also show that if $G$ is $d$-regular vertex-transitive bipartite graph on $2n$ vertices and $m_k(G)$ denote the number of matchings of size $k$, and ${\displaystyle }$M(G,t)=1+m_1(G)t+m_2(G)t^2+dots +m_n(G)t^n=prod_{k=1}^n(1+gamma_k(G)t),${\displaystyle }$ where $gamm{a}_1(G)leqdotsleqgamm{a}_n(G)$, then ${\displaystyle }$gamma_k(G)geq frac{d^2}{4(d-1)}frac{k^2}{n^2},${\displaystyle }$ and ${\displaystyle }$frac{m_{n-1}(G)}{m_n(G)}leq frac{2}{d}n^2.${\displaystyle }$ The latter result improves on a previous bound of C. Kenyon, D. Randall and A. Sinclair. There are examples of $d$-regular bipartite graphs for which these statements fail to be true without the condition of vertex-transitivity.

Recommendations

• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
• Matchings in Benjamini-Schramm convergent graph sequences
• Counting matchings in irregular bipartite graphs and random lifts
• Perfect matchings in \(\varepsilon\)-regular graphs
• Results and open problems in matchings in regular graphs

Cites work

• scientific article; zbMATH DE number 428989 (Why is no real title available?)
• scientific article; zbMATH DE number 3704754 (Why is no real title available?)
• scientific article; zbMATH DE number 3621721 (Why is no real title available?)
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• A positivity property of the dimer entropy of graphs
• A variational principle for domino tilings
• Alternating-sign matrices and domino tilings. I
• An asymptotic expansion and recursive inequalities for the monomer-dimer problem
• Approximating the Permanent
• Approximating the number of monomer-dimer coverings of a lattice.
• Computation of terms in the asymptotic expansion of dimer \(\lambda_d\) for high dimension
• Counting 1-factors in regular bipartite graphs
• Dimer problem in statistical mechanics-an exact result
• Dimers and amoebae
• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
• Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy
• Matchings in Benjamini-Schramm convergent graph sequences
• On Leonid Gurvits's proof for permanents
• On the Distribution of the Number of Successes in Independent Trials
• On the number of matchings in regular graphs
• The Holens-Đoković conjecture on permanents fails!
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Theory of monomer-dimer systems
• Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all

Cited in

(10)

• scientific article; zbMATH DE number 1792606 (Why is no real title available?)
• Bipartite matching and Van der Waerden conjecture
• Atoms of the matching measure
• Counting matchings in irregular bipartite graphs and random lifts
• Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms
• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
• Statistical Matching Theory
• Matchings on trees and the adjacency matrix: A determinantal viewpoint
• Matchings in Benjamini-Schramm convergent graph sequences
• Matching preclusion for vertex-transitive networks

This page was built for publication: Matchings in vertex-transitive bipartite graphs

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