Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Entropy, independent sets and antichains: A new approach to Dedekind's problem

Author: Jeff Kahn
Journal: Proc. Amer. Math. Soc. 130 (2002), 371-378
MSC (1991): Primary 05A16, 05C99, 06A07, 06D99, 94A17
Published electronically: June 8, 2001
MathSciNet review: 1862115
Full-text PDF

Abstract | References | Similar Articles | Additional Information


For $n$-regular, $N$-vertex bipartite graphs with bipartition $A\cup B$, a precise bound is given for the sum over independent sets $I$ of the quantity $\mu^{\vert I\cap A\vert}\lambda^{\vert I\cap B\vert}$. (In other language, this is bounding the partition function for certain instances of the hard-core model.) This result is then extended to graded partially ordered sets, which in particular provides a simple proof of a well-known bound for Dedekind's Problem given by Kleitman and Markowsky in 1975.

References [Enhancements On Off] (What's this?)

  • 1. N. Alon, Independent sets in regular graphs and sum-free subsets of finite groups, Israel J. Math. 73 (1991), 247-256. MR 92k:11024
  • 2. B. Bollobás, Modern Graph Theory, Springer, New York, 1998. MR 99h:05001
  • 3. F.R.K. Chung, P. Frankl, R. Graham and J.B. Shearer, Some intersection theorems for ordered sets and graphs, J. Combinatorial Th. Ser. A. 43 (1986), 23-37. MR 87k:05002
  • 4. R. Church, Numerical analysis of certain free distributive structures, Duke Math. J. 6 (1940), 732-734.
  • 5. I. Csiszár and J. Körner, Information theory. Coding theorems for discrete memoryless systems. Akadémiai Kiadó, Budapest, 1981. MR 98k:94003; MR 84e:94007
  • 6. R. Dedekind, Ueber Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler, Festschrift Hoch. Braunschweig u. ges. Werke, II (1897), 103-148.
  • 7. E.N. Gilbert, Lattice theoretic properties of frontal switching functions, J. Math. Phys. 33 (1954), 57-67. MR 15:1009e
  • 8. G. Hansel, Sur le nombre des fonctions booléennes monotones de $n$ variables, C.R. Acad. Sci. Paris 262 (1966), 1088-1090. MR 36:7439
  • 9. J. Kahn, An entropy approach to the hard-core model on bipartite graphs, Combinatorics, Probability & Computing, to appear.
  • 10. J. Kahn and A. Lawrenz, Generalized rank functions and an entropy argument, J. Combinatorial Th. Ser. A. 87 (1999), 398-403. MR 2000f:05009
  • 11. D. Kleitman, On Dedekind's problem: the number of isotone Boolean functions, Proc. Amer. Math. Soc. 21 (1969), 677-682. MR 39:2674
  • 12. D. Kleitman and G. Markowsky, On Dedekind's problem: the number of isotone Boolean functions. II, Trans. Amer. Math. Soc. 213 (1975), 373-390. MR 52:2995
  • 13. B.K. Korobkov, Monotone functions of the algebra of logic (Russian), Problemy Kibernet. 13 (1965) 5-28. MR 34:8885
  • 14. A.D. Korshunov, The number of monotone boolean functions (Russian), Problemy Kibernet. 38 (1981), 5-108. MR 83h:06013
  • 15. R.J. McEliece, The Theory of Information and Coding, Addison-Wesley, London, 1977. MR 57:9301
  • 16. A.A. Sapozhenko, The number of antichains in multilayered ranked sets (Russian), Diskret. Mat. 1 (1989), 110-128; translation in Discrete Math. Appl. 1 (1991), 149-169. MR 91k:06008
  • 17. W.T. Trotter, Combinatorics and Partially Ordered Sets, Johns Hopkins, Baltimore, 1992. MR 94a:06001
  • 18. M. Ward, Note on the order of free distributive lattices, Abstract 135, Bull. Amer. Math. Soc. 52 (1946), 423.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (1991): 05A16, 05C99, 06A07, 06D99, 94A17

Retrieve articles in all journals with MSC (1991): 05A16, 05C99, 06A07, 06D99, 94A17

Additional Information

Jeff Kahn
Affiliation: Department of Mathematics and RUTCOR, Rutgers University, New Brunswick, New Jersey 08903

Keywords: Entropy, independent set, antichain, Dedekind's Problem
Received by editor(s): June 23, 2000
Received by editor(s) in revised form: July 17, 2000
Published electronically: June 8, 2001
Additional Notes: The author was supported by the NSF
Communicated by: John R. Stembridge
Article copyright: © Copyright 2001 American Mathematical Society

American Mathematical Society