1‐Factorizations of pseudorandom graphs. Issue 2 (21st May 2020)

• Record Type: Journal Article
• Authors: Ferber, Asaf; Jain, Vishesh
• Is Part Of: Random structures & algorithms. Volume 57:Issue 2(2020)
• Page Start: 259
• Page End: 278
• Publication Date: 2020-05-21
• Subjects: 1‐factorizations -- pseudorandom graphs -- chromatic index -- edge coloring; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20927
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : A 1‐factorization of a graph G is a collection of edge‐disjoint perfect matchings whose union is E ( G ). In this paper, we prove that for any ϵ >0, an ( n, d, λ )‐graph G admits a 1‐factorization provided that n is even, C 0 ≤ d ≤ n −1 (where C 0 = C 0 ( ϵ ) is a constant depending only on ϵ ), and λ ≤ d 1− ϵ . In particular, since (as is well known) a typical random d ‐regular graph G n, d is such a graph, we obtain the existence of a 1‐factorization in a typical G n, d for all C 0 ≤ d ≤ n −1, thereby extending to all possible values of d results obtained by Janson, and independently by Molloy, Robalewska, Robinson, and Wormald for fixed d . Moreover, we also obtain a lower bound for the number of distinct 1‐factorizations of such graphs G, which is better by a factor of 2 nd /2 than the previously best known lower bounds, even in the simplest case where G is the complete graph.