Entropy compression versus Lovasz Local Lemma

被引：2
作者：
Alves, Rogerio G. [1 ]
Procacci, Aldo [2 ]
Sanchis, Remy [2 ]
机构：
[1] Univ Fed Ouro Preto, Dept Matemat, BR-35400000 Ouro Preto, MG, Brazil
[2] Univ Fed Minas Gerais, Dept Matemat, BR-30161970 Belo Horizonte, MG, Brazil
来源：
ADVANCES IN APPLIED MATHEMATICS | 2021年 / 125卷
关键词：
Probabilistic method in combinatorics; Lovasz Local Lemma; Randomized algorithms;
D O I：
10.1016/j.aam.2021.102163
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In the framework of the probabilistic method in combinatorics, we provide a systematization of the entropy compression method clarifying the setting in which it can be applied and providing a theorem yielding a general constructive criterion. We finally elucidate, through topical examples, the effectiveness of the entropy-compression criterion in comparison with the Lovasz Local Lemma criterion and, in particular, with the improved criterion based on cluster expansion. (C) 2021 Elsevier Inc. All rights reserved.
引用
收藏
页数：32
相关论文
共 42 条
[1]   Beyond the Lovasz Local Lemma: Point to Set Correlations and Their Algorithmic Applications [J].
Achlioptas, Dimitris ;
Iliopoulos, Fotis ;
Sinclair, Alistair .
2019 IEEE 60TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2019), 2019, :725-744
[2]   THE LINEAR ARBORICITY OF GRAPHS [J].
ALON, N .
ISRAEL JOURNAL OF MATHEMATICS, 1988, 62 (03) :311-325
[3]   A PARALLEL ALGORITHMIC VERSION OF THE LOCAL LEMMA [J].
ALON, N .
RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (04) :367-378
[4]   ACYCLIC COLORING OF GRAPHS [J].
ALON, N ;
MCDIARMID, C ;
REED, B .
RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (03) :277-288
[5]   AN ALGORITHMIC APPROACH TO THE LOVASZ LOCAL LEMMA .1. [J].
BECK, J .
RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (04) :343-365
[6]   The Local Cut Lemma [J].
Bernshteyn, Anton .
EUROPEAN JOURNAL OF COMBINATORICS, 2017, 63 :95-114
[7]  
Bissacot R, 2011, COMB PROBAB COMPUT, V20, P709, DOI [10.1017/S096354831100025, 10.1017/S0963548311000253]
[8]   Properly coloured copies and rainbow copies of large graphs with small maximum degree [J].
Boettcher, Julia ;
Kohayakawa, Yoshiharu ;
Procacci, Aldo .
RANDOM STRUCTURES & ALGORITHMS, 2012, 40 (04) :425-436
[9]   Improved upper bound for the degenerate and star chromatic numbers of graphs [J].
Cai, Jiansheng ;
Li, Xueliang ;
Yan, Guiying .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 34 (02) :441-452
[10]  
Camungol Serina, 2016, Involve: A Journal of Mathematics, V9, P657
12345