Restricted completion of sparse partial Latin squares

DOI10.1017/S096354831800055XMaRDI QIDQ5222548zbMATH OpenFDO

Authors Lina J. Andrén, Carl Johan Casselgren, Klas Markström

Publication date 6 April 2020

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.07383

zbMATH Keywords

\(\alpha \)-dense \(n \times n\) partial Latin square

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15)

Abstract: An $nimesn$ partial Latin square $P$ is called $alpha$-dense if each row and column has at most $alphan$ non-empty cells and each symbol occurs at most $alphan$ times in $P$. An $nimesn$ array $A$ where each cell contains a subset of $1,dots,n$ is a $$-array if each symbol occurs at most $$ times in each row and column and each cell contains a set of size at most $$. Combining the notions of completing partial Latin squares and avoiding arrays, we prove that there are constants $$ such that, for every positive integer $n$, if $P$ is an $alpha$-dense $nimesn$ partial Latin square, $A$ is an $nimesn$ $$-array, and no cell of $P$ contains a symbol that appears in the corresponding cell of $A$, then there is a completion of $P$ that avoids $A$; that is, there is a Latin square $L$ that agrees with $P$ on every non-empty cell of $P$, and, for each $i,j$ satisfying $1leqi,jleqn$, the symbol in position $(i,j)$ in $L$ does not appear in the corresponding cell of $A$.

Recommendations

• Constrained completion of partial Latin squares
• Completions of \(\epsilon \)-dense partial Latin squares
• scientific article; zbMATH DE number 3887704
• scientific article; zbMATH DE number 7535772
• Completing partial Latin squares with blocks of non-empty cells

Cites work

• scientific article; zbMATH DE number 3887704 (Why is no real title available?)
• scientific article; zbMATH DE number 3737686 (Why is no real title available?)
• scientific article; zbMATH DE number 1194938 (Why is no real title available?)
• A Combinatorial Theorem with an Application to Latin Rectangles
• A generalization of transversals for Latin squares
• A note on Latin squares with restricted support
• Avoidable partial Latin squares of order \(4m+1\).
• Avoiding Arrays of Odd Order by Latin Squares
• Avoiding multiple entry arrays
• Avoiding partial Latin squares and intricacy
• Chessboard squares
• Clique decompositions of multipartite graphs and completion of Latin squares
• Completing partial Latin squares with one filled row, column and symbol
• Completing partial Latin squares with one nonempty row, column, and symbol
• Completing partial Latin squares with two filled rows and two filled columns
• Completions of \(\epsilon \)-dense partial Latin squares
• Constrained completion of partial Latin squares
• Embedding Incomplete Latin Squares
• Latin squares with forbidden entries
• Latin squares with prescriptions and restrictions
• On avoiding some families of arrays
• Partial Latin squares are avoidable
• The complexity of completing partial Latin squares

Cited in

(7)

• Avoiding and extending partial edge colorings of hypercubes
• Restricted extension of sparse partial edge colorings of complete graphs
• Constrained completion of partial Latin squares
• Latin cubes of even order with forbidden entries
• Optimality analysis on partial \(l_1\)-minimization recovery
• Restricted extension of sparse partial edge colorings of hypercubes
• Completions of \(\epsilon \)-dense partial Latin squares

This page was built for publication: Restricted completion of sparse partial Latin squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5222548)