The Number of Maximal Independent Sets in the Hamming Cube

Jeff Kahn; Jinyoung Park

doi:10.1007/s00493-021-4729-9

The Number of Maximal Independent Sets in the Hamming Cube

Jeff Kahn, Jinyoung Park

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

Let Q_n be the n-dimensional Hamming cube and N = 2ⁿ. We prove that the number of maximal independent sets in Q_n is asymptotically 2 n2 ^N^/⁴, as was conjectured by Ilinca and the first author in connection with a question of Duffus, Frankl and Rödl. 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.

Original language	English (US)
Pages (from-to)	853-880
Number of pages	28
Journal	Combinatorica
Volume	42
Issue number	6
DOIs	https://doi.org/10.1007/s00493-021-4729-9
State	Published - Dec 2022
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s00493-021-4729-9

Cite this

@article{a8f69ee932f9423db1c43e3d269a1470,

title = "The Number of Maximal Independent Sets in the Hamming Cube",

abstract = "Let Qn be the n-dimensional Hamming cube and N = 2n. We prove that the number of maximal independent sets in Qn is asymptotically 2 n2 N/4, as was conjectured by Ilinca and the first author in connection with a question of Duffus, Frankl and R{\"o}dl. 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 Qn.",

author = "Jeff Kahn and Jinyoung Park",

note = "Funding Information: The authors are supported by NSF Grant DMS1501962 and BSF Grant 2014290. Publisher Copyright: {\textcopyright} 2022, J{\'a}nos Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.",

year = "2022",

month = dec,

doi = "10.1007/s00493-021-4729-9",

language = "English (US)",

volume = "42",

pages = "853--880",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "6",

}

TY - JOUR

T1 - The Number of Maximal Independent Sets in the Hamming Cube

AU - Kahn, Jeff

AU - Park, Jinyoung

PY - 2022/12

Y1 - 2022/12

N2 - Let Qn be the n-dimensional Hamming cube and N = 2n. We prove that the number of maximal independent sets in Qn is asymptotically 2 n2 N/4, as was conjectured by Ilinca and the first author in connection with a question of Duffus, Frankl and Rödl. 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 Qn.

AB - Let Qn be the n-dimensional Hamming cube and N = 2n. We prove that the number of maximal independent sets in Qn is asymptotically 2 n2 N/4, as was conjectured by Ilinca and the first author in connection with a question of Duffus, Frankl and Rödl. 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 Qn.

UR - http://www.scopus.com/inward/record.url?scp=85126222835&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85126222835&partnerID=8YFLogxK

U2 - 10.1007/s00493-021-4729-9

DO - 10.1007/s00493-021-4729-9

M3 - Article

AN - SCOPUS:85126222835

SN - 0209-9683

VL - 42

SP - 853

EP - 880

JO - Combinatorica

JF - Combinatorica

IS - 6

ER -

The Number of Maximal Independent Sets in the Hamming Cube

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this