Independent sets in the middle two layers of Boolean lattice

被引：10

作者：

Balogh, Jozsef ^{[1
,2
]}

Garcia, Ramon, I ^{[1
]}

Li, Lina ^{[1
]}

机构：

[1] Univ Illinois, Dept Math, Urbana, IL 61801 USA

[2] Moscow Inst Phys & Technol, Moscow, Russia

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES A | 2021年 / 178卷

关键词：

Boolean lattice; Cluster expansion; Graph container method; Independent set; HARD-CORE MODEL; CLUSTER-EXPANSION; NUMBER;

D O I：

10.1016/j.jcta.2020.105341

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

For an odd integer n = 2d - 1, let 13(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 13(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. (C) 2020 Elsevier Inc. All rights reserved.

引用

页数：24

共 23 条

[1] Applications of Graph Containers in the Boolean Lattice [J].

Balogh, Jozsef ;

Treglown, Andrew ;

Wagner, Adam Zsolt .

RANDOM STRUCTURES & ALGORITHMS, 2016, 49 (04) :845-872

[2] Independent sets, matchings, and occupancy fractions [J].

Davies, Ewan ;

Jenssen, Matthew ;

Perkins, Will ;

Roberts, Barnaby .

JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 2017, 96 :47-66

[3] Maximal independent sets in bipartite graphs obtained from Boolean lattices [J].

Duffus, Dwight ;

Frankl, Peter ;

Roedl, Vojtech .

EUROPEAN JOURNAL OF COMBINATORICS, 2011, 32 (01) :1-9

[4] H-coloring tori [J].

Engbers, John ;

Galvin, David .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2012, 102 (05) :1110-1133

[5] Cluster expansion for abstract polymer models.: New bounds from an old approach [J].

Fernandez, Roberto ;

Procacci, Aldo .

COMMUNICATIONS IN MATHEMATICAL PHYSICS, 2007, 274 (01) :123-140

[6]

Friedli S, 2017, Statistical mechanics of lattice systems: aconcrete mathematical introduction

[7] On homomorphisms from the Hamming cube to Z [J].

Galvin, D .

ISRAEL JOURNAL OF MATHEMATICS, 2003, 138 (1) :189-213

[8]

GALVIN D, 2019, ARXIV190101991

[9] Slow mixing of Glauber dynamics for the hard-core model on regular bipartite graphs [J].

Galvin, David ;

Tetali, Prasad .

RANDOM STRUCTURES & ALGORITHMS, 2006, 28 (04) :427-443

[10] A Threshold Phenomenon for Random Independent Sets in the Discrete Hypercube [J].

Galvin, David .

COMBINATORICS PROBABILITY & COMPUTING, 2011, 20 (01) :27-51

← 1 2 3 →