Embedding Borel graphs into grids of asymptotically optimal dimension

2024/07/29 by Anton Bernshteyn, Jing Yu, Bernshteyn, Anton +1 · 1 citation
Computer Science · #Distributed and Parallel Computing Systems #Computability, Logic, AI Algorithms

paper · pdf · doi:10.48550/arxiv.2407.19785

Abstract

Let G be a Borel graph all of whose finite subgraphs embed into the d-dimensional grid with diagonals. We show that then G itself admits a Borel embedding into the Schreier graph of a free Borel action of \mathbb Z^O(d). This strengthens an earlier result of the authors, in which O(d) is replaced by O(ρlog ρ), where ρ is the polynomial growth rate of G.

Cited by

• Flows with minimal subdynamics

Related

• Large-scale geometry of Borel graphs of polynomial growth
• Borel Edge Colorings for Finite Dimensional Groups
• Borel Combinatorics of Schreier Graphs of ℤ-actions
• Borel Combinatorics of Abelian Group Actions
• Borel Vizing's Theorem for Graphs of Subexponential Growth