Borel fractional colorings of Schreier graphs

DOI10.5802/AHL.145arXiv2105.11557OpenAlexW3164867379MaRDI QIDQ6159728FDOQ6159728

Anton Bernshteyn

Publication date: 20 June 2023

Published in: Annales Henri Lebesgue (Search for Journal in Brave)

Abstract: Let $Gamma$ be a countable group and let $G$ be the Schreier graph of the free part of the Bernoulli shift of $Gamma$ (with respect to some finite subset $FsubseteqGamma$). We show that the Borel fractional chromatic number of $G$ is equal to $1$ over the measurable independence number of $G$. As a consequence, we asymptotically determine the Borel fractional chromatic number of $G$ when $Gamma$ is the free group, answering a question of Meehan.

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

zbMATH Keywords

group actionsymbolic dynamicsfractional coloringBorel setsSchreier graphBorel combinatorics

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Symbolic dynamics (37B10) Descriptive set theory (03E15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Bernoulli actions are weakly contained in any free action
• Ultraproducts of measure preserving actions and graph combinatorics
• Large independent sets in regular graphs of large girth
• Borel chromatic numbers
• Borel structurability on the 2-shift of a countable group
• A determinacy approach to Borel combinatorics
• Local algorithms for independent sets are half-optimal
• Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections
• Borel Combinatorics of Locally Finite Graphs
• Measurable versions of the Lovász local lemma and measurable graph colorings
• Invariant Schreier decorations of unimodular random networks
• Approximate Schreier decorations and approximate Kőnig's line coloring theorem

Cited In (2)

• Fractional path coloring in bounded degree trees with applications
• Approximation and Online Algorithms

This page was built for publication: Borel fractional colorings of Schreier graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6159728)