Lower bounds on the sizes of defining sets in full n-Latin squares and full designs
Citation
Export citationCavenagh, N. J. (2018). Lower bounds on the sizes of defining sets in full n-Latin squares and full designs. Graphs and Combinatorics, 34(4), 571–577. https://doi.org/10.1007/s00373-018-1895-7
Permanent Research Commons link: https://hdl.handle.net/10289/12058
Abstract
The full n-Latin square is the n×n array with symbols 1, 2, . . . , n in each cell. In this paper we show, as part of a more general result,that any defining set for the full n-Latin square has size n³(1 − o(1)). The full design N(v, k) is the unique simple design with parameters (v,k,{v-2 \atopwithdelims ()k-2}); that is, the design consisting of all subsets of size k from a set of size v. We show that any defining set for the full design N(v, k) has size {v\atopwithdelims ()k}(1-o(1)) (as v-k becomes large). These results improve existing results and are asymptotically optimal. In particular, the latter result solves an open problem given in (Donovan, Lefevre, et al, 2009), in which it is conjectured that the proportion of blocks in the complement of a full design will asymptotically approach zero.
Date
2018Type
Publisher
Springer Japan KK
Rights
© Springer Japan KK, part of Springer Nature 2018.This is the author's accepted version. The final publication is available at Springer via dx.doi.org/10.1007/s00373-018-1895-7