Orthogonal Latin Rectangles

DOI10.1017/S0963548307008590MaRDI QIDQ3527541zbMATH OpenFDO

Authors Anders Johansson, Roland Häggkvist

Publication date 29 September 2008

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

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

zbMATH Keywords

Orthogonal Latin rectanglesorthogonal mate

Mathematics Subject Classification ID

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

Abstract: We use a greedy probabilistic method to prove that for every $epsilon>0$, every $mimesn$ Latin rectangle on $n$ symbols has an orthogonal mate, where $m=(1-epsilon)n$. That is, we show the existence of a second Latin rectangle such that no pair of the $mn$ cells receives the same pair of symbols in the two rectangles.

Recommendations

• scientific article; zbMATH DE number 26491
• Asymptotic enumeration of Latin rectangles
• Publication:4940076
• Latin squares without orthogonal mates
• On a Theorem of Mann on Latin Squares

Cites work

• A lower bound for the length of a partial transversal in a Latin square
• A lower bound for the order of a partial transversal in a latin square
• An n n Latin square has a transversal with at least n- n distinct symbols
• Asymptotically good list-colorings
• Research problems
• Transversals in row-latin rectangles
• Transversals of latin squares and their generalizations

Cited in

(14)

• On orthogonal generalized equitable rectangles
• Coloring by two-way independent sets
• An approximate version of a conjecture of Aharoni and Berger
• On a generalization of the Ryser-Brualdi-Stein conjecture
• Decomposition of bicolored square arrays into bichromatic diagonals
• Decomposition of bi-colored square arrays into balanced diagonals
• Rainbow matchings and connectedness of coloured graphs
• On a Theorem of Mann on Latin Squares
• On sets not belonging to algebras and rainbow matchings in graphs
• scientific article; zbMATH DE number 26491 (Why is no real title available?)
• scientific article; zbMATH DE number 1409235 (Why is no real title available?)
• Rainbow matchings and rainbow connectedness
• Rainbow structures in locally bounded colorings of graphs
• Full rainbow matchings in graphs and hypergraphs

This page was built for publication: Orthogonal Latin Rectangles

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