A conjecture on the number of SDRs of a (t, n)-family

作者：He, Dawei^*; Lu, Changhong

来源：European Journal of Combinatorics, 2012, 33(1): 1-7.

DOI：10.1016/j.ejc.2011.07.007

A system of distinct representatives (SDR) of a family F = (A(1), ... A(n)) is a sequence (x(1), ... ,x(n)) of n distinct elements with x(i) is an element of A(i) for 1 <= i <= n. Let N(F) denote the number of SDRs of a family F; two SDRs are considered distinct if they are different in at least one component. For a nonnegative integer t, a family F = (A1, ... ,A(n)) is called a (t, n)-family if the union of any k >= 1 sets in the family contains at least k t elements. The famous Hall's theorem says that N(F) >= 1 if and only if F is a (0, n)-family. Denote by M(t, n) the minimum number of SDRs in a (t. n)-family. The problem of determining M(t, n) and those families containing exactly M(t, n) SDRs was first raised by Chang [G.J. Chang, On the number of SDR of a (t, n)-family, European J. Combin. 10 (1989) 231-234]. He solved the cases when 0 <= t <= 2 and gave a conjecture for t >= 3. In this paper, we solve the conjecture.

• 出版日期2012-1
• 单位华东师范大学