TY - JOUR
T1 - Covering with latin transversals
AU - Alon, Noga
AU - Spencer, Joel
AU - Tetali, Prasad
N1 - Funding Information:
*Corresponding author. I Research supported in part by a USA-Israel
PY - 1995/2/10
Y1 - 1995/2/10
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=58149209442&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=58149209442&partnerID=8YFLogxK
U2 - 10.1016/0166-218X(93)E0136-M
DO - 10.1016/0166-218X(93)E0136-M
M3 - Article
AN - SCOPUS:58149209442
SN - 0166-218X
VL - 57
SP - 1
EP - 10
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 1
ER -