On the number of a SDRs of a valued (t,n)-family

preprint2010arXivOpen access

Abstract

A system of distinct representatives (SDR) of a family F=(A1,⋯ ,An)F = (A_1, \cdots, A_n) is a sequence (x1,⋯ ,xn)(x_1, \cdots, x_n) of nn distinct elements with xi∈Aix_i \in A_i for 1≤i≤n1 \le i \le n. Let N(F)N(F) denote the number of SDRs of a family FF; two SDRs are considered distinct if they are different in at least one component. For a nonnegative integer tt, a family F=(A1,⋯ ,An)F=(A_1,\cdots,A_n) is called a (t,n)(t,n)-family if the union of any k≥1k\ge 1 sets in the family contains at least k+tk+t elements. The famous Hall's Theorem says that N(F)≥1N(F)\ge 1 if and only if FF is a (0,n)(0,n)-family. Denote by M(t,n)M(t,n) the minimum number of SDRs in a (t,n)(t,n)-family. The problem of determining M(t,n)M(t,n) and those families containing exactly M(t,n)M(t,n) SDRs was first raised by Chang [European J. Combin.{\bf 10}(1989), 231-234]. He solved the cases when 0≤t≤20\le t\le 2 and gave a conjecture for t≥3t\ge 3. In this paper, we solve the conjecture. In fact, we get a more general result for so-called valued (t,n)(t,n)-family.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.