Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
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

PII: S 0002-9947(1975)0382107-0
Keywords: Dedekind's problem, Boolean functions, free distributive lattices
Article copyright: © Copyright 1975 American Mathematical Society

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia