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

Research output: Contribution to journalArticlepeer-review

43 Scopus citations

Abstract

For n-regular, N-vertex bipartite graphs with bipartition A ∪ B, a precise bound is given for the sum over independent sets I of the quantity μ|I∩A|λ|I∩B|. (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.

Original languageEnglish (US)
Pages (from-to)371-378
Number of pages8
JournalProceedings of the American Mathematical Society
Volume130
Issue number2
DOIs
StatePublished - 2002

All Science Journal Classification (ASJC) codes

  • General Mathematics
  • Applied Mathematics

Keywords

  • Antichain
  • Dedekind's Problem
  • Entropy
  • Independent set

Fingerprint

Dive into the research topics of 'Entropy, independent sets and antichains: A new approach to dedekind's problem'. Together they form a unique fingerprint.

Cite this