On existence of sets of distinct representatives for families of subsets of a multiset (Q1203464): Difference between revisions

For integers \(1\leq k\leq\ell\) and any collection \(A_ 1\), \(A_ 2,\dots,A_ n\) of \(\ell\)-sets, \textit{G. Katona} [A theorem of finite sets, Theory of graphs, Proc. Colloquium Tihany, Hungary 1966, 187-207 (1968; Zbl 0313.05003) Theorem 4, p. 206], solving a problem of P. Erdős, has determined a best possible upper bound for \(n\) which ensures the existence of \(n\) distinct \((l-k)\)-sets \(B_ i\subseteq A_ i(i=1,2,\dots,n)\). The present paper generalizes this result to multisets. An algorithm is given for calculating the upper bound on \(n\).