Let be a finite partially
ordered set, then an antichain in is a set of pairwise incomparable elements. Antichains are
also called Sperner systems in older literature (Comtet 1974).
For example, consider
to be a family of subsets together with the subset relation (i.e., if is a subset of ). The following table gives the antichains on the set of
subsets (i.e., the power set) of the -set
for small .
antichains
1
2
3
The number of antichains on the -set
for , 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 -set are equal to the number of monotonic increasing Boolean
functions of
variables, and also the number of free distributive lattices with generators (Comtet 1974, p. 273). Determining these numbers
is known as Dedekind's problem, and their values
for , 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 is the maximum cardinal number
of an antichain in .
For a partial order, the size of the longest antichain
is called the partial order width. Sperner (1928) proved that the maximum size (and hence
the width of the partial order) of an antichain containing elements is
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 Mexico27, 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 Giessen121, 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. Oxford12, 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. Paris16, 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. Oxford18, 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 -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. Japan6,
343-353, 1954.
be a finite partially
ordered set, then an antichain in 
is a set of pairwise incomparable elements. Antichains are
also called Sperner systems in older literature (Comtet 1974).
to be a family of subsets together with the subset relation (i.e., 
if 
is a subset of 
). The following table gives the antichains on the set of
subsets (i.e., the power set) of the 
-set 
for small 
.
-set 
for 
, 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).
-set are equal to the number of monotonic increasing Boolean
functions of 
variables, and also the number of free distributive lattices with 
generators (Comtet 1974, p. 273). Determining these numbers
is known as Dedekind's problem, and their values
for 
, 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).
is the maximum cardinal number
of an antichain in 
.
For a partial order, the size of the longest antichain
is called the partial order width 
. Sperner (1928) proved that the maximum size (and hence
the width of the partial order) of an antichain containing 
elements is
is a binomial
coefficient and 
is the floor function.
-Set."
In