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

DOI10.1007/S00373-018-1895-7zbMATH Open1402.05019arXiv1708.06058OpenAlexW2963266952MaRDI QIDQ2413623FDOQ2413623

Nicholas J. Cavenagh

Publication date: 14 September 2018

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: The full $n$-Latin square is the $nimesn$ array with symbols $1,2,dots,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^3(1-o(1))$. The full design $N(v,k)$ is the unique simple design with parameters $(v,k,v-2choosek-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 $vchoosek(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.

Full work available at URL: https://arxiv.org/abs/1708.06058

zbMATH Keywords

defining set\((m,n,t)\)-balanced Latin rectanglefull design, full \(n\)-Latin square

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Orthogonal arrays, Latin squares, Room squares (05B15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Defining sets of full designs with block size three. II
• Minimal defining sets for full \(2\)-\((v,3,v-2)\) designs
• Critical sets of full \(n\)-Latin squares
• The theory and application of latin bitrades: A survey
• On minimal defining sets of full designs and self-complementary designs, and a new algorithm for finding defining sets of \(t\)-designs
• On defining sets of full designs
• On defining sets of full designs with block size three
• On the spectrum of minimal defining sets of full designs
• Critical sets of 2-balanced Latin rectangles

Cited In (1)

• Title not available (Why is that?)

This page was built for publication: Lower bounds on the sizes of defining sets in full \(n\)-Latin squares and full designs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2413623)