On the spectrum of $r$-orthogonal Latin squares of different orders

Document Type : Research Paper


1 Alzahra University

2 Max Planck Institute for Intelligent Systems

3 Sharif University of Technology


‎Two Latin squares of order $n$ are orthogonal if in their superposition‎, ‎each of the $n^{2}$ ordered pairs of symbols occurs exactly once‎. ‎Colbourn‎, ‎Zhang and Zhu‎, ‎in a series of papers‎, ‎determined the integers $r$ for which there exist a pair of Latin squares of order $n$ having exactly $r$ different ordered pairs in their superposition‎. ‎Dukes and Howell defined the same problem for Latin squares of different orders $n$ and $n+k$‎. ‎They obtained a non-trivial lower bound for $r$ and solved the problem for $k \geq \frac{2n}{3} $‎. ‎Here for $k < \frac{2n}{3}$‎, ‎some constructions are shown to realize many values of $r$ and for small cases $(3\leq n \leq 6)$‎, ‎the problem has been solved‎.


Main Subjects

[1] G. B. Belyavskaya, $r$-Orthogonal quasigroups I, Math. Issled., 39 (1976) 32–39.

[2] G. B. Belyavskaya, $r$-Orthogonal quasigroups II, Math. Issled., 43 (1976) 39–49.

[3] G. B. Belyavskaya, $r$-Orthogonal Latin squares, in: J. Dénes and A. D. Keedwell (Editors), Latin Squares: New Developments, Elsevier, North-Holland, Amsterdam, 1992.

[4] C. J. Colbourn and L. Zhu, The spectrum of r-orthogonal Latin squares, C. J. Colbourn, E. S. Mahmoodian (Editors), Combinatorics advances (Tehran, 1994), Kluwer Academic Press, Dordrecht, 1995 49–75.

[5] P. Dukes and J. Howell, The orthogonality spectrum for Latin squares of different orders, Graphs Combin., 29 (2013) 71–78.

[6] J. Howell, The intersection problem and different pairs problem for Latin squares, Ph. D. dissertation, University of Victoria, 2010.

[7] H. J. Ryser, A combinatorial theorem with an application to Latin rectangles, Proc. Amer. Math. Soc., 2 (1951) 550–552.

[8] L. Zhu and H. Zhang, A few more $r$-orthogonal Latin squares, Discrete Math., 238 (2001) 183–191.

[9] L. Zhu and H. Zhang, Completing the spectrum of $r$-orthogonal Latin squares, Discrete Math., 268 (2003) 343–349.
  • Receive Date: 27 April 2015
  • Revise Date: 10 November 2015
  • Accept Date: 12 November 2015
  • Published Online: 01 June 2016