On the number of SDR of a (t,n)-family
type: Item
instance of: scholarly article
title: On the number of SDR of a (t,n)-family
zbMATH Open document ID: 0672.05002
DOI: 10.1016/S0195-6698(89)80056-3
published in: European Journal of Combinatorics
publication date: 1989-01-01T00:00:00Z
review text: A system of distinct representatives of a family \({\mathcal F}=A_ 1,...,A_ n)\) is a sequence \((a_ 1,...,a_ n)\) of distinct elements with always \(a_ i\) in \(A_ i\). Write N(\({\mathcal F})\) for the number of different such systems for the family \({\mathcal F}\). The family \({\mathcal F}\) is said to be a (t,n)-family if \(| \cup \{A_ i;i\in I\}| \geq | I| +t\) for all non-empty subsets I of \(\{\) 1,...,n\(\}\). Lt \(M(t,n)=\min \{N({\mathcal F})\); \({\mathcal F}\) is a (t,n)-family\(\}\). Thus Hall's classic theorem on distinct representatives asserts that M(0,n)\(\geq 1\). In this paper it is shown that \(M(1,n)=n+1\) and \(M(2,n)=n^ 2+n+1\). For \(0\leq t\leq 2\), the (t,n)-families \({\mathcal F}\) with N(\({\mathcal F})=M(t,n)\) are determined.
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 4099301
zbMATH Keywords: system of distinct representatives
zbMATH Keywords: family
zbMATH Keywords: (t,n)-families
author: Gerard Jennhwa Chang
reviewed by: Neil H. Williams
MaRDI profile type: Publication
cites work: Distinct representatives of subsets
cites work: On Representatives of Subsets
cites work: Transversal theory. An account of some aspects of combinatorial mathematics
cites work: On the Number of Systems of Distinct Representatives of Sets
description: scientific article; zbMATH DE number 4099301