Prime Factorization of Sperner Theory

作者: 张泰滺 , 晁福刚 :华东师范大学数学系,上海; 任韩 :华东师范大学数学系,上海;上海市核心数学与实践重点实验室,上海;

关键词: Sperner定理生成函数对称链Sperner Theory Generating Function Method Symmetric Chain

摘要: Sperner理论是建立在偏序集上的极值理论,在运筹学、计算机、超图理论等领域有很多的应用。然而原始的Sperner定理对集合限制颇大。本文的主要工作是借助于数论的方法,给出Sperner定理在自然数域上推广的一个可选择的证明。将Sperner中集合与不定方程的解对应起来,把复杂的集合结构简化为解的结构,得到了良好的性质。推广中还运用对称链分解辅助说明,凭借架构对称链数量上的一一对应,证明了推广的部分。

Abstract: Sperner theory is one of the most marvelous branches in extremal set theory. It has many applica-tions in the field of operation research, computer science, hypergraph theory and so on. The original Sperner theorem is brilliant; however, there are quite a few constraints. Using number theory method, an alternative proof of Sperner theorem was obtained. As an application, we correspond subsets of Sperner to the roots of indefinite equations, simplifying the complex conformation of the set of solutions and getting nicer properties. The utilization of symmetric chain decomposition plays a great role in promotion, by establishing numerical correspondence between symmetric chain structure and integer collection. The symmetric chain decomposition method also supports the promotion. We build a connection between chains and collections.

文章引用: 张泰滺 , 晁福刚 , 任韩 (2015) Sperner理论的质因子分解问题。 应用数学进展, 4, 357-364. doi: 10.12677/AAM.2015.44044


[1] Sperner, E. (1928) Ein Satz über Untermengen einer endlichen menge. Mathematische Zeitschrift, 27, 544-548.

[2] Dilworth, R.P. (1950) A Decomposition Theorem for Partially Or-dered Sets. Annals of Mathematics, 51, 161-166.

[3] Katona, G. (1975) Extremal Problems for Hypergraphs. In: Hall Jr., M. and van Lint, J.H., Eds., Combinatorics.

[4] Kleitman, D.J. and Sperner, J. (1973) Families of k-Independent Sets. Discrete mathematics, 6, 255-262.

[5] de Bruijn, N.G., van Ebbenhorst Tengbergen, C. and Kruyswijk, D. (1949) On the Set of Divisors of a Number. Nieuw Archief voor Wiskunde, 23, 191-193.

[6] Erdös, P., Ko, C. and Rado, R. (1961) Extremal Problems among Subsets of a Set. Quarterly Journal of Mathematics Oxford Se-ries, 12, 313-318.

[7] Greene, C., Katona, G. and Kleitman, D.J. (1976) Extensions of the EKR Theorem. Studies in Applied Mathematics, 55, 1-8.

[8] Lih, K.W. (1987) Problems in Finite Extremal Set Theory. Surikaisekikenkyusho-Kokyuroku, 607, 1-4.