论文标题
定向鲍尔图
Orienting Borel Graphs
论文作者
论文摘要
我们调查了Borel图何时接受A（可衡量的）取向，以$ k $为$ k $的各种红衣主教$ k $。我们证明了P.M.P. Graph $ g $，当$ K $大于$ g $的限制成本时，可以找到可测量的方向。使用Conley和Tamuz的概念，我们还可以找到具有次指数生长的图形的Borel方向。但是，对于每$ k $，我们还会找到图形，这些图形以$ k $界定的超级限制，但没有这样的borel方向。最后，对于$ k $的特殊值，我们绑定了borel $ k $的投影复杂性 - 对等效关系的图形和图形的定向性。从这些界限中得出的是，在代码中，borel selector的一组等效关系是$ \mathbfς^1_2 $，与平滑关系的情况形成鲜明对比。
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Σ^1_2$ in the codes, in stark contrast to the case of smooth relations.
