The Smallest Size of a Maximal Family of Subsets of a Finite Set No k of Which are Pairwise Disjoint

Abstract:

      Let S be a finite set with n elements, and F_k(s) be a maximal family of subsets of S no k of which are pairwise disjoint, i.e for any A₁, … A_k∈F_k(s), there exist A_i and A_j(i≠j) such that A_i∩A_j≠φ; and for A₀?S, A₀∈F_k(S), there exist A₁′, … A_k-1′ in F_k(s) such that A₁′, … A_k-1′ and A₀ are pairwise disjoint. How large can F_k(s) be? An unper bound on size of F_k(S) has been obtained by kleitman (see [ 1 ]), but lower bound remains open. P.Erdos and D. Kleit-man asked if the smallest size of a maximal family of subsets of S on k of which are pairwise disjoint is equal to 2ⁿ-2^n-k (see [2′]) This paper answers the question nogatively, and the smallest size of F_k(s) is determined. The main results can be described as follows. Theorem 1 min|F_k(s)|≤2ⁿ-2^n-k+1, where the minimum is taken over all maximal family of subsets of S on k of which are pairwise disjoint.Theorem 2 min|F_k(s)|=2ⁿ-2^n-k+1.