Counting 1-factors in regular bipartite graphs
From MaRDI portal
Publication:1386423
The author proves that any \(k\)-regular bipartite graph with \(2n\) vertices has at least \(({(k-1)^{k-1}\over{k^ {k-2}}})^n\) 1-factors. This generalizes an earlier result of \textit{M. Voorhoeve} [A lower bound for the permanents of certain \((0,1)\)-matrices, Indag. Math. 41, 83-86 (1979; Zbl 0401.05005)], in which it was shown a cubic bipartite graph has at least \(({4\over 3})^n\) 1-factors. This also establishes that \( {(k-1)^{k-1}}\over{k^{k-2}}\) is the best base possible. That is, if \(\alpha_k\) is the largest real number such that any \(k\)-regular bipartite graph with \(2n\) vertices has at least \(\alpha_k^n\) 1-factors, then \(\alpha_k = {{(k-1)^{k-1}}\over{k^{k-2}}}\).
Recommendations
Cites work
- A lower bound for the permanent of a doubly stochastic matrix
- scientific article; zbMATH DE number 3704754 (Why is no real title available?)
- scientific article; zbMATH DE number 3753004 (Why is no real title available?)
- scientific article; zbMATH DE number 193132 (Why is no real title available?)
- scientific article; zbMATH DE number 3621721 (Why is no real title available?)
- scientific article; zbMATH DE number 3621932 (Why is no real title available?)
- scientific article; zbMATH DE number 3277547 (Why is no real title available?)
- Matching theory
- On the number of edge-colourings of regular bipartite graphs
- Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
Cited in
(45)- Upper bounds on the Witten index for supersymmetric lattice models by discrete Morse theory
- On the validations of the asymptotic matching conjectures
- A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor
- Approximating the permanent via importance sampling with application to the dimer covering problem
- Maximising the permanent and complementary permanent of (0,1)-matrices with constant line sum
- Several constants arising in statistical mechanics
- A lower bound on the maximum permanent in \(\Lambda_{n}^{k}\).
- Problems and results in extremal combinatorics. I.
- The combinatorics of a three-line circulant determinant
- A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix
- A generalization of permanent inequalities and applications in counting and optimization
- A short survey on stable polynomials, orientations and matchings
- Perfect matchings in planar cubic graphs
- An update on Minc's survey of open problems involving permanents
- Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications
- Theory of computation of multidimensional entropy with an application to the monomer-dimer problem
- Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
- On the proportion of transverse-free plane curves
- Matchings in Benjamini-Schramm convergent graph sequences
- Cubic bridgeless graphs have more than a linear number of perfect matchings
- Permanents of multidimensional matrices: properties and applications
- Upper bounds on the numbers of 1-factors and 1-factorizations of hypergraphs
- Statistical Matching Theory
- Lower Bounds for Partial Matchings in Regular Bipartite Graphs and Applications to the Monomer–Dimer Entropy
- scientific article; zbMATH DE number 1156633 (Why is no real title available?)
- Randomly colouring graphs (a combinatorial view)
- A Tight Analysis of Bethe Approximation for Permanent
- Matchings in vertex-transitive bipartite graphs
- On the numbers of 1-factors and 1-factorizations of hypergraphs
- Perfect matchings of regular bipartite graphs
- Exponentially many perfect matchings in cubic graphs
- Counting matchings via capacity-preserving operators
- On the dimer problem of the vertex-edge graph of a cubic graph
- Factorisation of the complete bipartite graph into spanning semiregular factors
- Perfect matching in bipartite hypergraphs subject to a demand graph
- Experimental results on the number of perfect matchings in graphs of Latin rectangle
- A tight analysis of Bethe approximation for permanent
- Partitioning the hypercube into smaller hypercubes
- A common generalization of hypercube partitions and ovoids in polar spaces
- The number of symmetric chain decompositions
- Spanning trees of 3-uniform hypergraphs
- Computation of terms in the asymptotic expansion of dimer \(\lambda_d\) for high dimension
- Graph factors and factorization: 1985--2003: a survey
- Graphs with the maximum or minimum number of 1-factors
- An improved linear bound on the number of perfect matchings in cubic graphs
This page was built for publication: Counting 1-factors in regular bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1386423)
