Number of 1-factorizations of regular high-degree graphs

DOI10.1007/S00493-019-3970-YMaRDI QIDQ2220965zbMATH OpenOpenAlexWikidataFDO

Authors Asaf Ferber, Vishesh Jain, Benny Sudakov

Publication date 25 January 2021

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

regular graphs1-factorizationshigh-degree graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: A $1$-factor in an $n$-vertex graph $G$ is a collection of $fracn2$ vertex-disjoint edges and a $1$-factorization of $G$ is a partition of its edges into edge-disjoint $1$-factors. Clearly, a $1$-factorization of $G$ cannot exist unless $n$ is even and $G$ is regular (that is, all vertices are of the same degree). The problem of finding $1$-factorizations in graphs goes back to a paper of Kirkman in 1847 and has been extensively studied since then. Deciding whether a graph has a $1$-factorization is usually a very difficult question. For example, it took more than 60 years and an impressive tour de force of Csaba, K"uhn, Lo, Osthus and Treglown to prove an old conjecture of Dirac from the 1950s, which says that every $d$-regular graph on $n$ vertices contains a $1$-factorization, provided that $n$ is even and $dgeq2lceilfracn4ceil-1$. In this paper we address the natural question of estimating $F(n,d)$, the number of $1$-factorizations in $d$-regular graphs on an even number of vertices, provided that $dgeqfracn2+varepsilonn$. Improving upon a recent result of Ferber and Jain, which itself improved upon a result of Cameron from the 1970s, we show that $F(n,d)geqleft((1+o(1))fracd{e}^{2}ight{)}^{nd/2}$, which is asymptotically best possible.

Recommendations

• 1-factorizing regular graphs of high degree - an improved bound
• 1‐Factorizations of pseudorandom graphs
• Factorizations of regular graphs of high degree
• Regular Graphs of High Degree are 1-Factorizable
• On the number of 1-factorizations of a complete graph

Cites work

• scientific article; zbMATH DE number 124525 (Why is no real title available?)
• scientific article; zbMATH DE number 3458807 (Why is no real title available?)
• scientific article; zbMATH DE number 3520420 (Why is no real title available?)
• scientific article; zbMATH DE number 3801730 (Why is no real title available?)
• A theorem on flows in networks
• An upper bound on the number of Steiner triple systems
• Combinatorial Properties of Matrices of Zeros and Ones
• Counting Hamilton decompositions of oriented graphs
• Counting and packing Hamilton \(\ell\)-cycles in dense hypergraphs
• Edge coloring regular graphs of high degree
• Near-optimal, distributed edge colouring via the nibble method
• On a packing and covering problem
• One-factorizations of the complete graph—A survey
• Probability Inequalities for Sums of Bounded Random Variables
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• The maximum number of perfect matchings in graphs with a given degree sequence
• The number of Hamiltonian decompositions of regular graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Two-Sided, Unbiased Version of Hall’s Marriage Theorem

Cited in

(7)

• Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor
• scientific article; zbMATH DE number 1990720 (Why is no real title available?)
• All regular multigraphs of even order and high degree are 1-factorable
• 1-factorizing regular graphs of high degree - an improved bound
• Graph and hypergraph colouring via nibble methods: a survey
• Almost all optimally coloured complete graphs contain a rainbow Hamilton path
• Regular Graphs of High Degree are 1-Factorizable

This page was built for publication: Number of 1-factorizations of regular high-degree graphs

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