TOPICS
Search

Antichain


Let P be a finite partially ordered set, then an antichain in P is a set of pairwise incomparable elements. Antichains are also called Sperner systems in older literature (Comtet 1974).

For example, consider P to be a family of subsets together with the subset relation (i.e., s_1<=s_2 if s_1 is a subset of s_2). The following table gives the antichains on the set of subsets (i.e., the power set) of the n-set {1,2,3,...,n} for small n.

nantichains
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}}

The number of antichains on the n-set {1,2,...,n} for n=0, 1, 2, ..., are 1, 2, 5, 19, 167, ... (OEIS A014466). If the empty set is not considered a valid antichain, then these reduce to 0, 1, 4, 18, 166, ... (OEIS A007153; Comtet 1974, p. 273).

The number of antichains on the n-set are equal to the number of monotonic increasing Boolean functions of n variables, and also the number of free distributive lattices with n generators (Comtet 1974, p. 273). Determining these numbers is known as Dedekind's problem, and their values for n=0, 1, ... are called Dedekind numbers (Jäkel 2023), though they are conventionally defined as the numbers obtained by adding one to OEIS A014466, i.e., 2, 3, 6, 20, 168, 7581, 7828354, ... (OEIS A000372; Speciner 1972).

The partial order width of P is the maximum cardinal number of an antichain in P. For a partial order, the size of the longest antichain is called the partial order width w(P). Sperner (1928) proved that the maximum size (and hence the width of the partial order) of an antichain containing n elements is

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

where (n; k) is a binomial coefficient and |_n_| is the floor function.


See also

Boolean Function, Chain, Dedekind Number, Dedekind's Problem, Dilworth's Lemma, Partial Order Width, Partially Ordered Set

Explore with Wolfram|Alpha

References

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 and 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.

Referenced on Wolfram|Alpha

Antichain

Cite this as:

Weisstein, Eric W. "Antichain." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Antichain.html

Subject classifications