Orienting Borel Graphs

DOI10.1090/PROC/15742MaRDI QIDQ6332335arXivFDO

Authors Riley Thornton

Publication date 5 January 2020

Published in arXiv

Full work available at URL https://doi.org/10.1090/PROC/15742

Mathematics Subject Classification ID

Descriptive set theory (03E15) Coloring of graphs and hypergraphs (05C15) Measurable group actions (22F10)

arXiv classification

math.COmath.LOmath.PR

Abstract: We investigate when a Borel graph admits a (Borel or measurable) orientation with outdegree bounded by $k$ for various cardinals $k$. We show that for a p.m.p. graph $G$, a measurable orientation can be found when $k$ is larger than the normalized cost of the restriction of $G$ to any positive measure subset. Using an idea of Conley and Tamuz, we can also find Borel orientations of graphs with subexponential growth; however, for every $k$ we also find graphs which admit measurable orientations with outdegree bounded by $k$ but no such Borel orientations. Finally, for special values of $k$ we bound the projective complexity of Borel $k$-orientability for graphs and graphings of equivalence relations. It follows from these bounds that the set of equivalence relations admitting a Borel selector is $mathbf{Sigma}_2^1$ in the codes, in stark contrast to the case of smooth relations.

This page was built for publication: Orienting Borel Graphs

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