The Number of Maximal Independent Sets in the Hamming Cube
The Number of Maximal Independent Sets in the Hamming Cube
复制标题
汉明立方中最大独立集的数量
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Jinyoung Park
中科院分区：
文献类型：
--
作者：
J. Kahn;Jinyoung Park
设Q_n是n维汉明立方体，N=2^n。本文证明了$Q_n$中极大独立集的个数是渐近的[2n ~ 2 ^{N/4}]，这是Ilinca和第一作者结合达夫斯、Frankl和Rodl的一个问题所证明的.
该值是从极大独立集和诱导匹配之间的连接导出的自然下界。证明它也是一个上限借鉴了各种工具，其中“稳定性”的结果，最大独立集计数和旧的和新的结果等周行为在$Q_n$。
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 Rodl.
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$.
影响因子：
1
作者：
Kahn, Jeff;Park, Jinyoung
通讯作者：
Park, Jinyoung