In Graph Theory, a rainbow is any subgraph of an edge-coloured graph whose edges have all of them distinct colours. This paper deals with the problem of finding disjoint rainbow perfect matchings within an \(n\)-edge-coulored complete bipartite graph \(K_{n,n}\). This problem is equivalent to find disjoint transversal within generalized Latin squares. Recall in this regard that a generalized Latin square of order \(n\) is an \(n\times n\) array whose cells are filled with an arbitrary number of symbols such that no symbol appears twice in the same row or column. This is a Latin square when each cell contains precisely one symbol. Further, a transversal is any set of \(n\) cells within a generalized Latin square of order \(n\) that do not share the same row, column or symbol.
The main theorem of the paper indicates that every generalized Latin square with at most \((1-o(1))n\) symbols occurring more than \((1-o(n))\) times, has \((1-o(1))n\) pairwise disjoint transversals. As a corollary, the authors prove that, for all \(\varepsilon>0\) and \(n\) sufficiently large, every generalized Latin square with at least \(\varepsilon n^2\) symbols has \((1-\varepsilon)n\) pairwise disjoint transversals. This last result confirms that every generalized Latin square with at least \(n^2/2\) symbols has a transversal (which was conjectured by S. Akbari and A. Alipour [J. Comb. Des. 12, No. 5, 325–332 (2004; Zbl 1053.05017)]), and asymptotically that, under such a condition, a decomposition into disjoint transversals is always possible (which was conjectured by J. Barát and Z. L. Nagy [Ars Math. Contemp. 16, No. 1, 39–47 (2019; Zbl 1416.05054)]). Another consequence of the main theorem of the paper is that partial transversals of size \(n-o(n)\) must occur almost everywhere within a Latin square. Furthermore, it has also implications in the existence of transversals in certain subsquares of multiplication tables.
Concerning the implications of the main theorem in graph theory, the authors prove a series of results dealing with the decomposition of any properly coloured complete graph into disjoint rainbow Hamiltonian cycles and also into disjoint rainbow spanning trees. In particular, they prove the existence of a positive real number \(\alpha>0\) satisfying that every properly coloured complete graph \(K_n\) has \((1-\varepsilon)n/2\) edge-disjoint spanning rainbow trees, for all \(1>\varepsilon\geq n^{-\alpha}/\alpha\). This result constitutes an asymptotic version of the conjecture of R. A. Brualdi and S. Hollingsworth [J. Comb. Theory, Ser. B 68, No. 2, 310–313 (1996; Zbl 0861.05020)], ensuring that every properly \((2n-1)\)-coloured complete graph \(K_{2n}\) can be decomposed into edge-disjoint rainbow spanning trees, and also of the conjecture of A. Kaneko, M. Kano and K. Suzuki [“Three edge disjoint multicolored spanning trees in complete graphs”, Preprint] indicating that every properly coloured complete graph \(K_n\) contains \(\lfloor n/2\rfloor\) edge-disjoint rainbow spanning trees.