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

DOI10.1007/S00373-018-1895-7MaRDI QIDQ2413623zbMATH OpenOpenAlexFDO

Authors Nicholas J. Cavenagh

Publication date 14 September 2018

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

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

zbMATH Keywords

\((m,n,t)\)-balanced Latin rectangledefining setfull design, full \(n\)-Latin square

Mathematics Subject Classification ID

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

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.

Review text

An \((m,n,t)\)-balanced Latin rectangle is an \(m \times n\) array A with each entry containing a size \(t\) multi-subset of \(T = \{1,2, \ldots, t\}\) such that each element of \(T\) appears \(n\) times in each row and \(m\) times in each column of \(A\). This paper looks at minimum size of defining sets for \((m,n,t)\)-balanced Latin rectangles whose entries all equal \(T\). For \(n=m=t\), it is established that for large \(n\), the size of such a defining set is at least \(n^3(1-S)\) where S if a function of order \(n^{-0.5}\). A slightly more complicated asymptotic bound is also given for more general \(m\), \(n\), \(t\). Minimum sizes of defining sets are also considered for the \((v,k, \binom{v-2}{k-2})\) BIBD containing each size \(k\) subset of the point set once; here it is shown that for large \(v-k\), the size of such a defining set is at least \(\binom{v}{k} (1-S)\) where \(S\) is a function of order \((v-k)^{-0.5}\).

Recommendations

• Critical sets of full \(n\)-Latin squares
• On defining sets of full designs
• On the spectrum of minimal defining sets of full designs
• On defining sets of full designs with block size three
• On defining sets of full designs and of designs related to them

Cites work

• Constructing defining sets of full designs
• Critical sets of 2-balanced Latin rectangles
• Critical sets of full \(n\)-Latin squares
• Defining sets of full designs with block size three. II
• scientific article; zbMATH DE number 2114508 (Why is no real title available?)
• Minimal defining sets for full 2-(v,3,v-2) designs
• On defining sets of full designs
• On defining sets of full designs and of designs related to them
• On defining sets of full designs with block size three
• On minimal defining sets of full designs and self-complementary designs, and a new algorithm for finding defining sets of \(t\)-designs
• On the spectrum of minimal defining sets of full designs
• The theory and application of latin bitrades: A survey
• Using affine planes to partition full designs with block size three.

Cited in

(4)

• Constructing (0,1)-matrices with large minimal defining sets
• Defining sets for Latin squares given that they are based on groups
• scientific article; zbMATH DE number 90345 (Why is no real title available?)
• On the distances between Latin squares and the smallest defining set size

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)