Critical sets in nets and Latin squares (Q1333109)

A partial plane \(P\) is an incidence structure consisting of a set of objects called points, together with a list of certain non-empty point subsets called lines such that any two distinct points are contained in at most one line. A subset may appear more than once in the list of lines, but such a subset must have exactly one point. \(P\) is finite if it has finitely many points and lines. It is obvious that two distinct lines of \(P\) meet in at most one point. A net \(N\) of order \(n\) and degree \(r\), where \(r\) and \(n\) are positive integers, is a finite partial plane satisfying the following conditions: i) \(N\) has exactly \(n^ 2\) points. ii) Each line consists of exactly \(n\) points. iii) The set of lines may be partitioned into \(r\) subsets, called parallel classes, each consisting of mutually disjoint lines. Lines in the same parallel class are said to be parallel. iv) Any two non-parallel lines meet in a point. v) The \(r\) parallel classes are ordered and the lines in each parallel class are ordered. A partial net of degree \(r\) is a partial plane satisfying conditions (iii) and (v) above. A Latin square \(L\) of order \(n\) over a set \(S\), where \((S) = n\), is an \(n \times n\) array of elements (the entries of \(L\)) such that each element of \(S\) appears exactly once in each row and each column. The idea of critical set in a Latin square appears to have been introduced by J. A. Nelder (1977) and has been studied by various authors. Critical sets have applications to cryptography and agriculture [see e.g. Colbourn et al., 1984; Curran and Van Rees, 1978; Nelder, 1977; Seberry, 1990; Semtaniuk, 1979; Stinson and Van Rees, 1982]. Broadly speaking, a critical set in a Latin square \(L\) is a set \(C\) of entries which uniquely determines \(L\) and is minimal with respect to this property. Putting it in another way, \(L\) is the only Latin square of that order which contains \(C\), but any proper subset of \(C\) is contained in at least one other Latin square of the same order as \(L\). Bounds for the size of critical sets of a general Latin square of order \(n\) are somewhat crude. For instance, in this paper the authors prove in Theorem 4.2 that a critical set of Latin square of order \(n\) must contain at least \(n + 1\) elements if \(n \geq 5\). They prove this by establishing, in Theorem 4.1, a special embedding of Latin square of order \(m\) into Latin square of order \(n\) for any \(n > 2m\). By translating the idea of critical sets of Latin squares to nets, and regarding Latin squares as nets of order 3, they obviate the need to consider separately the six parastrophes (see Denes and Keedwell, 1972) of a Latin square. It can be noted that a Latin square and its parastrophes correspond to just one net of degree 3. Thus, the concepts of rows, columns and entry labels appear different in the context of Latin squares, but merely correspond to lines in different parallel classes in the associated net. Moreover, a critical set in the net corresponds to a critical set in each of the parastrophes. Thus the concept of a critical set in a Latin square is extended to the more general setting of nets. A lower bound is given for the size of a critical set in a group-based net. In the case of a general net of degree 3 and order \(n\) (\(n \geq 5\)), it is shown that the size of a critical set is bounded below by \(n + 1\). In the proof of this result, a special embedding of a Latin square of order \(m\) into a suitable Latin square of order \(n\) is established for every \(n \geq 2m\).