A092237 Maximum number of intercalates in a Latin square of order n.

0, 1, 0, 12, 4, 27, 42, 112, 72

Offset: 1

Author

Richard Bean, Feb 17 2004

Keywords

• hard
• nonn
• more

Comments

An intercalate is a 2 X 2 subsquare of a Latin square. a(10) >= 125, a(11) >= 172, a(12) >= 324.

a(13) >= 208, a(14) >= 391, a(15) >= 630, a(16) >= 960, a(17) >= 736, a(18) >= 729, a(19) >= 472, a(20) >= 1500, a(21) >= 884, a(22) >= 1497, a(23) >= 983, a(24) >= 1872, a(25) >= 1700, a(26) >= 2197, a(27) >= 648, a(28) >= 2940. - Eduard I. Vatutin, Mar 02 2025

If, in theory, all unordered pairs of rows and columns form intercalate in their intersection, total number of intercalates will be (n*(n-1))^2, so a(n) <= (n*(n-1))^2, a(n) is asymptotically less than O(n^4). In practice a(n) << (n*(n-1))^2. - Eduard I. Vatutin, Mar 11 2025

a(2^n-1) = 42*A006096(n) for n > 2. - Eduard I. Vatutin, Apr 23 2025

Due to existence of the pine Latin squares for even orders N=2n, a(2n) >= A383368(n). Pine Latin squares exist for all even orders, so a(N) >= (2k)^2 * (2k + 1) for N=4k and a(N) >= (2k+1)^3 for N=4k+2. Therefore, asymptotically maximum number of intercalates in Latin squares of even orders N greater or equal than o(k1*N^3), where k1 = 1/8. - Eduard I. Vatutin, Apr 30 2025

From Eduard I. Vatutin, Jul 01 2025: (Start)

Table showing minimums and maximums:

order | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

min number of intercalates | 0 1 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

max number of intercalates | 0 1 0 12 4 27 42 112 72 >=125 >=172 >=324 >=208 >=391 >=630 >=960 >=736 >=729 >=472 (this sequence)

.

order | 20 21 22 23 24 25 26 27 28 29

min number of intercalates | 0 0 0 0 0 0 <=15 0 <=1 0

max number of intercalates | >=1500 >=884 >=1497 >=983 >=1872 >=1700 >=2197 >=648 >=2940 ? (this sequence)

(End)

References

• I. Wanless, Private communication, 2003.

Links

• R. Bean, Critical sets in Latin squares and associated structures, Ph.D. Thesis, The University of Queensland, 2001.
• K. Heinrich and W. Wallis, The maximum number of intercalates in a Latin square, Combinatorial Math. VIII, Proc. 8th Australian Conf. Combinatorics, 1980, 221-233.
• Eduard I. Vatutin, Proving list, minimum number of intercalates (best known examples).
• Eduard I. Vatutin, Proving list, maximum number of intercalates (best known examples).
• Eduard I. Vatutin, About interconnection between maximum number of intercalates in Latin squares of order N=2^n-1 and Gaussian binomial coefficients [n,3] for q=2 (in Russian).
• Index entries for sequences related to Latin squares and rectangles.

Crossrefs

Cf. A006096, A016152, A091323, A090741, A383368.

Formula

If n is a power of 2, a(n) = n^2*(n-1)/4 = A016152(log2(n)); if n is one less than a power of 2, a(n) = n*(n-1)*(n-3)/4 = A006096(log2(n+1))*42. - updated by Eduard I. Vatutin, Jun 28 2025