Number of 1-Factorizations of Regular High-Degree Graphs

摘要

A 1-factor in ann-vertex graphGis a collection ofdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$rac{n}{2}$$end{document}vertex-disjoint edges and a 1-factorization ofGis a partition of its edges into edge-disjoint 1-factors. Clearly, a 1-factorization ofGcannot exist unlessnis even andGis 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, Kuhn, Lo, Osthus and Treglown to prove an old conjecture of Dirac from the 1950s, which says that everyd-regular graph onnvertices contains a 1-factorization, provided thatnis even anddocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$d geqslant 2left[ {rac{n}{4}} ight] - 1$$end{document}. In this paper we address the natural question of estimatingF(n,d), the number of 1-factorizations ind-regular graphs on an even number of vertices, provided thatdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$d geqslant left[ {rac{n}{2}} ight] + arepsilon n$$end{document}. Improving upon a recent result of Ferber and Jain, which itself improved upon a result of Cameron from the 1970s, we show thatdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$Fleft( {n,,d} ight) geqslant {left( {left( {1 + oleft( 1 ight)} ight)rac{d}{{{e<^>2}}}} ight)<^>{nd/2}}$$end{document}, which is asymptotically best possible.