On the Length of a Partial Independent Transversal in a Matroidal Latin Square

Daniel Kotlar, Ran Ziv

Abstract


We suggest and explore a matroidal version of the Brualdi-Ryser conjecture about Latin squares. We prove that any $n\times n$ matrix, whose rows and columns are bases of a matroid, has an independent partial transversal of length $\lceil2n/3\rceil$. We show that for any $n$, there exists such a matrix with a maximal independent partial transversal of length at most $n-1$.

Keywords


Latin square; matroidal Latin square; partial independent transversal

Full Text: PDF