Systems of Representatives

详细

Lower and upper bounds are obtained for the size ζ(n, r, s, k) of a minimum system of common representatives for a system of families of k-element sets. By ζ(n, r, s, k) wemean themaximum (over all systems Σ = {M₁, …, M_r} of sets M_i consisting of at least s subsets of {1, …, n} of cardinality not exceeding k) of the minimum size of a system of common representatives of Σ. The obtained results generalize previous estimates of ζ(n, r, s, 1).