主题
Search

反链

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

令 P 为有限偏序集，则 P 中的反链是两两不可比较元素的集合。反链在较早的文献中也称为 Sperner 系统（Comtet 1974）。

例如，考虑 P 为子集族以及子集关系（即，s_1<=s_2 如果 s_1 是 s_2 的子集）。下表给出了 n-元集 {1,2,3,...,n} 的子集（即幂集）上的反链，对于小的 n。

n反链
1emptyset,{{1}}
2emptyset,{{1}},{{2}},{{1},{2}},{{1,2}}
3emptyset,{{1}},{{2}},{{3}},{{1,2}},
{{1,3}},{{2,3}},{{1},{2}},{{1},{3}},
{{2},{3}},{{1,2,3}},{{1},{2,3}},{{1,2},{2,3}},
{{1,2},{1,3}},{{1,2},{3}},{{2},{1,3}},
{{2,3},{1,3}},{{1},{2},{3}},{{1,2},{2,3},{1,3}}

对于 n=0, 1, 2, ...，n-元集 {1,2,...,n} 上的反链的数量是 1, 2, 5, 19, 167, ... (OEIS A014466)。如果空集不被认为是有效的反链，那么这些数字减少为 0, 1, 4, 18, 166, ... (OEIS A007153；Comtet 1974, p. 273)。

n-元集上的反链的数量等于 n 个变量的单调递增布尔函数的数量，也等于 n 个生成元的自由分配格的数量 (Comtet 1974, p. 273)。确定这些数字被称为 Dedekind 问题，并且它们对于 n=0, 1, ... 的值被称为 Dedekind 数 (Jäkel 2023)，尽管它们通常被定义为通过将 1 加到 OEIS A014466 获得的数字，即 2, 3, 6, 20, 168, 7581, 7828354, ... (OEIS A000372；Speciner 1972)。

P 的偏序宽度是 P 中反链的最大基数。对于偏序，最长反链的大小称为偏序宽度 w(P)。Sperner (1928) 证明了包含 n 个元素的反链的最大大小（以及因此偏序的宽度）是

w_(max(n))=(n; |_n/2_|),

其中 (n; k) 是二项式系数，|_n_| 是向下取整函数。

参见

布尔函数, 链, Dedekind 数, Dedekind 问题, Dilworth 引理, 偏序宽度, 偏序集

使用 探索

参考文献

Agnew, R. P. "Minimax Functions, Configuration Functions, and Partitions." J. Indian Math. Soc. 24, 1-21, 1961.Anderson, I. Combinatorics of Finite Sets. Oxford, England: Oxford University Press, p. 38, 1987.Arocha, J. L. "Antichains in Ordered Sets" [Spanish]. Anales del Instituto de Matematicas de la Universidad Nacional Autonoma de Mexico 27, 1-21, 1987.Berman, J. "Free Spectra of 3-Element Algebras." In Universal Algebra and Lattice Theory (Puebla, 1982) (Ed. R. S. Freese 和 O. C. Garcia). New York: Springer-Verlag, 1983.Berman, J. and Koehler, P. "Cardinalities of Finite Distributive Lattices." Mitteilungen aus dem Mathematischen Seminar Giessen 121, 103-124, 1976.Birkhoff, G. Lattice Theory, 3rd ed. Providence, RI: Amer. Math. Soc., p. 63, 1967.Church, R. "Numerical Analysis of Certain Free Distributive Structures." Duke Math. J. 6, 732-733, 1940.Church, R. "Enumeration by Rank of the Elements of the Free Distributive Lattice with Seven Generators." Not. Amer. Math. Soc. 12, 724, 1965.Comtet, L. "Sperner Systems." §7.2 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 271-273, 1974.Dedekind, R. "Über Zerlegungen von Zahlen durch ihre grössten gemeinsammen Teiler." In Gesammelte Werke, Bd. 1. (Ed. K. May). Heidelberg, Germany: Mohr Siebeck, pp. 103-148, 1897.Erdős, P.; Ko, Chao; and Rado, R. "Intersection Theorems for Systems of Finite Sets." Quart. J. Math. Oxford 12, 313-320, 1961.Gilbert, E. N. "Lattice Theoretic Properties of Frontal Switching Networks." J. Math. Phys. 33, 57-97, 1954.Hansel, G. "Problèmes de dénombrement et d'évaluation de bornes concernant les éléments du trellis distributif libre." Publ. Inst. Statist. Univ. Paris 16, 163-294, 1967.Harrison, M. A. Introduction to Switching and Automata Theory. New York: McGraw-Hill, p. 188, 1965.Hilton, A. J. W. and Milner, E. C. "Some Intersection Theorems of Systems of Finite Sets." Quart. J. Math. Oxford 18, 369-384, 1967.Jäkel, C. "A Computation of the Ninth Dedekind Number." 3 Apr 2023. https://arxiv.org/abs/2304.00895.Katona, G. "On a Conjecture of Erdős and a Stronger Form of Sperner's Theorem." Studia Sci. Math. Hung. 1, 59-63, 1966.Katona, G. "A Theorem of Finite Sets." In Theory of Graphs, Proceedings of the Colloquium Held at Tihany, Hungary, September 1966 (Ed. P. Erdős and G. Katona). New York: Academic Press, pp. 187-207, 1968.Kleitman, D. "A Conjecture of Erdős-Katona on Commensurable Pairs Among Subsets of a n-Set." In Theory of Graphs, Proceedings of the Colloquium Held at Tihany, Hungary, September 1966 (Ed. P. Erdős and G. Katona). New York: Academic Press, pp. 215-218, 1968.Kleitman, D. "On Dedekind's Problem: The Number of Monotone Boolean Functions." Proc. Amer. Math. Soc. 21, 677-682, 1969.Kleitman, D. and Markowsky, G. "On Dedekind's Problem: The Number of Isotone Boolean Functions. II." Trans. Amer. Math. Soc. 213, 373-390, 1975.Lunnon, W. F. "The IU Function: The Size of a Free Distributive Lattice." In Combinatorial Mathematics and Its Applications: Proceedings of a conference held at the Mathematical Institute, Oxford, from 7-10 July, 1969 (Ed. D. J. A. Welsh). New York: Academic Press, pp. 173-181, 1971.Mešalkin, L. D. "A Generalization of Sperner's Theorem on the Number of Subsets of a Finite Set." Theory Prob. 8, 203-204, 1963.Milner, E. C. "A Combinatorial Theorem on Systems of Sets." J. London Math. Soc. 43, 204-206, 1968.Muroga, S. Threshold Logic and Its Applications. New York: Wiley, p. 38 and 214, 1971.Rivière, N. M. "Recursive Formulas on Free Distributive Lattices." J. Combin. Th. 5, 229-234, 1968.Shapiro, H. N. "On the Counting Problem for Monotone Boolean Functions." Comm. Pure Appl. Math. 23, 299-312, 1970.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 241, 1990.Sloane, N. J. A. Sequences A006826/M2469, A007153/M3551, and A014466 in "The On-Line Encyclopedia of Integer Sequences."Speciner, M. Item 18 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, p. 10, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item18.Sperner, E. "Ein Satz über Untermengen einer endlichen Menge." Math. Z. 27, 544-548, 1928.Ward, M. "Note on the Order of the Free Distributive Lattice." Bull. Amer. Math. Soc. 52, 423, 1946.Yamamoto, K. "Logarithmic Order of Free Distributive Lattice." J. Math. Soc. Japan 6, 343-353, 1954.

在 上引用

反链

引用为

Weisstein, Eric W. "反链。" 来自 网络资源。 https://mathworld.net.cn/Antichain.html

主题分类