×

Most Latin squares have many subsquares. (English) Zbl 0948.05014

This (in my opinion excellent and important) paper contains a wealth of results on subsquares of Latin squares. The attention is focused on subsquares of order 2 (intercalates). The methods and results are too technical to be reproduced here but some of the more easily stated corollaries include: (1) For arbitrary \(\varepsilon> 0\), with probability approaching \(1\) as \(n\to\infty\), a random Latin squares of order \(n\) contains at least \(n^{(3/2-\varepsilon)}\) intercalates. (2) For arbitrary \(\varepsilon> 0\), the probability of a random Latin square of order \(n\) not containing any intercalates is \(O(\exp(-n^{(2-\varepsilon)})\) as \(n\to\infty\).
The results of computer enumeration for small order Latin square as well as a brief consideration of larger order subsquares are also included. As the authors suggest, a possible subtitle could be “…however, almost all of those subsquares are of order 2”.

MSC:

05B15 Orthogonal arrays, Latin squares, Room squares
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Denniston, R. H.F., Remarks on Latin squares with no subsquares of order two, Utilitas Math., 13, 299-302 (1978) · Zbl 0379.05010
[2] Godsil, C. D.; McKay, B. D., Asymptotic enumeration of Latin rectangles, J. Combin. Theory Ser. B, 48, 19-44 (1990) · Zbl 0687.05010
[3] Heinrich, K.; Wallis, W. D., The maximum number of intercalates in a Latin square, Combinatorial Mathematics, VIII, Geelong, 1980. Combinatorial Mathematics, VIII, Geelong, 1980, Lecture Notes in Math., 884 (1981), Springer-Verlag: Springer-Verlag New York/Berlin, p. 221-233 · Zbl 0475.05014
[4] Jacobson, M. T.; Matthews, P., Generating uniformly distributed random Latin squares, J. Combin. Des., 4, 405-437 (1996) · Zbl 0913.05027
[5] Kotzig, A.; Lindner, C. C.; Rosa, A., Latin squares with no subsquares of order two and disjoint Steiner triple systems, Utilitas Math., 7, 287-294 (1975) · Zbl 0311.05013
[6] Kotzig, A.; Turgeon, J., On certain constructions for Latin squares with no Latin subsquares of order two, Discrete Math., 16, 263-270 (1976) · Zbl 0351.05016
[7] McKay, B. D.; Rogoyski, E., Electron. J. Combin., 2, N3 (1995)
[8] McKay, B. D.; Wormald, N. C., Uniform generation of random Latin rectangles, Combin. Math. Combin. Comput., 9, 179-186 (1991) · Zbl 0751.05017
[9] McLeish, M., On the existence of Latin squares with no subsquares of order two, Utilitas Math., 8, 41-53 (1975) · Zbl 0342.05011
[10] Minc, H., Permanents. Permanents, Encyclopedia Math. Appl. (1978), Addison-Wesley: Addison-Wesley Reading · Zbl 0401.15005
[11] Pittenger, A. O., Mappings of Latin squares, Linear Algebra Appl., 261, 251-268 (1997) · Zbl 0876.05014
[12] Schrijver, A., Bounds on permanents and the number of 1-factors and 1-factorizations of bipartite graphs, London Math. Soc. Lecture Note Ser. (1983), Cambridge Univ. Press: Cambridge Univ. Press Cambridge, p. 107-134 · Zbl 0529.05048
[13] van Lint, J. H.; Wilson, R. M., A Course in Combinatorics (1992), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0769.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.