Moser-Tardos resampling algorithm, entropy compression method and the subset gas

DOI10.4171/AIHPD/122MaRDI QIDQ2693173zbMATH OpenFDO

Authors Paula Mendes Soares Fialho, Aldo Procacci, 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

zbMATH Keywords

abstract polymer systementropy compressionLovász local lemmaMoser-Tardos algorithmsubset gas

Mathematics Subject Classification ID

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)

Recommendations

• An extension of the Moser-Tardos algorithmic local lemma
• Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas
• Entropy compression versus Lovász local lemma
• Moser and tardos meet Lovász
• The Moser--Tardos Framework with Partial Resampling

Cites work

• 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

Cited in

(3)

• The Moser-Tardos Resample algorithm: Where is the limit? (an experimental inquiry)
• Moser-Tardos resampling algorithm, entropy compression method and the subset gas
• A linear-time algorithm for (1+)-edge-coloring

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)