Critical sets in Latin squares and related matters: an update. (English) Zbl 1053.05019

Keedwell, A. D.

Util. Math. 65, 97-131 (2004).

A partial Latin square of order \(n\) is uniquely completable if it is contained in exactly one Latin square of order \(n\). It is a critical set if removal of any entry destroys the uniqueness of completion. This paper surveys the state-of-the-art in critical sets. It is an update in the sense that the author wrote an earlier survey [Congr. Numerantium 113, 231–245 (1996; Zbl 0955.05019)] on the same topic. However, the present work is self contained and only rarely refers to the earlier survey.
The section headings give a good indication of the scope of the survey. They are: 1. Introduction; 2. Definitions; 3. Critical sets for group-based Latin squares; 4. Weakly completable critical sets; 5. The spectrum of critical sets; 6. The spectrum of Latin trades; 7. Upper and lower bounds for the minimal size of a Latin trade in a group-based Latin square; 8. Critical sets in direct products; 9. Critical sets for graph colourings and orthogonal Latin squares; 10. On group distances and other related results.
The study of critical sets has gained impetus through recent discoveries of connections with other branches of mathematics, for example, the famous cycle double cover conjecture from graph theory (discussed in Section 6) and triangulations and topological embeddings (discussed in Section 10).

Reviewer: Ian M. Wanless (Darwin)

MSC:

05B15

Orthogonal arrays, Latin squares, Room squares

Keywords:

critical set; partial Latin square; uniquely completable; Latin trade; Latin interchange

Citations:

Zbl 0955.05019