Measurable versions of the Lovász local lemma and measurable graph colorings

DOI10.1016/j.aim.2019.06.031zbMath1436.05110arXiv1604.07349OpenAlexW2963733075WikidataQ124878808 ScholiaQ124878808MaRDI QIDQ2319876

Anton Bernshteyn

Publication date: 20 August 2019

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1604.07349

zbMATH Keywords

graph coloringLovász local lemmameasurabledescriptive combinatorics

Mathematics Subject Classification ID

Applications of graph theory (05C90) Dynamical aspects of measure-preserving transformations (37A05) Probabilistic measure theory (60A10) Coloring of graphs and hypergraphs (05C15) General groups of measure-preserving transformations and dynamical systems (37A15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items

Factor-of-iid balanced orientation of non-amenable graphs ⋮ Definable Kőnig theorems ⋮ Distributed algorithms, the Lovász local lemma, and descriptive combinatorics ⋮ Measurable graph combinatorics ⋮ Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms ⋮ Borel fractional colorings of Schreier graphs ⋮ Extremal problems in hypergraph colourings ⋮ Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022 ⋮ Equivariant maps to subshifts whose points have small stabilizers ⋮ A short proof of Bernoulli disjointness via the local lemma ⋮ Minimal definable graphs of definable chromatic number at least three ⋮ Measurable versions of Vizing's theorem ⋮ Building large free subshifts using the Local Lemma ⋮ Ergodic theorems for the shift action and pointwise versions of the Abért-Weiss theorem ⋮ An announce of results linking Kolmogorov complexity to entropy for amenable group actions ⋮ On Baire measurable colorings of group actions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weak isomorphisms between Bernoulli shifts
• Perfect matchings as IID factors on non-amenable groups
• On large deviations for amenable group actions
• Lopsided Lovász Local lemma and Latin transversals
• Entropy and isomorphism theorems for actions of amenable groups
• On the independence and chromatic numbers of random regular graphs
• The Abramov-Rokhlin entropy addition formula for amenable group actions
• Asymptotic lower bounds for Ramsey functions
• Borel chromatic numbers
• The list chromatic number of graphs with small clique number
• Topics in orbit equivalence
• Measurable chromatic and independence numbers for ergodic graphs and group actions
• Hyperfiniteness and Borel combinatorics
• A bound on measurable chromatic numbers of locally finite Borel graphs
• A determinacy approach to Borel combinatorics
• Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma
• KŐNIG’S LINE COLORING AND VIZING’S THEOREMS FOR GRAPHINGS
• A constructive proof of the general lovász local lemma
• Acyclic coloring of graphs
• Kolmogorov Complexity and Algorithmic Randomness
• Nonrepetitive colorings of graphs
• On Brooks' Theorem for Sparse Graphs
• Improved bounds and algorithms for hypergraph 2-coloring
• Computable Følner monotilings and a theorem of Brudno
• Moser and tardos meet Lovász
• BROOKS’ THEOREM FOR MEASURABLE COLORINGS
• An introduction to Kolmogorov complexity and its applications
• Graph colouring and the probabilistic method