Hostname: page-component-7b7567c8c-kwt9d Total loading time: 0 Render date: 2026-11-14T09:05:04.268Z Has data issue: false hasContentIssue false
  • English
  • Français

On the number of symbols that forces a transversal

Part of:Graph theoryDesigns 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: keevash@maths.ox.ac.uk
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 2 , March 2020, pp. 234 - 240
Copyright
© Cambridge University Press 2019

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