Quasi-treeings are treeable: a streamlined proof

2024/09/15 by Zhai, Zhaoshen · 1 citation
#03E15 #20E08 #20F65 #37A20 #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.2409.09843

Abstract

We present a streamlined exposition of a construction by R. Chen, A. Poulin, R. Tao, and A. Tserunyan, which proves the treeability of equivalence relations generated by any locally-finite Borel graph such that each component is a quasi-tree. More generally, we show that if each component of a locally-finite Borel graph admits a finitely-separating Borel family of cuts, then we may 'canonically' replace each component of the graph by a tree of special ultrafilter-like objects on cuts called orientations; moreover, if the cuts are dense towards ends, then the union of these trees is a Borel treeing.

Cited by

• Minor-excluded graphs and soficity

Related

• Applications of tree decompositions and accessibility to treeability of Borel graphs
• On describing trees and quasi-trees from their leaves
• Quasi-isometries between non-locally-finite graphs and structure trees
• Tree amalgamations and quasi-isometries
• Universal countable Borel quasi-orders