A quantitative approach to perfect one-factorizations of complete bipartite graphs (Q2341065)

Summary: Given a one-factorization \(\mathcal{F}\) of the complete bipartite graph \(K_{n,n}\), let \(\mathsf {pf}(\mathcal{F})\) denote the number of Hamiltonian cycles obtained by taking pairwise unions of perfect matchings in \(\mathcal{F}\). Let \(\mathsf {pf}(n)\) be the maximum of \(\mathsf {pf}(\mathcal{F})\) over all one-factorizations \(\mathcal{F}\) of \(K_{n,n}\).~In this work we prove that \(\mathsf {pf}(n)\geqslant n^2/4\), for all \(n\geqslant 2\).