The number of maximal independent sets in the Hamming cube

DOI10.1007/S00493-021-4729-9arXiv1909.04283MaRDI QIDQ6324993FDOQ6324993

Authors: J. Kahn, Jinyoung Park 

Publication date: 10 September 2019

Abstract: Let $Q_n$ be the $n$-dimensional Hamming cube and $N=2^n$. We prove that the number of maximal independent sets in $Q_n$ is asymptotically [2n2^{N/4},] as was conjectured by Ilinca and the first author in connection with a question of Duffus, Frankl and R"odl. The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof that it is also an upper bound draws on various tools, among them "stability" results for maximal independent set counts and old and new results on isoperimetric behavior in $Q_n$.

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

This page was built for publication: The number of maximal independent sets in the Hamming cube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6324993)