Moser-Tardos resampling algorithm, entropy compression method and the subset gas
Coloring of graphs and hypergraphs (05C15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorial probability (60C05) Randomized algorithms (68W20) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)
Summary: We establish a connection between the entropy compression method and the Moser-Tardos algorithmic version of the Lovász local lemma through the cluster expansion of the subset gas. We also show that the Moser-Tardos resampling algorithm and the entropy compression bactracking algorithm produce identical bounds.
- A constructive Lovász local lemma for permutations
- A constructive proof of the general Lovász local lemma
- A local lemma for focused stochastic algorithms
- A new bound on the acyclic edge chromatic number
- A note on acyclic vertex-colorings
- A parallel algorithmic version of the local lemma
- Abstract polymer gas: a simple inductive proof of the Fernández-Procacci criterion
- Acyclic edge coloring through the Lovász local lemma
- Acyclic edge-coloring using entropy compression
- An algorithmic approach to the Lovász local lemma. I
- An algorithmic proof of the Lovász local lemma via resampling oracles
- An extension of the Moser-Tardos algorithmic local lemma
- An improvement of the Lovász local lemma via cluster expansion
- Analytic combinatorics
- Application of entropy compression in pattern avoidance
- Asymptotic size of covering arrays: an application of entropy compression
- Avoiding approximate repetitions with respect to the longest common subsequence distance
- Cluster expansion for abstract polymer models
- Cluster expansion for abstract polymer models. New bounds from an old approach
- Commutativity in the Algorithmic Lovász Local Lemma
- Generalized arboricity of graphs with large girth
- scientific article; zbMATH DE number 991497 (Why is no real title available?)
- scientific article; zbMATH DE number 3854171 (Why is no real title available?)
- scientific article; zbMATH DE number 3492718 (Why is no real title available?)
- scientific article; zbMATH DE number 2232270 (Why is no real title available?)
- Improved algorithms for colorings of simple hypergraphs and applications
- Improved upper bound for the degenerate and star chromatic numbers of graphs
- Moser and tardos meet Lovász
- New approach to nonrepetitive sequences
- Nonrepetitive colouring via entropy compression
- Oblivious resampling oracles and parallel algorithms for the Lopsided Lovász Local Lemma
- On a problem of Spencer
- On the convergence of cluster expansions for polymer gases
- On the facial Thue choice index via entropy compression
- On the facial Thue choice number of plane graphs via entropy compression method
- Perfect and separating hash families: new bounds via the algorithmic cluster expansion local lemma
- Properly coloured copies and rainbow copies of large graphs with small maximum degree
- Random walks that find perfect objects and the Lovász local lemma
- The local cut lemma
- The probabilistic method
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas
This page was built for publication: Moser-Tardos resampling algorithm, entropy compression method and the subset gas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2693173)
