Moser-Tardos resampling algorithm, entropy compression method and the subset gas
From MaRDI portal
Publication:2693173
DOI10.4171/AIHPD/122MaRDI QIDQ2693173
Aldo Procacci, Paula Mendes Soares Fialho, Bernardo Nunes Borges de Lima
Publication date: 17 March 2023
Published in: Annales de l'Institut Henri Poincaré D. Combinatorics, Physics and their Interactions (AIHPD) (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2001.00880
Combinatorial probability (60C05) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Coloring of graphs and hypergraphs (05C15) Randomized algorithms (68W20) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the facial Thue choice number of plane graphs via entropy compression method
- A note on acyclic vertex-colorings
- Application of entropy compression in pattern avoidance
- Acyclic edge coloring through the Lovász local lemma
- Nonrepetitive colouring via entropy compression
- Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas
- Improved algorithms for colorings of simple hypergraphs and applications
- On the convergence of cluster expansions for polymer gases
- On a problem of Spencer
- Cluster expansion for abstract polymer models
- Perfect and separating hash families: new bounds via the algorithmic cluster expansion local lemma
- Generalized arboricity of graphs with large girth
- Abstract polymer gas: a simple inductive proof of the Fernández-Procacci criterion
- A new bound on the acyclic edge chromatic number
- The local cut lemma
- Improved upper bound for the degenerate and star chromatic numbers of graphs
- Acyclic edge-coloring using entropy compression
- Cluster expansion for abstract polymer models. New bounds from an old approach
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- Avoiding approximate repetitions with respect to the longest common subsequence distance
- Properly coloured copies and rainbow copies of large graphs with small maximum degree
- On the Facial Thue Choice Index via Entropy Compression
- An Improvement of the Lovász Local Lemma via Cluster Expansion
- Random Walks That Find Perfect Objects and the Lovász Local Lemma
- An Extension of the Moser--Tardos Algorithmic Local Lemma
- A constructive proof of the general lovász local lemma
- An algorithmic approach to the Lovász local lemma. I
- A parallel algorithmic version of the local lemma
- Commutativity in the Algorithmic Lovász Local Lemma
- New approach to nonrepetitive sequences
- An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles
- Oblivious resampling oracles and parallel algorithms for the Lopsided Lovász Local Lemma
- A Local Lemma for Focused Stochastic Algorithms
- Asymptotic Size of Covering Arrays: An Application of Entropy Compression
- Moser and tardos meet Lovász
