Covering with latin transversals

Noga Alon, Joel Spencer, Prasad Tetali

Research output: Contribution to journalArticle

Abstract

Given an n × n matrix A = [aij], a transversal of A is a set of elements, one from each row and one from each column. A transversal is a latin transversal if no two elements are the same. Erdös and Spencer showed that there always exists a latin transversal in any n × n matrix in which no element appears more than s times, for s≤ (n - 1)/16. Here we show that, in fact, the elements of the matrix can be partitioned into n disjoint latin transversals, provided n is a power of 2 and no element appears more than εn times for some fixed ε>0. The assumption that n is a power of 2 can be weakened, but at the moment we are unable to prove the theorem for all values of n.

Original languageEnglish (US)
Pages (from-to)1-10
Number of pages10
JournalDiscrete Applied Mathematics
Volume57
Issue number1
DOIs
StatePublished - Feb 10 1995

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Covering with latin transversals'. Together they form a unique fingerprint.

  • Cite this