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

Abstract | References | Similar Articles | Additional Information

Abstract:

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


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
Email: jkahn@math.rutgers.edu

DOI: http://dx.doi.org/10.1090/S0002-9939-01-06058-0
PII: S 0002-9939(01)06058-0
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