Independent sets in the middle two layers of Boolean lattice

József Balogh; Ramon I. Garcia; Lina Li

doi:10.1016/j.jcta.2020.105341

Independent sets in the middle two layers of Boolean lattice

József Balogh, Ramon I. Garcia, Lina Li

Mathematics

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

Abstract

For an odd integer n=2d−1, let B(n,d) be the subgraph of the hypercube Q_n induced by the two largest layers. In this paper, we describe the typical structure of independent sets in B(n,d) and give precise asymptotics on the number of them. The proofs use Sapozhenko's graph container method and a recently developed method of Jenssen and Perkins, which combines Sapozhenko's graph container lemma with the cluster expansion for polymer models from statistical physics.

Original language	English (US)
Article number	105341
Journal	Journal of Combinatorial Theory. Series A
Volume	178
DOIs	https://doi.org/10.1016/j.jcta.2020.105341
State	Published - Feb 2021

Keywords

Boolean lattice
Cluster expansion
Graph container method
Independent set

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Online availability

10.1016/j.jcta.2020.105341

Library availability

Discover UIUC Full Text

Cite this

@article{c7ac4cda91e94a48ad30cdb7c6c72358,

title = "Independent sets in the middle two layers of Boolean lattice",

abstract = "For an odd integer n=2d−1, let B(n,d) be the subgraph of the hypercube Qn induced by the two largest layers. In this paper, we describe the typical structure of independent sets in B(n,d) and give precise asymptotics on the number of them. The proofs use Sapozhenko's graph container method and a recently developed method of Jenssen and Perkins, which combines Sapozhenko's graph container lemma with the cluster expansion for polymer models from statistical physics.",

keywords = "Boolean lattice, Cluster expansion, Graph container method, Independent set",

author = "J{\'o}zsef Balogh and Garcia, {Ramon I.} and Lina Li",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier Inc.",

year = "2021",

month = feb,

doi = "10.1016/j.jcta.2020.105341",

language = "English (US)",

volume = "178",

journal = "Journal of Combinatorial Theory. Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Independent sets in the middle two layers of Boolean lattice

AU - Balogh, József

AU - Garcia, Ramon I.

AU - Li, Lina

PY - 2021/2

Y1 - 2021/2

N2 - For an odd integer n=2d−1, let B(n,d) be the subgraph of the hypercube Qn induced by the two largest layers. In this paper, we describe the typical structure of independent sets in B(n,d) and give precise asymptotics on the number of them. The proofs use Sapozhenko's graph container method and a recently developed method of Jenssen and Perkins, which combines Sapozhenko's graph container lemma with the cluster expansion for polymer models from statistical physics.

AB - For an odd integer n=2d−1, let B(n,d) be the subgraph of the hypercube Qn induced by the two largest layers. In this paper, we describe the typical structure of independent sets in B(n,d) and give precise asymptotics on the number of them. The proofs use Sapozhenko's graph container method and a recently developed method of Jenssen and Perkins, which combines Sapozhenko's graph container lemma with the cluster expansion for polymer models from statistical physics.

KW - Boolean lattice

KW - Cluster expansion

KW - Graph container method

KW - Independent set

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

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

U2 - 10.1016/j.jcta.2020.105341

DO - 10.1016/j.jcta.2020.105341

M3 - Article

AN - SCOPUS:85091952491

SN - 0097-3165

VL - 178

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

M1 - 105341

ER -

Independent sets in the middle two layers of Boolean lattice

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this