Publication Date:
2019
Description:
〈p〉Publication date: 7 September 2019〈/p〉
〈p〉〈b〉Source:〈/b〉 Advances in Mathematics, Volume 353〈/p〉
〈p〉Author(s): Anton Bernshteyn〈/p〉
〈h5〉Abstract〈/h5〉
〈div〉〈p〉In this paper we investigate the extent to which the Lovász Local Lemma (an important tool in probabilistic combinatorics) can be adapted for the measurable setting. In most applications, the Lovász Local Lemma is used to produce a function 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.svg"〉〈mi〉f〈/mi〉〈mo〉:〈/mo〉〈mi〉X〈/mi〉〈mo stretchy="false"〉→〈/mo〉〈mi〉Y〈/mi〉〈/math〉 with certain properties, where 〈em〉X〈/em〉 is some underlying combinatorial structure and 〈em〉Y〈/em〉 is a (typically finite) set. Can this function 〈em〉f〈/em〉 be chosen to be Borel or 〈em〉μ〈/em〉-measurable for some probability Borel measure 〈em〉μ〈/em〉 on 〈em〉X〈/em〉 (assuming that 〈em〉X〈/em〉 is a standard Borel space)? In the positive direction, we prove that if the set of constraints put on 〈em〉f〈/em〉 is, in a certain sense, “locally finite,” then there is always a Borel choice for 〈em〉f〈/em〉 that is “〈em〉ε〈/em〉-close” to satisfying these constraints, for any 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si2.svg"〉〈mi〉ε〈/mi〉〈mo linebreak="goodbreak" linebreakstyle="after"〉〉〈/mo〉〈mn〉0〈/mn〉〈/math〉. Moreover, if the combinatorial structure on 〈em〉X〈/em〉 is “induced” by the 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si3.svg"〉〈mo stretchy="false"〉[〈/mo〉〈mn〉0〈/mn〉〈mo〉;〈/mo〉〈mn〉1〈/mn〉〈mo stretchy="false"〉]〈/mo〉〈/math〉-shift action of a countable group Γ, then, even without any local finiteness assumptions, there is a Borel choice for 〈em〉f〈/em〉 which satisfies the constraints on an invariant conull set (i.e., with 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si4.svg"〉〈mi〉ε〈/mi〉〈mo linebreak="goodbreak" linebreakstyle="after"〉=〈/mo〉〈mn〉0〈/mn〉〈/math〉). A direct corollary of our results is an upper bound on the measurable chromatic number of the graph 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1206.svg"〉〈msub〉〈mrow〉〈mi〉G〈/mi〉〈/mrow〉〈mrow〉〈mi〉n〈/mi〉〈/mrow〉〈/msub〉〈/math〉 generated by the shift action of the free group 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si6.svg"〉〈msub〉〈mrow〉〈mi mathvariant="double-struck"〉F〈/mi〉〈/mrow〉〈mrow〉〈mi〉n〈/mi〉〈/mrow〉〈/msub〉〈/math〉 that is asymptotically tight up to a factor of at most 2 (which answers a question of Lyons and Nazarov). On the other hand, our result for structures induced by measure-preserving group actions is, at least for amenable groups, sharp in the following sense: a probability measure-preserving action of a countably infinite amenable group satisfies the measurable version of the Lovász Local Lemma if and only if it admits a factor map to the 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si3.svg"〉〈mo stretchy="false"〉[〈/mo〉〈mn〉0〈/mn〉〈mo〉;〈/mo〉〈mn〉1〈/mn〉〈mo stretchy="false"〉]〈/mo〉〈/math〉-shift action. To prove this, we combine the tools of the Ornstein–Weiss theory of entropy for actions of amenable groups with concepts from computability theory, specifically, Kolmogorov complexity.〈/p〉〈/div〉
Print ISSN:
0001-8708
Electronic ISSN:
1090-2082
Topics:
Mathematics
Permalink