Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-07T22:28:59.000Z Has data issue: false hasContentIssue false
  • English
  • Français

Orthogonal Latin Rectangles

Published online by Cambridge University Press:  01 July 2008

ROLAND HÄGGKVIST  and
ANDERS JOHANSSON
ROLAND HÄGGKVIST
Affiliation:
Matematiska Institutionen, Umeå Universitet, S-901 87 Umeå, Sweden (e-mail: rolandh@math.umu.se)
ANDERS JOHANSSON
Affiliation:
N-Institutionen, Högskolan i Gävle, S-801 76 Gävle, Sweden (e-mail: ajj@hig.se)
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.

We use a greedy probabilistic method to prove that, for every ε > 0, every m × n Latin rectangle on n symbols has an orthogonal mate, where m = (1 − ε)n. That is, we show the existence of a second Latin rectangle such that no pair of the mn cells receives the same pair of symbols in the two rectangles.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 4 , July 2008 , pp. 519 - 536
Copyright
Copyright © Cambridge University Press 2008

References

[1]Alon, N. and Spencer, J. (1992) The Probabilistic Method, Wiley.Google Scholar
[2]Birkhoff, G. (1946) Three observations on linear algebra. Univ. Nac. Tucumán. Rev. Ser. A 5 147–151.Google Scholar
[3]Brouwer, A. E., de Vries, A. J. and Wieringa, R. M. A (1978) A lower bound for the length of a partial transversal in a Latin square. Nieuw Archief vor Wieskunde (3) XXVI 330–332.Google Scholar
[4]Dénes, J. and Keedwell, A. D., eds (1974) Latin Squares and their Applications, Academic Press, New York.Google Scholar
[5]Drisko, A. A. (1998) Transversals in row-Latin rectangles. J. Combin. Theory Ser. A 84 181–195.CrossRefGoogle Scholar
[6]Hilton, A. J. W. (1994) Problem BCC 13.20. Discrete Math. 125 407–417.Google Scholar
[7]Jensen, T. R. and Toft, B. (1995) Graph Colouring Problems, Wiley, New York.Google Scholar
[8]Kahn, J. (1996) Asymptotically good list-colourings. J. Combin. Theory. Ser. A 73 1–59.CrossRefGoogle Scholar
[9]Koksma, K. K. (1969) A lower bound for the order of a partial transversal in a Latin square. J. Combin. Theory 7 94–95.CrossRefGoogle Scholar
[10]Molloy, M. S. and Reed, B. (2002) Graph Colouring and the Probabilistic Method, Springer.CrossRefGoogle Scholar
[11]Shor, P. W. (1982) A lower bound for the length of a partial transversal in a Latin square. J. Combin. Theory Ser. A 33 1–8.CrossRefGoogle Scholar
[12]Stein, S. K. (1975) Transversals of Latin squares and their generalizations. Pacific J. Math. 59 567–575.CrossRefGoogle Scholar
[13]Woolbright, D. E. (1978) A n × n Latin square has a transversal with at least $n-\sqrt{n}$ distinct symbols. J. Combin. Theory Ser. A 24 235–237.CrossRefGoogle Scholar