Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-26T16:33:02.863Z Has data issue: false hasContentIssue false
  • English
  • Français

Covering Problem for Idempotent Latin Squares

Published online by Cambridge University Press:  20 November 2018

Katherine Heinrich
Katherine Heinrich*
Affiliation:
Department of Mathematics, Simon Fraser University, Burnaby B.C.VSA IS6
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.

Let A = (aij) be an idempotent latin square of order n, n ≥ 3, in which aii = i, 1 ≤ i ≤ nc. A set S ⊆ N = {1, 2, …, n} is a cover of A if (N × N)\{(i, i):i ∉ S} = {(i, j): i ∊ S, j ∊ N} ∪ {(j, i): i ∊ S, j ∊ N} ∪ {(i, j): aij ∊ S}. A cover S is minimum for A if |S| < |T| for every cover T of A and we write c(A) = |S|. We denote by c(n) the maximum value of c(A) over all idempotent latin squares A of order n and in this paper show that (7n/10)-3.8 ≤ c (n) < n - n1/3 + 1 for all n ≥ 15. The problem of determining c(n) was first raised by J. Schönheim.

Keywords

05B15
Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 26 , Issue 2 , 01 June 1983 , pp. 144 - 148
Copyright
Copyright © Canadian Mathematical Society 1983

References

1. Rouse Ball, W. W. and Coxeter, H. S. M., Mathematical Recreations and Essays. University of Toronto Press, 1974.Google Scholar
2. Bose, R. C., Shrikhande, S. S. andParker, E. T., Further results on the construction of mutually orthogonal latin squares and the falsity of Euler's conjecture. Canad. J. Math. 12 (1960), 189–203.Google Scholar
3. Dénes, J. and Keedwell, A. D., Latin Squares and their Applications. Akadémiai Kiadό, Budapest, 1974.Google Scholar
4. Kraitchik, Maurice, Mathematical Recreations. Dover, 1953.Google Scholar
5. Schönheim, J., Problem 32 in Combinatorial Structures and their Applications. Proceedings of the Calgary Conference, Gordon and Breach, 1969, p. 505.Google Scholar