Transversals in generalized Latin squares - Barát, János (Ars mathematica contemporanea, 2019)
We are seeking a sufficient condition that forces a transversal in a generalized Latin square. A generalized Latin square of order ?$n$? is equivalent to a proper edge-coloring of ?$K_{n, n}$?. A transversal corresponds to a multicolored perfect matching. S. Akbari and A. Alipour J. Comb. Des. 12, No. 5, 325-332 (2004) defined ?$l(n)$? as the least integer such that every properly edge-colored ?$K_{n, n}$?, which contains at least ?$l(n)$? different colors, admits a multicolored perfect matching. They conjectured that ?$l(n) ≤ n^2/2\ if\ n$? is large enough. In this note we prove that ?$l(n)$? is bounded from above by ?$0.75n^2\ if\ n > 1$?. We point out a connection to anti-Ramsey problems. We propose a conjecture related to a well-known result by D. E. Woolbright and H.-L. Fu J. Comb. Des. 6, No. 1, 1-20 (1998), that every proper edge-coloring of ?$K_{2n}$? admits a multicolored 1-factor.
Keywords: anti-Ramsey problems; anti-Ramseyjevi problemi; Latin squares; latinski kvadrati; Lovász local lemma; Lovászeva lokalna lema; transversals; transverzale