Loading...
Thumbnail Image
Item

Lower bounds on the sizes of defining sets in full n-Latin squares and full designs

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.
Type
Journal Article
Type of thesis
Series
Citation
Cavenagh, 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
Date
2018
Publisher
Springer Japan KK
Degree
Supervisors
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