Counting Maximal Antichains and Independent Sets

L. Ilinca, J. Kahn

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

Answering several questions of Duffus, Frankl and Rödl, we give asymptotics for the logarithms of (i) the number of maximal antichains in the n-dimensional Boolean algebra and (ii) the numbers of maximal independent sets in the covering graph of the n-dimensional hypercube and certain natural subgraphs thereof. The results in (ii) are implied by more general upper bounds on the numbers of maximal independent sets in regular and biregular graphs. We also mention some stronger possibilities involving actual rather than logarithmic asymptotics.

Original languageEnglish (US)
Pages (from-to)427-435
Number of pages9
JournalOrder
Volume30
Issue number2
DOIs
StatePublished - Jul 2013

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Geometry and Topology
  • Computational Theory and Mathematics

Keywords

  • Asymptotic enumeration
  • Entropy
  • Maximal antichains
  • Maximal independent sets
  • Shearer's Lemma

Fingerprint Dive into the research topics of 'Counting Maximal Antichains and Independent Sets'. Together they form a unique fingerprint.

Cite this