A307164 Maximum number of intercalates in a diagonal Latin square of order n.

0, 0, 0, 12, 4, 9, 30, 112, 72

Offset: 1

Author

Eduard I. Vatutin, Mar 27 2019

Keywords

• nonn
• more
• hard

Comments

An intercalate is a 2 X 2 subsquare of a Latin square.

0 <= A307163(n) <= A307164(n) <= A092237(n). - Eduard I. Vatutin, Sep 21 2020

a(10) >= 109, a(11) >= 172, a(12) >= 324, a(13) >= 180, a(14) >= 391, a(15) >= 630, a(16) >= 960, a(17) >= 736, a(18) >= 547, a(19) >= 457, a(20) >= 1100, a(21) >= 785, a(22) >= 887, a(23) >= 899, a(24) >= 1680, a(25) >= 1700, a(26) >= 1299, a(27) >= 1372, a(28) >= 2892. - Eduard I. Vatutin, May 31 2021, updated 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 05 2025

Examples

			From _Eduard I. Vatutin_, May 31 2021: (Start)
One of the best known diagonal Latin squares of order n=5
  0 1 2 3 4
  4 2 0 1 3
  1 4 3 2 0
  3 0 1 4 2
  2 3 4 0 1
has 4 intercalates:
  . . 2 3 .   . . . . .   . . . . .   . . . . .
  . . . . .   . . 0 . 3   . . . . .   . . . . .
  . . 3 2 .   . . 3 . 0   1 . 3 . .   . 4 3 . .
  . . . . .   . . . . .   3 . 1 . .   . . . . .
  . . . . .   . . . . .   . . . . .   . 3 4 . .
so a(5)=4. (End)
		

Links

• Eduard I. Vatutin, Discussion about properties of diagonal Latin squares at forum.boinc.ru (in Russian).
• Eduard I. Vatutin, About the maximum number of intercalates in a diagonal Latin squares of order 9 (in Russian).
• Eduard I. Vatutin, About the heuristic approximation of the spectrum of number of intercalates in diagonal Latin squares of order 14 (in Russian).
• Eduard I. Vatutin, Proving list (best known examples).
• Eduard Vatutin, Alexey Belyshev, Natalia Nikitina, and Maxim Manzuk, Evaluation of Efficiency of Using Simple Transformations When Searching for Orthogonal Diagonal Latin Squares of Order 10, High-Performance Computing Systems and Technologies in Sci. Res., Automation of Control and Production (HPCST 2020), Communications in Comp. and Inf. Sci. book series (CCIS, Vol. 1304) Springer, Cham (2020), 127-146.
• Eduard I. Vatutin, Natalia N. Nikitina, and Maxim O. Manzuk, First results of an experiment on studying the properties of DLS of order 9 in the volunteer distributed computing projects Gerasim@Home and RakeSearch (in Russian).
• Eduard I. Vatutin, Natalia N. Nikitina, Maxim O. Manzuk, Alexandr M. Albertyan, and Ilya I. Kurochkin, On the construction of spectra of fast-computable numerical characteristics for diagonal Latin squares of small order, Intellectual and Information Systems (Intellect - 2021), Tula, 2021, pp. 7-17 (in Russian).
• E. I. Vatutin, V. S. Titov, A. I. Pykhtin, A. V. Kripachev, N. N. Nikitina, M. O. Manzuk, A. M. Albertyan and I. I. Kurochkin, Estimation of the Cardinalities of the Spectra of Fast-computable Numerical Characteristics for Diagonal Latin Squares of Orders N>9 (in Russian) // Science and education in the development of industrial, social and economic spheres of Russian regions. Murom, 2022. pp. 314-315.
• Index entries for sequences related to Latin squares and rectangles.

Crossrefs

Cf. A092237, A307163, A345760.

Extensions

a(9) added by Eduard I. Vatutin, Sep 21 2020