Number of 1-Factorizations of Regular High-Degree Graphs
METADATA ONLY
Loading...
Author / Producer
Date
2020-06
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
A 1-factor in an n-vertex graph G is a collection of n/2 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ühn, 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 (Formula presented.). 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 (Formula presented.). Improving upon a recent result of Ferber and Jain, which itself improved upon a result of Cameron from the 1970s, we show that (Formula presented.), which is asymptotically best possible. © 2020 János Bolyai Mathematical Society and Springer-Verlag.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
40 (3)
Pages / Article No.
315 - 344
Publisher
Springer
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
Notes
Funding
175573 - Extremal problems in combinatorics (SNF)