Liviu Ilinca, Jeff Kahn
Published 2012-02-20Version 1
Answering several questions of Duffus, Frankl and R\"odl, 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.
Maximal Independent Sets In Graphs With At Most r Cycles
Inverse problems for the number of maximal independent sets
On graphs having maximal independent sets of exactly $t$ distinct cardinalities
![QR code for arXiv:1202.4427 [math.CO]](http://oss.arxitics.com/images/favicon.svg)