What is the size of the smallest Latin square for which a weakly completable critical set of cells exists? (Q2761047)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: What is the size of the smallest Latin square for which a weakly completable critical set of cells exists? |
scientific article; zbMATH DE number 1682909
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | What is the size of the smallest Latin square for which a weakly completable critical set of cells exists? |
scientific article; zbMATH DE number 1682909 |
Statements
17 December 2001
0 references
uniquely completable set
0 references
critical set
0 references
What is the size of the smallest Latin square for which a weakly completable critical set of cells exists? (English)
0 references
A Latin square of order \(n\) yields a set of \(n^2\) triples \((i,j,k)\), where \(k\) is the entry in the cell of row \(i\) and column \(j\). For a fixed \(n\), a set \(U\) of triples is called uniquely completable (a UC set), if there is a unique Latin square of order \(n\) which has \(U\) as a subset of its triples. The completion process includes situations when, for a given symbol, the placement of the symbol in all cells of a certain row (or a certain column), but in one cell, would yield an immediate contradiction to the definition of the Latin square, forcing thus the placement of the symbol to the distinguished cell of the row (or of the column). It also contains situations when, for a given cell, the placement of all symbols, but one, would contradict the definition of the Latin square in an immediate way, forcing thus again an addition of a triple to the set which is being completed. A UC set is called strong, if its full completion can be enforced in this way, step by step. The paper contains a proof that every UC set is strong, if \(n \leq 4\), and for \(n=5\) presents (without a proof) an example of a UC set that is not strong.
0 references