Hall's condition for partial Latin squares

MaRDI QIDQ2799808zbMATH OpenFDO

Authors Emil R. Vaughan, A. J. W. Hilton

Publication date 13 April 2016

Published in Congressus Numerantium (Search for Journal in Brave)

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

zbMATH Keywords

Hall's conditionLatin squarepartial Latin square

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15)

Abstract: Hall's Condition is a necessary condition for a partial latin square to be completable. Hilton and Johnson showed that for a partial latin square whose filled cells form a rectangle, Hall's Condition is equivalent to Ryser's Condition, which is a necessary and sufficient condition for completability. We give what could be regarded as an extension of Ryser's Theorem, by showing that for a partial latin square whose filled cells form a rectangle, where there is at most one empty cell in each column of the rectangle, Hall's Condition is a necessary and sufficient condition for completability. It is well-known that the problem of deciding whether a partial latin square is completable is NP-complete. We show that the problem of deciding whether a partial latin square that is promised to satisfy Hall's Condition is completable is NP-hard.

Review text

\textit{A. J. W. Hilton} and \textit{P. D. Johnson jun.} [in: Topics in combinatorics and graph theory. Essays in honour of Gerhard Ringel. Heidelberg: Physica-Verlag. 359--371 (1990; Zbl 0731.05017)] formulated a necessary, so called Hall's condition, for a partial Latin square to be completable. In this paper, it is shown that this condition is sufficient as well for some classes of partial Latin squares.

Recommendations

• scientific article; zbMATH DE number 5944469
• Completing partial Latin squares: Cropper's problem
• A note on completing Latin squares
• Hall's theorem and extending partial Latinized rectangles
• Cropper's question and Cruse's theorem about partial Latin squares

Cited in

(7)

• An analogue of Ryser's theorem for partial Sudoku squares
• The Hall strength and the conjugate Hall strength of a partial Latin square
• Cropper's question and Cruse's theorem about partial Latin squares
• On Smetaniuk's Construction for Latin Squares and the Andersen-Hilton Theorem
• Hall's theorem and extending partial Latinized rectangles
• Refinements of Hall's condition
• Completing partial Latin squares: Cropper's problem

This page was built for publication: Hall's condition for partial Latin squares

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