A matroid generalization of a result on row-Latin rectangles

DOI10.1006/JCTA.1999.2999MaRDI QIDQ1818212zbMATH OpenOpenAlexFDO

Authors Glenn G. Chappell

Publication date 22 March 2000

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

Latin rectanglesLatin squarestransversals

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Abstract: Let A be an m imes n matrix in which the entries of each row are all distinct. Drisko showed that, if m ge 2n-1, then A has a transversal: a set of n distinct entries with no two in the same row or column. We generalize this to matrices with entries in a matroid. For such a matrix A, we show that if each row of A forms an independent set, then we can require the transversal to be independent as well. We determine the complexity of an algorithm based on the proof of this result. Lastly, we observe that m ge 2n-1 appears to force the existence of not merely one but many transversals. We discuss a number of conjectures related to this observation (some of which involve matroids and some of which do not).

Review text

The paper is devoted to some generalization of an \textit{A. A. Drisko} result [J. Comb. Theory, Ser. A 84, No. 2, 181-195 (1998; Zbl 0915.05025)] on finding such a minimum value of \(m\) that every \(m \times n\) row-Latin rectangle has a transversal. Due to a suggested new proof of an A. A. Drisko result, the author decreases the time complexity of the computational algorithm for finding a transversal from \(O(n^4)\) to \(O(n^2)\). The paper contains also a set of unsolved problems which are suggested for further investigations and references properly covering the history of finding transversals in row-Latin rectangles.

Recommendations

• On a generalization of the matroid
• On independent transversals in matroidal Latin rectangles
• A matroid generalization of theorems of Lewin and Gallai
• scientific article; zbMATH DE number 742858
• scientific article; zbMATH DE number 3997861
• A matroid generalization of a result of Dirac
• A result on generalized Latin rectangles
• Maximising the permanent of (0,1)-matrices and the number of extensions of Latin rectangles
• Generalized laminar matroids

Cites work

• A lower bound for the length of a partial transversal in a Latin square
• An n n Latin square has a transversal with at least n- n distinct symbols
• Has Every Latin Square of Order n a Partial Latin Transversal of Size n - 1?
• scientific article; zbMATH DE number 16256 (Why is no real title available?)
• scientific article; zbMATH DE number 3613053 (Why is no real title available?)
• Transversals in row-latin rectangles
• Transversals of latin squares and their generalizations

Cited in

(4)

• Rainbow sets in the intersection of two matroids: a generalization of results of Drisko and Chappell
• Rainbow sets in the intersection of two matroids
• On the length of a partial independent transversal in a matroidal Latin square
• On independent transversals in matroidal Latin rectangles

This page was built for publication: A matroid generalization of a result on row-Latin rectangles

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