Borel fractional colorings of Schreier graphs

DOI10.5802/AHL.145MaRDI QIDQ6159728zbMATH OpenOpenAlexFDO

Authors Anton Bernshteyn

Publication date 20 June 2023

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

Copyright license Creative Commons Attribution 4.0 International

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)

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.

Recommendations

• Borel edge colorings for finite-dimensional groups
• Borel chromatic numbers
• A complexity problem for Borel graphs
• A bound on measurable chromatic numbers of locally finite Borel graphs
• Measurable chromatic and independence numbers for ergodic graphs and group actions

Cites work

• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 1131873 (Why is no real title available?)
• A determinacy approach to Borel combinatorics
• Approximate Schreier decorations and approximate Kőnig's line coloring theorem
• Bernoulli actions are weakly contained in any free action
• Borel chromatic numbers
• Borel combinatorics of locally finite graphs
• Borel structurability on the 2-shift of a countable group
• Invariant Schreier decorations of unimodular random networks
• Large independent sets in regular graphs of large girth
• Local algorithms for independent sets are half-optimal
• Measurable versions of the Lovász local lemma and measurable graph colorings
• Randomized greedy algorithms for independent sets and matchings in regular graphs: exact results and finite girth corrections
• Ultraproducts of measure preserving actions and graph combinatorics

Cited in

(4)

• Factor-of-iid Schreier decorations of lattices in Euclidean spaces
• Borel edge colorings for finite-dimensional groups
• 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)