关于行拉丁矩的横截的一个猜想

A Conjecture on Transversals in Row-Latin Rectangles

一个m×n阶矩阵 ,其元素取自集合 {a1 ,a2 ,… ,ak} ,满足每一行的元素互不相同 ,称这个矩阵为基于k的一个m×n阶行拉丁矩。设R是一个m×n阶拉丁矩 ,它的n个不同行不同列的且互不相同的元素称为R的横截。1 998年 ,DRISKO提出了一个猜想 :假设k≥n ,令R是一个 ( 2n-2 ) ×n阶基于k的行拉丁矩 ,则R或有一个横截 ,或R同痕于行拉丁矩A(2n- 2 )×n,这里A(2n- 2 )×n 是 ( 2n-2 )×n阶矩阵 ,它的元素是由记号 1 ,2 ,… ,n ,组成 ,其中前n -1行为 ( 1 ,2 ,… ,n-1 ,n) ,其余的n-1行都为 ( 2 ,3 ,… ,n ,1 )。本文利用行拉丁矩的配对算法 。

An m×n row-latin rectangle based on k is an m×n array R whose entries are elements of {a 1,a 2,...,a k} such that no entry occurs more than once in any row. A transversal in an m×n row-latin rectangle R is a set of n distinct entries of R, no two of which are in the same row or column. In 1998, DRISKO suggested the conjecture: Suppose that k≥n. Let R be a (2n-2)×n row-latin rectangle based on k. Then R either has a transversal, or is isotopic to A (2n-2)×n whose first n-1 rows consist of symbols 1,2,...,n in order and whose remaining rows have the same symbols in the order 2,3,...,n,1. In this paper, we use the matched algorithm for finding a transversal in m×n row-latin rectangle if m>2n-2 and show the conjecture is true.