Mathematics – Combinatorics
Scientific paper
2010-07-13
Mathematics
Combinatorics
Scientific paper
A system of distinct representatives (SDR) of a family $F = (A_1, \cdots, A_n)$ is a sequence $(x_1, \cdots, x_n)$ of $n$ distinct elements with $x_i \in A_i$ for $1 \le i \le 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=(A_1,\cdots,A_n)$ is called a $(t,n)$-family if the union of any $k\ge 1$ sets in the family contains at least $k+t$ elements. The famous Hall's Theorem says that $N(F)\ge 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 [European J. Combin.{\bf 10}(1989), 231-234]. He solved the cases when $0\le t\le 2$ and gave a conjecture for $t\ge 3$. In this paper, we solve the conjecture. In fact, we get a more general result for so-called valued $(t,n)$-family.
He Dawei
Lu Changhong
No associations
LandOfFree
On the number of a SDRs of a valued (t,n)-family does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the number of a SDRs of a valued (t,n)-family, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the number of a SDRs of a valued (t,n)-family will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-350441