Orienting Borel Graphs

DOI10.1090/PROC/15742arXiv2001.01319MaRDI QIDQ6332335

Riley Thornton

Publication date: 5 January 2020

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.

Mathematics Subject Classification ID

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

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)