极大的无k个子集两两不相交的子集系的最小容量

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

中文摘要:

      本文从认识村镇建设现状和发展经济与建设的辩证关系入手,把城乡视为一个相互依存、彼此协调的经济、社会体系的思想来研究黑龙江省村镇建设发展战略。本文为黑龙江省的村镇建设(不论在总体布局、或具体目标等方面)指出了明确的发展方向。文章指出:到本世纪末,本省将初步建立起城乡协调发展的城、镇、村完整体系;乡村经济进一步向农工商综合发展;乡村剩余劳力将得到合理转移;乡村人口得到适度集中;村镇建设面貌大为改观;乡村城镇化程度将有明显的提高。

英文摘要:

      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.