Search Advanced

AIMS Mathematics

2021, Volume 6, Issue 1: 261-295. doi: 10.3934/math.2021017
Previous Article Next Article
Research article Special Issues

A census of critical sets based on non-trivial autotopisms of Latin squares of order up to five

  • 1.
    Department of Applied Mathematics I. Universidad de Sevilla, Spain
  • 2.
    School of Computing and Mathematics. University of South Wales, United Kingdom
  • Received: 14 August 2020 Accepted: 07 October 2020 Published: 10 October 2020

  • MSC : 05B15

  • This paper delves into the study of critical sets of Latin squares having a given isotopism in their autotopism group. Particularly, we prove that the sizes of these critical sets only depend on both the main class of the Latin square and the cycle structure of the isotopism under consideration. Keeping then in mind that the autotopism group of a Latin square acts faithfully on the set of entries of the latter, we enumerate all the critical sets based on autotopisms of Latin squares of order up to five.

    Citation: Raúl M. Falcón, Laura Johnson, Stephanie Perkins. A census of critical sets based on non-trivial autotopisms of Latin squares of order up to five[J]. AIMS Mathematics, 2021, 6(1): 261-295. doi: 10.3934/math.2021017

    Related Papers:

  • This paper delves into the study of critical sets of Latin squares having a given isotopism in their autotopism group. Particularly, we prove that the sizes of these critical sets only depend on both the main class of the Latin square and the cycle structure of the isotopism under consideration. Keeping then in mind that the autotopism group of a Latin square acts faithfully on the set of entries of the latter, we enumerate all the critical sets based on autotopisms of Latin squares of order up to five.


    加载中


    [1] C. J. Colbourn, M. J. Colbourn, D. R. Stinson, The computational complexity of recognizing critical sets, Lect. Notes Math., 1073 (1984), 248-253. doi: 10.1007/BFb0073124
    [2] C. J. Colbourn, The complexity of completing partial Latin squares, Discrete Appl. Math., 8 (1984), 25-30. doi: 10.1016/0166-218X(84)90075-1
    [3] J. Nelder, Critical sets in Latin squares. In: CSIRO Division of Math. and Stats, Newsletter, 1977.
    [4] J. Cooper, D. Donovan, J. Seberry, Latin squares and critical sets of minimal size, Australas. J. Combin., 4 (1991), 113-120.
    [5] J. A. Bate, G. H. J. van Rees, The size of the smallest strong critical set in a Latin square, Ars Comb., 53 (1999), 73-83.
    [6] N. Cavenagh, D. Donovan, A. Khodkar, On the spectrum of critical sets in back circulant Latin squares, Ars Combin., 82 (2007), 287-319.
    [7] B. Smetaniuk, On the minimal critical set of a Latin square, Utilitas Math., 16 (1979), 97-100.
    [8] D. Curran, G. H. J. Van Rees, Critical sets in Latin squares. In: Proceedings of the Eighth Manitoba Conference on Numerical Mathematics and Computing, Congress. Numer., XXII, 1979,165-168.
    [9] D. R. Stinson, G. H. J. Van Rees, Some large critical sets, Congr. Numer., 34 (1982), 441-456.
    [10] A. P. Street, Defining sets for t-designs and critical sets for Latin squares, New Zealand J. Math., 21 (1992), 133-144.
    [11] A. D. Keedwell, Critical sets for Latin squares, graphs and block designs: a survey, Congr. Numer., 113 (1996), 231-245.
    [12] A. D. Keedwell, Critical sets in Latin squares: An Intriguing Problem, Math. Gaz., 85 (2001), 239-244. doi: 10.2307/3622009
    [13] A. D. Keedwell, Critical sets in Latin squares and related matters: an update, Util. Math., 65 (2004), 97-131.
    [14] N. J. Cavenagh, The theory and application of Latin bitrades: a survey, Math. Slovaca, 58 (2008), 691-718.
    [15] P. Adams, R. Bean, A. Khodkar, A census of critical sets in the Latin squares of order at most six, Ars Combin., 68 (2003), 203-223.
    [16] D. Donovan, A. Howse, Critical sets for Latin squares of order 7, J. Combin. Math. Combin. Comput., 28 (1998), 113-123.
    [17] A. Hulpke, P. Kaski, P. R. J.?sterg?rd, The number of Latin squares of order 11, J. Math. Comp., 80 (2011), 1197-1219.
    [18] G. Kolesova, C. W. H. Lam, L. Thiel, On the number of 8 × 8 Latin squares, J. Combin. Theory Ser. A, 54 (1990), 143-148. doi: 10.1016/0097-3165(90)90015-O
    [19] B. D. McKay, A. Meynert, W. Myrvold, Small Latin squares, quasigroups, and loops, J. Combin. Des., 15 (2007), 98-119.
    [20] R. M. Falcón, The set of autotopisms of partial Latin squares, Discrete Math., 313 (2013), 1150- 1161.
    [21] R. M. Falcón, Enumeration and classification of self-orthogonal partial Latin rectangles by using the polynomial method, European J. Combin., 48 (2015), 215-223.
    [22] R. M. Falcón, R. J. Stones, Classifying partial Latin rectangles, Electron. Notes Discrete Math., 49 (2015), 765-771. doi: 10.1016/j.endm.2015.06.103
    [23] R. M. Falcón, O. J. Falcón, J. Nú?ez, Counting and enumerating partial Latin rectangles by means of computer algebra systems and CSP solvers, Math. Methods Appl. Sci., 41 (2018), 7236-7262.
    [24] R. M. Falcón, R. J. Stones, Enumerating partial Latin rectangles, Electron. J. Combin., 27 (2020), ]P2.47.
    [25] J. Browning, D. S. Stones, I. Wanless, Bounds on the number of autotopisms and subsquares of a Latin square, Combinatorica, 33 (2013), 11-22. doi: 10.1007/s00493-013-2809-1
    [26] R. M. Falcón, R. J. Stones, Partial Latin rectangle graphs and autoparatopism groups of partial Latin rectangles with trivial autotopism groups, Discrete Math., 340 (2017), 1242-1260. doi: 10.1016/j.disc.2017.01.002
    [27] D. Kotlar, Parity types, cycle structures and autotopisms of Latin squares, Electron. J. Combin., 19 (2012), 10.
    [28] D. S. Stones, Symmetries of partial Latin squares, European J. Combin., 34 (2013), 1092-1107. doi: 10.1016/j.ejc.2013.02.005
    [29] R. M. Falcón, V. álvarez, F. Gudiel, A computational algebraic geometry approach to analyze pseudo-random sequences based on Latin squares, Adv. Comput. Math., 45 (2019), 1769-1792. doi: 10.1007/s10444-018-9654-0
    [30] E. Danan, R. M. Falcón, D. Kotlar, T. G. Marbach, R. J. Stones, Refining invariants for computing autotopism groups of partial Latin rectangles, Discrete Math., 343 (2020), 1-21.
    [31] R. M. Falcón, Using a CAS/DGS to analyze computationally the configuration of planar bar linkage mechanisms based on partial Latin squares, Math. Comp. Sc., 14 (2020), 375-389.
    [32] D. Kotlar, Computing the autotopy group of a Latin square by cycle structure, Discrete Math., 331 (2014), 74-82. doi: 10.1016/j.disc.2014.05.004
    [33] R. Stones, R. M. Falcón, D. Kotlar, T. G. Marbach, Computing autotopism groups of partial Latin rectangles: a pilot study, Comput. Math. Meth., (2020), e1094.
    [34] R. Stones, R. M. Falcón, D. Kotlar, T. G. Marbach, Computing autotopism groups of partial Latin rectangles, J. Exp. Algorithmics, 25 (2020), 1-39.
    [35] R. J. Stones, M. Su, X. Liu, G. Wang, S. Lin, A Latin square autotopism secret sharing scheme, Des. Codes Cryptogr., 35 (2015), 1-16
    [36] M. Yan, J. Feng, T. G. Marbach, R. J. Stones, G. Wang, X. Liu, Gecko: A resilient dispersal scheme for multi-cloud storage, IEEE Access, 7 (2019), 77387-77397. doi: 10.1109/ACCESS.2019.2920405
    [37] L. Yi, R. J. Stones, G. Wang, Two-erasure codes from 3-plexes. In: Network and Parallel Computing. Springer International Publishing, Cham, 2019,264-276.
    [38] R. J. Stones, K-plex 2-erasure codes and Blackburn partial Latin squares, IEEE Trans. Inf. Theory, 66 (2020), 3704-3713. doi: 10.1109/TIT.2020.2967758
    [39] R. M. Falcón, O. J. Falcón, J. Nú?ez, A historical perspective of the theory of isotopisms, Symmetry, 10 (2018), 322.
    [40] R. M. Falcón, Latin squares associated to principal autotopisms of long cycles. Application in Cryptography. In: Proceedings of Transgressive Computing 2006: a conference in honor of Jean Della Dora, Université J. Fourier, Grenoble, France, 2006,213-230.
    [41] R. M. Falcón, Study of critical sets in Latin squares by using the autotopism group, Electron. Notes Discrete Math., 29 (2007), 503-507.
    [42] S. D. Andres, R. M. Falcón, Autotopism stabilized colouring games on rook's graphs, Discrete Appl. Math., 266 (2019), 200-212.
    [43] N. J. Cavenagh, D. S. Stones, Near-automorphisms of Latin squares, J. Combin. Des., 19 (2011), 365-377. doi: 10.1002/jcd.20282
    [44] M. Grüttmüller, Completing partial Latin squares with two cyclically generated prescribed diagonals, J. Combin. Theory Ser. A, 103 (2003), 349-362.
    [45] M. Grüttmüller, Completing partial Latin squares with prescribed diagonals, Discrete Appl. Math., 138 (2004), 89-97.
    [46] R. M. Falcón, J. Martín-Morales, Gr?bner bases and the number of Latin squares related to autotopisms of order up to 7, J. Symb. Comput., 42 (2007), 1142-1154.
    [47] D. S. Stones, P. Vojtěchovsky, I. M. Wanless, Cycle structure of autotopisms of quasigroups and Latin squares, J. Combin. Des., 20 (2012), 227-263. doi: 10.1002/jcd.20309
    [48] W. Decker, G. M. Greuel, G. Pfister, et al., Singular 4-1-3 A computer algebra system for polynomial computations, 2020. Available from: http://www.singular.uni-kl.de.
    [49] R. M. Falcón, L. Johnson, S. Perkins, Equivalence classes of critical sets based on non-trivial autotopisms of Latin squares, Mendeley Data, v1, 2020. Available from: http://dx.doi.org/10.17632/fkm575299m.1.
    [50] H. A. Norton, The 7 × 7 squares, Ann. Eugenics, 9 (1939), 269-307.
    [51] A. Drápal, T. Kepka, Exchangeable groupoids I, Acta Univ. Carolin.—Math. Phys., 24 (1983), 57-72.
    [52] D. Donovan, A. Howse, P. Adams, A discussion of Latin interchanges, J. Combin. Math. Combin. Comput., 23 (1997), 161-182.
    [53] N. Cavenagh, D. Donovan, A. Drápal, Constructing and deconstructing Latin trades, Discrete Math., 284 (2004), 97-105.
    [54] N. Cavenagh, D. Donovan, 3-Homogeneous Latin trades, Discrete Math., 300 (2005), 57-70.
    [55] D. Donovan, J. A. Cooper, D. J. Nott, J. Seberry, Latin squares: Critical sets and their lower bounds, Ars Combin., 39 (1995), 33-48.
  • Reader Comments
  • © 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
AIMS Mathematics
1.8 3.4

Metrics

Article views(3281) PDF downloads(122) Cited by(1)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(4)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog