Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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

Authors: D. Kleitman and G. Markowsky
Journal: Trans. Amer. Math. Soc. 213 (1975), 373-390
MSC: Primary 06A35; Secondary 05A15
MathSciNet review: 0382107
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

$\displaystyle \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 [Enhancements On Off] (What's this?)

  • [1] W. K. Feller, An introduction to probability theory and its applications. Vol. I, Wiley, New York; Chapman & Hall, London, 1957. MR 19, 466. MR 0088081 (19:466a)
  • [2] C. Greene and D. J. Kleitman, Strong versions of Sperner's theorem, J. Combinatorial Theory (to appear).
  • [3] G. Hansel, Sur le nombres des fonctions booléennes monotones de n variables, C. R. Acad. Sci. Paris Sér. A-B 262 (1966), A1088-A1090. MR 36 #7439. MR 0224395 (36:7439)
  • [4] D. J. Kleitman, On Dedekind's problem: The number of monotone Boolean functions, Proc. Amer. Math. Soc. 21 (1969), 677-682. MR 39 #2674. MR 0241334 (39:2674)
  • [5] D. E. Knuth, The asymptotic number of geometries, Discrete Math. (to appear). MR 0335312 (49:94)
  • [6] G. Markowsky, Combinatorial aspects of lattice theory with applications to the enumeration of free distributive lattices, Ph. D. Thesis, Harvard University, 1973.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 06A35, 05A15

Retrieve articles in all journals with MSC: 06A35, 05A15

Additional Information

Keywords: Dedekind's problem, Boolean functions, free distributive lattices
Article copyright: © Copyright 1975 American Mathematical Society

American Mathematical Society