2014/07/21 by Péter Csíkvári, Csikvári, Péter · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1407.5409
openalex publication_date 2014/07/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A theorem of A. Schrijver asserts that a d-regular bipartite graph on 2n vertices has at least (\frac(d-1)d-1dd-2)n 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 (\frac(d-1)d-1dd-2+c(k))n perfect matchings. We also show that if (Gi) is a Benjamini--Schramm convergent graph sequence of vertex-transitive bipartite graphs, then (ln pm(Gi))/(v(Gi)) 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 mk(G) denote the number of matchings of size k, and M(G,t)=1+m1(G)t+m2(G)t2+… +mn(G)tn=∏k=1n(1+γk(G)t), where γ1(G)≤ … ≤ γn(G), then γk(G)≥ (d2)/(4(d-1))(k2)/(n2), and \fracmn-1(G)mn(G)≤ (2)/(d)n2. 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.