A constructive proof of the general lovász local lemma
From MaRDI portal
Publication:3578191
DOI10.1145/1667053.1667060zbMath1300.60024arXiv0903.0544OpenAlexW2109693504WikidataQ124802019 ScholiaQ124802019MaRDI QIDQ3578191
Publication date: 14 July 2010
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0903.0544
Nonnumerical algorithms (68W05) Combinatorial probability (60C05) Graph algorithms (graph-theoretic aspects) (05C85) Extremal combinatorics (05D99)
Related Items (only showing first 100 items - show all)
On a combinatorial framework for fault characterization ⋮ Algorithms for Constructing Anonymizing Arrays ⋮ \((1, j)\)-set problem in graphs ⋮ New bounds for the acyclic chromatic index ⋮ On Conflict-Free Multi-coloring ⋮ The list chromatic number of graphs with small clique number ⋮ A Probabilistic Approach to Reducing Algebraic Complexity of Delaunay Triangulations ⋮ Graph theory -- a survey on the occasion of the Abel Prize for László Lovász ⋮ Commutativity in the Algorithmic Lovász Local Lemma ⋮ A note on near-optimal coloring of shift hypergraphs ⋮ Rainbow Hamilton cycles and lopsidependency ⋮ Probabilistic existence of regular combinatorial structures ⋮ Covering metric spaces by few trees ⋮ Counting Candy Crush configurations ⋮ Partial Resampling to Approximate Covering Integer Programs ⋮ DELAUNAY STABILITY VIA PERTURBATIONS ⋮ Improved upper bound for the degenerate and star chromatic numbers of graphs ⋮ A Short Implicant of a CNF Formula with Many Satisfying Assignments ⋮ A General Framework for Hypergraph Coloring ⋮ Bisecting and \(D\)-secting families for set systems ⋮ Bandwidth and low dimensional embedding ⋮ Counting Solutions to Random CNF Formulas ⋮ Edge-partitioning 3-edge-connected graphs into paths ⋮ Graphs with $\chi=\Delta$ Have Big Cliques ⋮ Acyclic coloring of graphs without bichromatic long path ⋮ What can be sampled locally? ⋮ Application of entropy compression in pattern avoidance ⋮ Improved bounds on coloring of graphs ⋮ Total functions in QMA ⋮ Probabilistic existence of large sets of designs ⋮ Another approach to non-repetitive colorings of graphs of bounded degree ⋮ Unnamed Item ⋮ A new bound on the acyclic edge chromatic number ⋮ Expander spanning subgraphs with large girth ⋮ On the paper of Pascal Schweitzer concerning similarities between incompressibility methods and the Lovász local lemma ⋮ Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022 ⋮ Moser-Tardos resampling algorithm, entropy compression method and the subset gas ⋮ Unnamed Item ⋮ THE LOGARITHMICALLY AVERAGED CHOWLA AND ELLIOTT CONJECTURES FOR TWO-POINT CORRELATIONS ⋮ New bounds for the Moser‐Tardos distribution ⋮ Equivariant maps to subshifts whose points have small stabilizers ⋮ A rainbow blow‐up lemma ⋮ Acyclic edge-coloring using entropy compression ⋮ Colouring graphs when the number of colours is almost the maximum degree ⋮ Progress on the Adjacent Vertex Distinguishing Edge Coloring Conjecture ⋮ Colorful strips ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Generalized arboricity of graphs with large girth ⋮ A note on the discrepancy of matrices with bounded row and column sums ⋮ On weak odd domination and graph-based quantum secret sharing ⋮ Generating square-free words efficiently ⋮ Asymptotic and constructive methods for covering perfect hash families and covering arrays ⋮ The Lovász local lemma and variable strength covering arrays ⋮ Generalized acyclic edge colorings via entropy compression ⋮ Towards the linear arboricity conjecture ⋮ Pathwidth and nonrepetitive list coloring ⋮ Hölder-type inequalities and their applications to concentration and correlation bounds ⋮ Abstract polymer gas: a simple inductive proof of the Fernández-Procacci criterion ⋮ Acyclic edge coloring through the Lovász local lemma ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ New approach to nonrepetitive sequences ⋮ An asymptotically tight bound on the adaptable chromatic number ⋮ Improved Bounds for Centered Colorings ⋮ Nonrepetitive colouring via entropy compression ⋮ A Kolmogorov complexity proof of the Lovász local lemma for satisfiability ⋮ Asymptotically optimal frugal colouring ⋮ An upper bound for the choice number of star edge coloring of graphs ⋮ Reliable communication over highly connected noisy networks ⋮ Compressibility and probabilistic proofs ⋮ Entropy compression versus Lovász local lemma ⋮ Partial covering arrays: algorithms and asymptotics ⋮ Equitable orientations of sparse uniform hypergraphs ⋮ A short implicant of a CNF formula with many satisfying assignments ⋮ Low-weight superimposed codes and related combinatorial structures: bounds and applications ⋮ Pattern avoidance in partial words over a ternary alphabet ⋮ An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles ⋮ Directed Lovász local lemma and Shearer's lemma ⋮ Coloring graphs without bichromatic cycles or paths ⋮ Acyclic coloring of graphs and entropy compression method ⋮ Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas ⋮ Ergodic theorems for the shift action and pointwise versions of the Abért-Weiss theorem ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ Bandwidth and Low Dimensional Embedding ⋮ Covering Metric Spaces by Few Trees ⋮ Acyclic edge colourings of graphs with large girth ⋮ Train tracks with gaps: applying the probabilistic method to trains ⋮ A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability ⋮ Small simplicial complexes with prescribed torsion in homology ⋮ An Improvement of the Lovász Local Lemma via Cluster Expansion ⋮ Finding independent transversals efficiently ⋮ Measurable versions of the Lovász local lemma and measurable graph colorings ⋮ New selectors and locally thin families with applications to multi-access channels supporting simultaneous transmissions ⋮ Upper bounds on the sizes of variable strength covering arrays using the Lovász local lemma ⋮ Comparison of two convergence criteria for the variable-assignment Lopsided Lovász Local Lemma ⋮ Implementations and the independent set polynomial below the Shearer threshold ⋮ How to play Thue games ⋮ On Baire measurable colorings of group actions ⋮ Distributed coloring algorithms for triangle-free graphs ⋮ Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs ⋮ The local cut lemma
This page was built for publication: A constructive proof of the general lovász local lemma
