Covering with Latin transversals
type: Item
instance of: scholarly article
title: Covering with Latin transversals
zbMATH Open document ID: 0817.05018
DOI: 10.1016/0166-218X(93)E0136-M
author: Noga Alon
author: Prasad Tetali
author: Joel Spencer
published in: Discrete Applied Mathematics
publication date: 1995-07-11T00:00:00Z
review text: A Latin transversal is a set of elements from a square matrix, one from each row and column and no two the same. As the authors note, the supply of conjectures about Latin transversals outstrip the ability to resolve them. In this paper, the authors show that the elements of an \(n\) by \(n\) matrix can be partitioned into \(n\) Latin transversals provided (1) \(n\) is a power of two, and (2) no element appears more than \(pn\) times, for some fixed \(p\). The proof uses the probabilistic method relying on the Lovász local lemma. The authors, of course, add to the supply of unresolved conjectures by suggesting that the result proved should hold for all \(n\).
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 734611
zbMATH Keywords: covering
zbMATH Keywords: Latin transversal
zbMATH Keywords: square matrix
zbMATH Keywords: probabilistic method
zbMATH Keywords: Lovász local lemma
reviewed by: Rakesh V. Vohra
MaRDI profile type: Publication
cites work: The strong chromatic number of a graph
cites work: An algorithmic approach to the Lovász local lemma. I
cites work: Q4769064
cites work: Has Every Latin Square of Order n a Partial Latin Transversal of Size n - 1?
cites work: Q4074927
cites work: Lopsided Lovász Local lemma and Latin transversals
cites work: Q5592263
cites work: Q3481743
cites work: Transversals of latin squares and their generalizations
cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
full work available at URL: 0166-218x(93)e0136-m
OpenAlex ID: W4210536965
description: scientific article; zbMATH DE number 734611