Matchings in vertex-transitive bipartite graphs

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

Authors: Péter Csikvári 

Publication date: 11 January 2017

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

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.

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

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

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)

Cites Work

• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all
• Alternating-sign matrices and domino tilings. I
• Approximating the number of monomer-dimer coverings of a lattice.
• Theory of monomer-dimer systems
• 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
• Dimers and amoebae
• A variational principle for domino tilings
• Title not available (Why is that?)
• Approximating the Permanent
• Counting 1-factors in regular bipartite graphs
• On the number of matchings in regular graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Leonid Gurvits's proof for permanents
• The Holens-Đoković conjecture on permanents fails!
• A positivity property of the dimer entropy of graphs
• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
• Matchings in Benjamini-Schramm convergent graph sequences
• An asymptotic expansion and recursive inequalities for the monomer-dimer problem
• On the Distribution of the Number of Successes in Independent Trials
• Computation of terms in the asymptotic expansion of dimer \(\lambda_d\) for high dimension
• Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy

Cited In (7)

• Matching preclusion for vertex-transitive networks
• Atoms of the matching measure
• Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms
• Matchings on trees and the adjacency matrix: A determinantal viewpoint
• Statistical Matching Theory
• Bipartite matching and Van der Waerden conjecture
• Title not available (Why is that?)

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)