Number of 1-factorizations of regular high-degree graphs

DOI10.1007/S00493-019-3970-YzbMATH Open1474.05320arXiv1803.10360OpenAlexW3009357296WikidataQ114229223 ScholiaQ114229223MaRDI QIDQ2220965FDOQ2220965

Authors: Asaf Ferber, Vishesh Jain, Benny Sudakov 

Publication date: 25 January 2021

Published in: Combinatorica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• A theorem on flows in networks
• On a packing and covering problem
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• An upper bound on the number of Steiner triple systems
• Combinatorial Properties of Matrices of Zeros and Ones
• Title not available (Why is that?)
• Title not available (Why is that?)
• The maximum number of perfect matchings in graphs with a given degree sequence
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• Title not available (Why is that?)
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• Counting and packing Hamilton \(\ell\)-cycles in dense hypergraphs
• One-factorizations of the complete graph—A survey
• Title not available (Why is that?)
• Edge coloring regular graphs of high degree
• Near-optimal, distributed edge colouring via the nibble method
• The number of Hamiltonian decompositions of regular graphs
• Counting Hamilton decompositions of oriented graphs
• 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
• Title not available (Why is that?)
• 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)