Restricted completion of sparse partial Latin squares

DOI10.1017/S096354831800055XzbMATH Open1436.05022arXiv1608.07383MaRDI QIDQ5222548FDOQ5222548

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)

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$.

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

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

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)

Cites Work

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

Cited In (7)

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

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)