The Size of the Smallest Strong Critical Set in a Latin Square.

Abstract

A critical set in a latin square is a set of entries in a latin square<E-372> which can be embedded in only one latin square. Also, if any element of the<E-384> critical set is deleted, the remaining set can be embedded in more than one latin<E-378> square. A critical set is strong if the embedding latin square is particularly easy<E-379> to find because the remaining squares of the latin square are "forced" one at a<E-392> time. A semi-strong critical set is a generalization of a strong critical set. It is<E-389> proved that the size of the smallest strong or semi-strong critical set of a latin<E-378> square of order n is ën<E-155> 2<E-165> /4û . An example of a critical set that is not strong or<E-388> semi-strong is also displayed. It is also proved that the smallest critical set of a<E-392> latin square of order 6 is 9.<E-172> 1. Introduction<E-89> This paper deals with critical sets in latin squares. A latin square, L, of<E-388> order n is a n x n array with elements chosen fro...