1‐Factorizations of pseudorandom graphs

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₀ ≤ d ≤ n?1 (where C₀=C₀(?) 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₀ ≤ 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.