An official website of the United States government
We investigate when a Borel graph admits a (Borel or measurable) orientation with outdegree bounded by k k for various cardinals k k . We show that for a probability measure preserving (p.m.p) graph G G , a measurable orientation can be found when k k is larger than the normalized cost of the restriction of G 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 k we also find graphs which admit measurable orientations with outdegree bounded by k k but no such Borel orientations. Finally, for special values of k k we bound the projective complexity of Borel k 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 Σ 2 1 \mathbf {\Sigma }_{2}^{1} in the codes, in stark contrast to the case of smooth relations.
more »
« less
This content will become publicly available on March 26, 2026
Tree-like graphings, wallings, and median graphings of equivalence relations
We prove several results showing that every locally finite Borel graph whose large-scale geometry is ‘tree-like’ induces a treeable equivalence relation. In particular, our hypotheses hold if each component of the original graph either has bounded tree-width or is quasi-isometric to a tree, answering a question of Tucker-Drob. In the latter case, we moreover show that there exists a Borel quasi-isometry to a Borel forest, under the additional assumption of (componentwise) bounded degree. We also extend these results on quasi-treeings to Borel proper metric spaces. In fact, our most general result shows treeability of countable Borel equivalence relations equipped with an abstract wallspace structure on each class obeying some local finiteness conditions, which we call aproper walling. The proof is based on the Stone duality between proper wallings and median graphs (i.e., CAT(0) cube complexes). Finally, we strengthen the conclusion of treeability in these results to hyperfiniteness in the case where the original graph has one (selected) end per component, generalizing the same result for trees due to Dougherty–Jackson–Kechris.
more »
« less
- Award ID(s):
- 2224709
- PAR ID:
- 10638114
- Publisher / Repository:
- Cambridge University Press
- Date Published:
- Journal Name:
- Forum of Mathematics, Sigma
- Volume:
- 13
- ISSN:
- 2050-5094
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We extend the Becker–Kechris topological realization and change-of-topology theorems for Polish group actions in several directions. For Polish group actions, we prove a single result that implies the original Becker–Kechris theorems, as well as Sami’s and Hjorth’s sharpenings adapted levelwise to the Borel hierarchy; automatic continuity of Borel actions via homeomorphisms and the equivalence of ‘potentially open’ versus ‘orbitwise open’ Borel sets. We also characterize ‘potentially open’ n-ary relations, thus yielding a topological realization theorem for invariant Borel first-order structures. We then generalize to groupoid actions and prove a result subsuming Lupini’s Becker–Kechris-type theorems for open Polish groupoids, newly adapted to the Borel hierarchy, as well as topological realizations of actions on fiberwise topological bundles and bundles of first-order structures. Our proof method is new even in the classical case of Polish groups and is based entirely on formal algebraic properties of category quantifiers; in particular, we make no use of either metrizability or the strong Choquet game. Consequently, our proofs work equally well in the non-Hausdorff context, for open quasi-Polish groupoids and more generally in the point-free context, for open localic groupoids.more » « less
-
Bringmann, Karl; Grohe, Martin; Puppis, Gabriele; Svensson, Ola (Ed.)Graph classes of bounded tree rank were introduced recently in the context of the model checking problem for first-order logic of graphs. These graph classes are a common generalization of graph classes of bounded degree and bounded treedepth, and they are a special case of graph classes of bounded expansion. We introduce a notion of decomposition for these classes and show that these decompositions can be efficiently computed. Also, a natural extension of our decomposition leads to a new characterization and decomposition for graph classes of bounded expansion (and an efficient algorithm computing this decomposition). We then focus on interpretations of graph classes of bounded tree rank. We give a characterization of graph classes interpretable in graph classes of tree rank 2. Importantly, our characterization leads to an efficient sparsification procedure: For any graph class 𝒞 interpretable in a graph class of tree rank at most 2, there is a polynomial time algorithm that to any G ∈ 𝒞 computes a (sparse) graph H from a fixed graph class of tree rank at most 2 such that G = I(H) for a fixed interpretation I. To the best of our knowledge, this is the first efficient "interpretation reversal" result that generalizes the result of Gajarský et al. [LICS 2016], who showed an analogous result for graph classes interpretable in classes of graphs of bounded degree.more » « less
-
A long-standing open problem in the theory of hyperfinite equivalence relations asks if the orbit equivalence relation generated by a Borel action of a countable amenable group is hyperfinite. In this paper we prove that this question always has a positive answer when the acting group is polycyclic, and we obtain a positive answer for all free actions of a large class of solvable groups including the Baumslag–Solitar group BS(1, 2) and the lamplighter group Z2 ≀ Z. This marks the first time that a group of exponential volume-growth has been verified to have this property. In obtaining this result we introduce a new tool for studying Borel equivalence relations by extending Gromov’s notion of asymptotic dimension to the Borel setting. We show that countable Borel equivalence relations of finite Borel asymptotic dimension are hyperfinite, and more generally we prove under a mild compatibility assumption that increasing unions of such equivalence relations are hyperfinite. As part of our main theorem, we prove for a large class of solvable groups that all of their free Borel actions have finite Borel asymptotic dimension (and finite dynamic asymptotic dimension in the case of a continuous action on a zero dimensional space). We also provide applications to Borel chromatic numbers, Borel and continuous Følner tilings, topological dynamics, and C∗-algebras.more » « less
-
Abstract Hajnal and Szemerédi proved that if G is a finite graph with maximum degree $$\Delta $$ , then for every integer $$k \geq \Delta +1$$ , G has a proper colouring with k colours in which every two colour classes differ in size at most by $$1$$ ; such colourings are called equitable. We obtain an analogue of this result for infinite graphs in the Borel setting. Specifically, we show that if G is an aperiodic Borel graph of finite maximum degree $$\Delta $$ , then for each $$k \geq \Delta + 1$$ , G has a Borel proper k -colouring in which every two colour classes are related by an element of the Borel full semigroup of G . In particular, such colourings are equitable with respect to every G -invariant probability measure. We also establish a measurable version of a result of Kostochka and Nakprasit on equitable $$\Delta $$ -colourings of graphs with small average degree. Namely, we prove that if $$\Delta \geq 3$$ , G does not contain a clique on $$\Delta + 1$$ vertices and $$\mu $$ is an atomless G -invariant probability measure such that the average degree of G with respect to $$\mu $$ is at most $$\Delta /5$$ , then G has a $$\mu $$ -equitable $$\Delta $$ -colouring. As steps toward the proof of this result, we establish measurable and list-colouring extensions of a strengthening of Brooks’ theorem due to Kostochka and Nakprasit.more » « less
