Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-17T02:14:47.653Z Has data issue: false hasContentIssue false
  • English
  • Français

On the number of symbols that forces a transversal

Part of: Graph theory Designs and configurations

Published online by Cambridge University Press:  21 October 2019

Peter Keevash  and
Liana Yepremyan
Peter Keevash*
Affiliation:
Mathematical Institute, University of Oxford, Oxford OX1 3LB, UK
Liana Yepremyan
Affiliation:
Mathematical Institute, University of Oxford, Oxford OX1 3LB, UK
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Akbari and Alipour [1] conjectured that any Latin array of order n with at least n2/2 symbols contains a transversal. For large n, we confirm this conjecture, and moreover, we show that n399/200 symbols suffice.

MSC classification

Primary: 05C70: Factorization, matching, partitioning, covering and packing
Secondary: 05B15: Orthogonal arrays, Latin squares, Room squares
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 2 , March 2020 , pp. 234 - 240
Copyright
© Cambridge University Press 2019

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

Research supported in part by ERC Consolidator Grant 647678.

References

Akbari, S. and Alipour, A. (2004) Transversals and multicolored matchings. J. Combin. Designs 12 325–332.CrossRefGoogle Scholar
Barát, J. and Nagy, Z. L. (2017) Transversals in generalized Latin squares. arXiv:1701.08220Google Scholar
Best, D., Hendrey, K., Wanless, I. M., Wilson, T. E. and Wood, D. (2016) Transversals in Latin arrays with many distinct symbols. arXiv:1612.09443Google Scholar
Bollobás, B. (1998) Modern Graph Theory, Springer.CrossRefGoogle Scholar
Brualdi, R. A. and Ryser, H. J. (1991) Combinatorial Matrix Theory, Cambridge University Press.CrossRefGoogle Scholar
Gyárfás, A. and Sárközy, G. (2012) Rainbow matchings and partial transversals of Latin squares. arXiv:1208.5670Google Scholar
Hatami, P. and Shor, P. W. (2008) A lower bound for the length of a partial transversal in a Latin square. J. Combin. Theory Ser. A 115 1103–1113.CrossRefGoogle Scholar
Kim, J., Kühn, D., Kupavskii, A. and Osthus, D. (2018) Rainbow structures in locally bounded colourings of graphs. arXiv:1805.08424Google Scholar
Montgomery, R., Pokrovskiy, A. and Sudakov, B. (2018) Decompositions into spanning rainbow structures. arXiv:1805.07564Google Scholar
Peng, Y., Rödl, V. and Ruciński, A. (2002) Holes in graphs. Electron. J. Combin. 9 R1.CrossRefGoogle Scholar
Ryser, H. (1967) Neuere Probleme in der Kombinatorik. In Vorträge über Kombinatorik, Mathematischen Forschungsinstitut, Oberwolfach, pp. 69–91.Google Scholar
Stein, S. K. (1975) Transversals of Latin squares and their generalizations. Pacific J. Math . 59 567–575.CrossRefGoogle Scholar