Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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 Free Access

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?)


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

DOI: http://dx.doi.org/10.1090/S0002-9947-1975-0382107-0
PII: S 0002-9947(1975)0382107-0
Keywords: Dedekind's problem, Boolean functions, free distributive lattices
Article copyright: © Copyright 1975 American Mathematical Society