Transversals in generalized Latin squares

Authors

  • János Barát University of Pannonia, Hungary and MTA–ELTE Geometric and Algebraic Combinatorics Research Group, Hungary
  • Zoltán Lóránt Nagy MTA–ELTE Geometric and Algebraic Combinatorics Research Group, Hungary and Eötvös Loránd University, Hungary

DOI:

https://doi.org/10.26493/1855-3974.1316.2d2

Keywords:

Latin squares, transversals, anti-Ramsey problems, Lovász local lemma

Abstract

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 Kn, n. A transversal corresponds to a multicolored perfect matching. Akbari and Alipour defined l(n) as the least integer such that every properly edge-colored Kn, n, which contains at least l(n) different colors, admits a multicolored perfect matching. They conjectured that l(n) ≤ n2/2 if n is large enough. In this note we prove that l(n) is bounded from above by 0.75n2 if n > 1. We point out a connection to anti-Ramsey problems. We propose a conjecture related to a well-known result by Woolbright and Fu, that every proper edge-coloring of K2n admits a multicolored 1-factor.

Published

2018-09-09

Issue

Section

Articles