2018/10/01 by Asaf Ferber, Vishesh Jain · 1 citation
Computer Science · Materials Science · Engineering · Mathematics · #Cooperative Communication and Network Coding #Nanocluster Synthesis and Applications #graph theory and CDMA systems #Combinatorics #Mathematics #Factorization #Upper and lower bounds #Disjoint sets #Discrete mathematics #Exponent #Graph #Lambda #Algorithm
paper · doi:10.1002/rsa.20927
openalex publication_date 2018/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
A 1-factorization of a graph G is a collection of edge-disjoint perfect matchings whose union is E(G). A trivial necessary condition for G to admit a 1-factorization is that |V (G)| is even and G is regular; the converse is easily seen to be false. In this paper, we consider the problem of finding 1-factorizations of regular, pseudorandom graphs. Specifically, we prove that for any ϵ > 0, an (n, d, λ)-graph G (that is, a d-regular graph on n vertices whose second largest eigenvalue in absolute value is at most λ) admits a 1-factorization provided that n is even, C0≤ d ≤ n-1 (where C0= C0(∈) is a constant depending only on ∈), and λ ≤ d1-∈. In particular, since (as is well known) a typical random d-regular graph Gn,dis such a graph, we obtain the existence of a 1-factorization in a typical Gn,dfor all C0≤ 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 off by a factor of 2 in the base of the exponent from the known upper bound. This lower bound is better by a factor of 2nd/2than the previously best known lower bounds, even in the simplest case where G is the complete graph. Our proofs are probabilistic and can be easily turned into polynomial time (randomized) algorithms.