On Dedekind’s problem: the number of isotone Boolean functions. II

Kleitman, D.; Markowsky, G.

doi:10.1090/S0002-9947-1975-0382107-0

On Dedekind’s problem: the number of isotone Boolean functions. II
HTML articles powered by AMS MathViewer

by D. Kleitman and G. Markowsky

Trans. Amer. Math. Soc. 213 (1975), 373-390

DOI: https://doi.org/10.1090/S0002-9947-1975-0382107-0

PDF | Request permission

Abstract:

It is shown that $\psi (n)$, the size of the free distributive lattice on n generators (which is the number of isotone Boolean functions on subsets of an n element set), satisfies \[ \psi (n) \leqslant {2^{(1 + O(\log \;n/n))\left ( {\begin {array}{*{20}{c}} n \\ {[n/2]} \\ \end {array} } \right )}}.\] This result is an improvement by a factor $\sqrt n$ in the 0 term of a previous result of Kleitman. In the course of deriving the main result, we analyze thoroughly the techniques used here and earlier by Kleitman, and show that the result in this paper is “best possible” (up to constant) using these techniques.

References

William Feller, An introduction to probability theory and its applications. Vol. I, John Wiley & Sons, Inc., New York; Chapman & Hall, Ltd., London, 1957. 2nd ed. MR 0088081

Strong versions of Sperner’s theorem

Georges Hansel, Sur le nombre des fonctions booléennes monotones de $n$ variables, C. R. Acad. Sci. Paris Sér. A-B 262 (1966), A1088–A1090 (French). MR 224395
Daniel Kleitman, On Dedekind’s problem: The number of monotone Boolean functions, Proc. Amer. Math. Soc. 21 (1969), 677–682. MR 241334, DOI 10.1090/S0002-9939-1969-0241334-6
Donald E. Knuth, The asymptotic number of geometries, J. Combinatorial Theory Ser. A 16 (1974), 398–400. MR 335312, DOI 10.1016/0097-3165(74)90063-6

Combinatorial aspects of lattice theory with applications to the enumeration of free distributive lattices