Embedding Borel graphs into grids of asymptotically optimal dimension

Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be a Borel graph all of whose finite subgraphs embed into the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d"> <mml:semantics> <mml:mi>d</mml:mi> <mml:annotation encoding="application/x-tex">d</mml:annotation> </mml:semantics> </mml:math> </inline-formula> /dimensional grid with diagonals. We show that then <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> itself admits a Borel embedding into the Schreier graph of a free Borel action of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper Z Superscript upper O left-parenthesis d right-parenthesis"> <mml:semantics> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">Z</mml:mi> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>d</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:msup> <mml:annotation encoding="application/x-tex">\mathbb {Z}^{O(d)}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . This strengthens an earlier result of the authors, in which <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis d right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>d</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(d)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is replaced by <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis rho log rho right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi> ρ </mml:mi> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mi> ρ </mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(\rho \log \rho )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="rho"> <mml:semantics> <mml:mi> ρ </mml:mi> <mml:annotation encoding="application/x-tex">\rho</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the polynomial growth rate of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> .