The local cut lemma
From MaRDI portal
Abstract: The Lov'{a}sz Local Lemma is a very powerful tool in probabilistic combinatorics, that is often used to prove existence of combinatorial objects satisfying certain constraints. Moser and Tardos have shown that the LLL gives more than just pure existence results: there is an effective randomized algorithm that can be used to find a desired object. In order to analyze this algorithm, Moser and Tardos developed the so-called entropy compression method. It turned out that one could obtain better combinatorial results by a direct application of the entropy compression method rather than simply appealing to the LLL. The aim of this paper is to provide a generalization of the LLL which implies these new combinatorial results. This generalization, which we call the Local Cut Lemma, concerns a random cut in a directed graph with certain properties. Note that our result has a short probabilistic proof that does not use entropy compression. As a consequence, it not only shows that a certain probability is positive, but also gives an explicit lower bound for this probability. As an illustration, we present a new application (an improved lower bound on the number of edges in color-critical hypergraphs) as well as explain how to use the Local Cut Lemma to derive some of the results obtained previously using the entropy compression method.
Recommendations
Cites work
- A constructive proof of the general Lovász local lemma
- Acyclic coloring of graphs
- Acyclic colorings of planar graphs
- Acyclic edge colorings of graphs
- Acyclic edge-coloring using entropy compression
- An extension of the Moser-Tardos algorithmic local lemma
- An improvement of the Lovász local lemma via cluster expansion
- Deterministic algorithms for the Lovász local lemma
- scientific article; zbMATH DE number 53883 (Why is no real title available?)
- scientific article; zbMATH DE number 3492718 (Why is no real title available?)
- scientific article; zbMATH DE number 3603300 (Why is no real title available?)
- scientific article; zbMATH DE number 1775440 (Why is no real title available?)
- Improved bounds and algorithms for hypergraph 2-coloring
- Improved bounds on coloring of graphs
- Lopsided Lovász Local lemma and Latin transversals
- New approach to nonrepetitive sequences
- New bounds for the acyclic chromatic index
- Nonrepetitive colorings of graphs
- Nonrepetitive colorings of graphs -- a survey
- Nonrepetitive colouring via entropy compression
- Nonrepetitive list colourings of paths
- Nonrepetitive vertex colorings of graphs
- On the number of edges in colour-critical graphs and hypergraphs
- Sparse color‐critical graphs and hypergraphs with no short cycles
- Sparse colour-critical hypergraphs
- The asymptotic behavior of the correspondence chromatic number
Cited in
(21)- Using Lovász local lemma in the space of random injections
- The lonely runner problem for lacunary sequences
- The Lovász local lemma and its applications to some combinatorial arrays
- On the paper of Pascal Schweitzer concerning similarities between incompressibility methods and the Lovász local lemma
- Entropy compression versus Lovász local lemma
- Another approach to non-repetitive colorings of graphs of bounded degree
- The local loop lemma
- Cutting lemma and Zarankiewicz's problem in distal structures
- The asymptotic behavior of the correspondence chromatic number
- Moser-Tardos resampling algorithm, entropy compression method and the subset gas
- Quest for negative dependency graphs
- New bounds for the acyclic chromatic index
- A sharper local lemma with improved applications
- Random walks that find perfect objects and the Lovász local lemma
- An algorithmic proof of the Lovász local lemma via resampling oracles
- A general framework for hypergraph coloring
- Progress on the adjacent vertex distinguishing edge coloring conjecture
- Single‐conflict colouring
- Colorings, transversals, and local sparsity
- Graphs of low average degree without independent transversals
- On harmonious coloring of hypergraphs
This page was built for publication: The local cut lemma
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2357223)
