What is the size of the smallest Latin square for which a weakly completable critical set of cells exists? (Q2761047)

From MaRDI portal





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
    0 references

    Identifiers