%~Mouliné par MaN_auto v.0.25.0 2021-10-04 13:35:16 \documentclass[AHL,Unicode,longabstracts,published]{cedram} \usepackage{pgf} \usepackage{tikz} \usepackage{pgfplots} %\usepackage{enumerate} \usetikzlibrary{arrows} \newcommand{\bfB}{\mathbf{B}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\ortt}{\texttt{or}} \newcommand{\N}{\mathbb{N}} \newcommand{\bbP}{\mathbb{P}} \newcommand{\F}{\mathcal{F}} \newcommand{\G}{\mathcal{G}} \newcommand{\clM}{\mathcal{M}} \newcommand{\clD}{\mathcal{D}} \newcommand{\clC}{\mathcal{C}} \newcommand{\clH}{\mathcal{H}} \newcommand{\clB}{\mathcal{B}} \newcommand{\GoG}{\mathfrak{G}} \newcommand{\orl}{\mathrm{or}} \newcommand{\redl}{\mathrm{red}} \newcommand{\bluel}{\mathrm{blue}} \newcommand{\purpll}{\mathrm{purple}} \DeclareMathOperator{\Sch}{Sch} \DeclareMathOperator{\ran}{ran} \DeclareMathOperator{\Cyl}{Cyl} \newcommand{\acts}{\curvearrowright} %%%%%%%%%%%%%%%%%%%%%% \definecolor{qqqqff}{rgb}{0.,0.,1.} \definecolor{yqqqyq}{rgb}{0.5019607843137255,0.,0.5019607843137255} %\definecolor{yqqqyq}{rgb}{0.5019607843137255,0.,0.5019607843137255} \definecolor{ffqqqq}{rgb}{1.,0.,0.} \definecolor{qqqqff}{rgb}{0.,0.,1.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \makeatletter \def\@setauthors{% \begingroup \raggedright \fontfamily{\OratorFont}\fontsize{18pt}{18pt}\fontseries{m}\selectfont \parindent=0pt\normalparindent=0pt% \def\lastname##1{\def\l@stmp@{##1}\uppercasenonmath\l@stmp@\l@stmp@}% \let\firstname\lastname% \let\middlename\lastname% %\myspace : filet entre les noms des auteurs \def\myspace{\vskip5pt plus 1pt minus 1pt\hrule height 0.2pt\vskip5pt plus 1pt minus 1pt\relax}% % Dans la macro \authors, les noms des auteurs sont espac\'es par \and. % On fait en sorte que cette commande passe \`a la ligne et affiche le filet, comme % \c{c}a tout se fait tout seul si on ex\'ecute \authors. % On rajoute aussi une bo\^{\i}te invisible de taille verticale % la taille verticale maximale des noms des auteurs, pour assurer que les filets % soient tous \'equitablement espac\'es (utile s'il y a des auteurs avec accents et % des auteurs sans accents) \def\and{\myspace\leavevmode\begingroup\def\and{}\vphantom{\authors}\endgroup}% \and\authors\myspace\unskip% \endgroup } \makeatother %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \graphicspath{{./figures/}} \newcommand*{\mk}{\mkern -1mu} \newcommand*{\Mk}{\mkern -2mu} \newcommand*{\mK}{\mkern 1mu} \newcommand*{\MK}{\mkern 2mu} \hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red} \newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}} \newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}} \newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}} \newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}} \let\oldtilde\tilde \renewcommand*{\tilde}[1]{\mathchoice{\widetilde{#1}}{\widetilde{#1}}{\oldtilde{#1}}{\oldtilde{#1}}} \let\oldexists\exists \renewcommand*{\exists}{\mathrel{\oldexists}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title[Invariant Schreier decorations of unimodular random networks]{Invariant Schreier decorations of unimodular random networks} \alttitle{Décorations de Schreier invariantes sur les graphes aléatoires unimodulaires} \subjclass{37A50, 20E05, 05C15} \keywords{Schreier graph, graph limits, unimodular random graph, Invariant Random Subgroup} \author[\initial{L.~M.} \lastname{Tóth}]{\firstname{L{\'a}szl{\'o}} \middlename{M{\'a}rton} \lastname{T{\'o}th}} \address{Chair of Ergodic and\\ Geometric Group Theory,\\ EPFL SB MATH EGG, Station 8,\\1015 Lausanne, (Switzerland)} \email{laszlomarton.toth@epfl.ch} \begin{abstract} We prove that every $2d$-regular unimodular random network carries an invariant random Schreier decoration. Equivalently, it is the Schreier coset graph of an invariant random subgroup of the free group $F_d$. As a corollary we get that every $2d$-regular graphing is the local isomorphic image of a graphing coming from a p.m.p. action of $F_d$. The key ingredients of the analogous statement for finite graphs do not generalize verbatim to the measurable setting. We find a more subtle way of adapting these ingredients and prove measurable coloring theorems for graphings along the way. \end{abstract} \begin{altabstract} Nous démontrons que tout graphe aléatoire unimodulaire $2d$-régulier admet une décoration de Schreier aléatoire invariante. De manière équivalent, c'est le graphe de Schreier des classes d'un sous-groupe invariant aléatoire du groupe libre $F_d$. Comme corollaire, nous obtenons que tout graphage $2d$-régulier est localement l'image isomorphe d'un graphage provenant d'une action de $F_d$ préservant une mesure de probabilité. Les ingrédients-clé de l'énoncé analogue pour les graphes finis ne se généralisent pas tels quels au contexte mesurable. Nous trouvons une manière plus subtile d'adapter ces ingrédients, et nous obtenons en chemin des théorèmes de coloriages mesurables de graphages. \end{altabstract} \datereceived{2020-03-25} \daterevised{2021-01-25} \dateaccepted{2021-02-05} \editor{D. Aldous} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \dateposted{2021-12-03} \begin{document} \maketitle \section{Introduction} \label{section:intro} It is a nice exercise in combinatorics to show that any 2d-regular finite graph is a Schreier graph of the free group $F_d$ on $d$ generators. That is, the edges can be oriented and colored by $\{1,\,\ldots,\,d\}=[d]$ such that every vertex has exactly one incoming and outgoing edge of each color. We call such a coloring and orientation a \emph{Schreier decoration} of our graph. We do not want to spoil the argument for the reader, but will inevitably have to talk about parts of the solution. See~\cite{cannizzo2013invariant} for a proof. The main result of this paper generalizes the above result to unimodular random rooted graphs, a notion that arises as a natural generalization of a finite graph in the limit theory of sparse graph sequences. \begin{theo}\label{theorem:main} Every $2d$-regular unimodular random rooted graph has an invariant random Schreier decoration. \end{theo} We now introduce unimodularity and invariant random Schreier decorations. For the precise definitions omitted from the Introduction see Section~\ref{section:preliminaries}. Let $\GoG_{\circ}^{2d}$ denote the space of rooted, connected (possibly infinite) graphs with degrees bounded by $2d$. Similarly, let $\GoG_{\circ}^{\Sch}$ denote the space of rooted, connected Schreier graphs of $F_d$. There is a natural forgetting map $\Phi: \GoG_{\circ}^{\Sch} \to \GoG_{\circ}^{2d}$. We denote by $\clM(X)$ the set of Borel probability measures on a topological space $X$. A measure $\mu \in \clM(\GoG_{\circ}^{2d})$ is called a \emph{unimodular random rooted graph} or \emph{unimodular random rooted network} if it satisfies an involution invariance property mimicking reversibility of random walks. The ``rooted'' is dropped to shorten terminology, unless we want to explicitly emphasize the presence of a root. A \emph{random Schreier graph} is a measure $\mu' \in \clM(\GoG_{\circ}^{\Sch})$. It is \emph{invariant}, if it is preserved by the natural action $F_d \acts \GoG_{\circ}^{\Sch}$, where generators $s \in [d]$ act by moving the root along the unique outward edge colored by $s$ adjacent to it. \begin{defi}\label{definition:invariant_schreierization} Let $\mu \in \clM(\GoG_{\circ}^{2d})$ be a unimodular random rooted graph that is $2d$-regular with probability 1. An invariant random Schreier decoration of $\mu$ is a measure $\mu' \in \clM(\GoG_{\circ}^{\Sch})$ that is invariant and has $\Phi_{*} \mu' = \mu$. \end{defi} \noindent The condition $\Phi_{*} \mu' = \mu$ expresses that forgetting both the orientation and the coloring from a random Schreier graph generated by $\mu'$ gives the same random graph as $\mu$ in distribution. %\medskip Cannizzo investigated the Schreier decorations of unimodular random rooted graphs in~\cite{cannizzo2013invariant}. He showed that for an invariant random Schreier graph $\mu'$ the pushforward $\Phi_{*} \mu'$ is always unimodular. Moreover, under some assumptions, if a unimodular random graph has an invariant random Schreier decoration, then it has uncountably many ergodic ones. Theorem~\ref{theorem:main} complements these results nicely. Invariant random Schreier graphs are closely related to Invariant Random Subgroups (IRS's) introduced by Abért, Glasner and Virág in~\cite{abert2014kesten}. On one hand, the invariance property of the graph translates to conjugation invariance of the random subgroup that is the stabilizer of the root. On the other hand, given an IRS $H \leq F_d$, the Schreier graph on the coset space $F_d/H$ rooted at $H$ gives an invariant random Schreier graph. Keeping this correspondence in mind, Theorem~\ref{theorem:main} can be thought of as a statement on IRS's of $F_d$. Bowen proved in~\cite{bowen2012invariant} that $F_d$ has a large ``zoo'' of ergodic IRS's. Cannizzo's work shows that non-unimodularity is a probabilistic obstruction to finding an IRS with a given factor geometry. Our result shows that it is the only obstruction. %\medskip The proof of the finite case relies on two parts. First, a finite $2d$-regular graph has a \emph{balanced} orientation. That is, an orientation with equal in- and outdegrees at all vertices. Second, a $d$-regular bipartite finite graph can be properly edge-colored with $d$ colors. This is K{\H o}nig's line coloring theorem. Our approach to Theorem~\ref{theorem:main} is to study these questions for \emph{graphings} instead of graphs. Graphings are measurable, bounded degree graphs on some standard Borel probability space $(X,\nu)$ as vertex set with an additional measure preserving property. Their close connection to unimodular random graphs is also explained in Section~\ref{section:preliminaries}. For now it suffices to know that any unimodular random graph $\mu$ can be encoded in a single graphing $\G$. We say $\G$ \emph{represents} $\mu$ if the connected component in $\G$ of a $\nu$-random vertex is the same as $\mu$ in distribution. Such a representing graphing exists for any unimodular random graph, though the choice is not unique. Unfortunately neither of the two finite statements directly generalizes to graphings. In~\cite{laczkovich1988closed} Laczkovich constructed a $2$-regular graphing that has no measurable balanced orientation. Moreover, there are $d$-regular bipartite graphings that have no measurable proper edge coloring with $d$ colors~\cite[Section~6]{conley2013measurable}. We substitute these steps with the next two theorems. First we claim that representing graphings can be chosen smartly. \begin{theo}\label{theorem:balanced_orientation} Let $\mu$ be a $2d$-regular unimodular random rooted graph. Then there exists a graphing $\G=(X,E,\nu)$ on a standard Borel space $(X, \nu)$ such that $\G$ represents $\mu$, and there is a measurable balanced orientation of the edges of $\G$. \end{theo} Second, we claim that the coloring can be done with little error. Coloring questions for Borel graphs and graphings have been extensively studied, see~\cite{kechris2015descriptive} for a survey. We build on the work of Cs{\'o}ka, Lippner and Pikhurko in~\cite{csoka2016kHonig} to derive a version of K{\H o}nig's theorem that suits our purposes. \begin{theo}\label{theorem:almost_proper_coloring} Let $\G=(X_1,X_2,E, \nu)$ be a $d$-regular bipartite graphing. For every $\varepsilon > 0$ there is a measurable proper edge coloring of $\G$ with $d+1$ colors, such that the measure of edges of the $(d+1)^{\rm th}$ color is at most $\varepsilon$. \end{theo} Combining Theorems~\ref{theorem:balanced_orientation} and~\ref{theorem:almost_proper_coloring} with a subsequential weak limit argument gives the proof of Theorem~\ref{theorem:main}. % %\medskip We can formulate versions of both Theorem~\ref{theorem:main} and~\ref{theorem:almost_proper_coloring} using local isomorphisms. We say a graphing $\G_1=(X_1, E_1, \nu_1)$ is the \emph{local isomorphic image} of another graphing $\G_2=(X_2, E_2, \nu_2)$ if their is a measure preserving map $\varphi: X_2 \to X_1$ that is a rooted isomorphism restricted to the connected component of almost all vertices of $\G_2$. It is clear that in this case $\G_1$ and $\G_2$ represent the same unimodular random graph. Theorem~\ref{theorem:main} can be reformulated as follows. \begin{coro}\label{corollary:graphing_lift} Every $2d$-regular graphing $\G$ is the local isomorphic image of some graphing $\G'$ that comes from a p.m.p. action of $F_d$. That is, the edges of $\G'$ have a measurable balanced orientation and coloring with $[d]$. \end{coro} This formulation is a priori stronger, it is easy to see that Corollary~\ref{corollary:graphing_lift} implies Theorems~\ref{theorem:main} (and~\ref{theorem:balanced_orientation}) directly. The other implication is proved in Section~\ref{section:graphings}. Similarly, Theorem~\ref{theorem:almost_proper_coloring} has the following version. \begin{coro}\label{corollary:proper_coloring_lift} Let $\G=(X_1,X_2,E)$ be a bipartite graphing with maximum degree $d$. Then $\G$ is the local isomorphic image of a bipartite graphing that can be measurably edge-colored with $d$ colors. \end{coro} \noindent Both corollaries are instances of a more general correspondence between coloring results for unimodular random networks and graphings. We express this phenomenon in Theorem~\ref{theorem:translation} in Section~\ref{section:graphings}. \begin{rema*} For graphings being bipartite is a stronger assumption than containing no odd cycles. This distinction is not relevant for our results, Theorem~\ref{theorem:almost_proper_coloring} and Corollary~\ref{corollary:proper_coloring_lift} hold with the weaker assumption as well. The reason for stating our results this way is that the relevant graphings arising in this paper are automatically bipartite. \end{rema*} \noindent It is natural to ask if any of these random decorations can be constructed as factor of i.i.d.\ (FIID) processes. See for example~\cite{csoka2017invariant} for the definition of FIID for deterministic graphs, the definition for random graphs is analogous. \begin{enonce*}{Question} Which $2d$-regular unimodular random networks have a factor of i.i.d.\ Schreier decoration? Which even degree unimodular random networks have a factor of i.i.d.\ balanced orientations? \end{enonce*} \noindent Note that the bi-infinite line has no FIID balanced orientation. %\medskip \goodbreak The structure of the paper is as follows. In Section~\ref{section:preliminaries} we give a detailed introduction to unimodularity, graphings, and explain the connection to Benjamini--Schramm convergence. We also study the finite statement to motivate our question. We consider orientations in Section~\ref{section:orientation} and prove Theorem~\ref{theorem:balanced_orientation}. In Section~\ref{section:coloring} we turn to coloring the edges and prove Theorem~\ref{theorem:almost_proper_coloring}. We put these together and prove Theorem~\ref{theorem:main} in Section~\ref{section:proof_of_main}. In Section~\ref{section:graphings} we prove Corollaries~\ref{corollary:graphing_lift} and~\ref{corollary:proper_coloring_lift}. %\medskip \subsection*{Acknowledgements} The author would like to thank Miklós Abért, Damien Gaboriau, Ferenc Bencs and Nóra Sz{\H o}ke for inspiring conversations about the topic. %\end{acknowledgement} \section{Graphings, unimodularity and local convergence} \label{section:preliminaries} In this section we will introduce the main notions of the paper and provide background and motivation for Theorem~\ref{theorem:main}. A thorough and beautifully written exposition of the notions introduced here can be found in~\cite{lovasz2012large}. Throughout this paper graphs will be simple; they do not contain loops or multiple edges. We will use standard letters $F,G, \ldots$ to denote countable graphs, calligraphic letters $\G, \clH,\,\ldots$ to denote graphings and $\GoG$ with certain indices to denote spaces of graphs. The measures $\mu, \mu', \widetilde{\mu},\,\ldots$ will denote random graphs, while $\nu, \nu', \widetilde{\nu},\,\ldots$ will denote measures on vertex or edge sets of graphings. To avoid confusion, decorations of edges will be \emph{colors} and decorations of vertices will be \emph{labels}. The map $\Phi$ will always forget all the decoration of a graph. We do not burden the notation with indicating what type of decoration we are forgetting, this will always be clear from context. We consider Schreier graphs to be rooted and connected, unless explicitly stated otherwise. Properties of random graphs are always understood to hold with probability 1. \subsection{Local convergence} Recall that $\GoG_{\circ}^{2d}$ denotes the space of rooted, connected graphs with degrees bounded by $2d$. For two such graphs $(G_1, o_1), (G_2, o_2) \in \GoG_{\circ}^{2d}$ we define their distance as \[ d\big(\left(G_1, o_1\right), \left(G_2, o_2\right)\big) = \frac{1}{2^r}, \] where $r$ is the largest integer with $B_{G_1}(r,o_1) \cong B_{G_2}(r,o_2)$. $B_G(r,o)$ denotes the rooted ball in $G$ around $o$ of radius $r$, and the isomorphism has to map $o_1$ to $o_2$. Two rooted graphs are close, if they look the same in a large neighborhood of the root. If the balls above are isomorphic for all $r \in \N$, then $(G_1,o_1)$ and $(G_2,o_2)$ are isomorphic, and their distance is defined 0. With this distance $\GoG_{\circ}^{2d}$ becomes a totally disconnected compact metric space~\cite[Section~18.3.1]{lovasz2012large}. Local (or Benjamini--Schramm~\cite{benjamini2001}) convergence takes a connected finite graph $F$ (with degree bound $2d$) and by choosing a uniform random root among its vertices turns it into the random rooted graph $(F,o)$. If the graph is not connected, only the component of the random root is kept. This way we obtain a probability measure $\mu_F$ on $\GoG_{\circ}^{2d}$. Formally we define the map $f:V(F) \to \GoG_{\circ}^{2d}$, $f(v) = (C_F(v),v)$, where $C_F(v)$ denotes the component of $F$ containing $v$. Then $\mu_F$ is simply the pushforward of the uniform measure on $V(F)$ onto $\GoG_{\circ}^{2d}$ by $f$. A sequence of graphs $(F_n)$ is convergent, if the corresponding $\mu_{F_n}$ converge weakly in the space $\clM(\GoG_{\circ}^{2d})$ of probability measures on $\GoG_{\circ}^{2d}$. In this case the weak limit $\mu$ is considered to be the limit of the finite graphs $F_n$. Since $\GoG_{\circ}^{2d}$ is totally disconnected, weak convergence is equivalent to the convergence of the measures of the following clopen sets. For a finite rooted graph $(F,v) \in \GoG_{\circ}^{2d}$ of radius $r$ we define the clopen set \[ \GoG_{(F,\,v)}=\left\{(G,o) \in \GoG_{\circ}^{2d}~\middle|~B_{G}(r,o) \cong (F,v)\right\}. \] A sequence of measures $\mu_n \in \clM(\GoG_{\circ}^{2d})$ converges weakly to $\mu$ if and only if $\mu_n(\GoG_{(F,\,v)})\linebreak\to \mu(\GoG_{(F,\,v)})$ for all choices of $(F,v)$. While the $\mu_{F_n}$ are supported on finite rooted graphs, their limit $\mu$ can be supported on infinite graphs as well. Throughout the paper various spaces of rooted and decorated graphs will appear. They are all metric spaces with rooted metrics that are analogous to the one on $\GoG_{\circ}^{2d}$, with isomorphisms required to respect the decoration as well as the graph structure and the root. We believe that not defining these metrics explicitly will cause no confusion. \subsection{Sofic and unimodular measures} A central question of this limit theory is to determine which measures are limits of finite graphs. This leads to the notions of \emph{sofic} and \emph{unimodular} measures. Soficity is easy to define: a measure $\mu \in \clM(\GoG_{\circ}^{2d})$ is sofic if it is the limit of measures $\mu_{F_n}$ corresponding to finite graphs. Unimodularity is more subtle, and we will only define it in the regular case. See for example~\cite{lovasz2012large} for a general treatment. Let $\mu \in \clM(\GoG_{\circ}^{2d})$ be $2d$-regular with probability 1. It is unimodular if it satisfies the following involution invariance property. We generate a random instance $(G,o)$ of $\mu$. We then choose a uniform random neighbor $o'$ of $o$ in $G$. We say that $\mu$ is unimodular, if the random birooted graph $(G,o,o')$ is invariant with respect to inverting the order of the roots. Formally we introduce the space $\GoG_{\circ\circ}^{2d}$ of connected graphs with degrees bounded by $2d$, that have two distinguished vertices, the first and the second root. The topology is defined similarly to $\GoG_{\circ}^{2d}$, two such birooted graphs are close, if the look the same in large neighborhoods around both roots. There is a natural involution $\iota: \GoG_{\circ\circ}^{2d} \to \GoG_{\circ\circ}^{2d}$ swapping the roots: $\iota (G,o,o') = (G,o',o)$. The random rooted graph $\mu \in \clM(\GoG_{\circ}^{2d})$ determines a measure $\widetilde{\mu} \in \clM(\GoG_{\circ\circ}^{2d})$ as above, by choosing the second root uniformly among the neighbors of the original. We say $\mu$ is unimodular if $\iota_{*}\widetilde{\mu}=\widetilde{\mu}$. We mention two important facts about unimodularity. First, measures $\mu_F$ coming from finite graphs are unimodular. (This is true without assuming $F$ to be regular, but here we only defined unimodularity for regular graphs.) Indeed, unimodularity is just a reformulation of the simple random walk being not only stationary, but also reversible with respect to the uniform measure on the vertices of a finite regular graph. Second, unimodularity is a closed condition in $\clM(\GoG_{\circ}^{2d})$ with respect to weak convergence. The reason is that involution invariance can be checked using only the local neighborhood probabilities $\mu(\GoG_{(F,\,v)})$. These two facts imply that every sofic measure is unimodular. The converse however is an open question, it is not known whether there is a non-sofic unimodular measure. \subsection{Invariance in the finite case} To motivate Theorem~\ref{theorem:main} we explore how the invariance property appears in the finite case. Our finite statement takes a connected finite graph $F$ and turns it into an unrooted Schreier graph $\widetilde{F}=(F, \orl, c)$, where $\orl$ and $c$ signify the orientation and coloring respectively. If we then choose a uniform random root, we get the random rooted Schreier graph $(F, o, \orl, c)$, where $o \in V(F)$ is uniform random. We denote its distribution by $\mu'_{\widetilde{F}} \in \clM(\GoG_{\circ}^{\Sch})$. The action of any generator $s$ is by a bijection on $V(F)$, so the uniform distribution on $V(F)$ is invariant with respect to the action $F_d \acts V(F)$. This implies that $\mu'_{\widetilde{F}}$ is invariant. The graph structure of $\mu'_{\widetilde{F}}$ without the orientation and coloring is the same as $\mu_F$. Using our notation, we say $\Phi_{*} \mu'_{\widetilde{F}} = \mu_F$. These two phenomena, $\mu'_{\widetilde{F}}$ being invariant and $\Phi_{*} \mu'_{\widetilde{F}} = \mu_F$ are what motivate the definition of an invariant random Schreier decorations. With this in mind it is relatively easy to prove that sofic random rooted graphs have invariant random Schreier decorations. Finding Schreier decorations of the finite approximations, then taking a subsequential weak limit of the corresponding random rooted Schreier graphs solves the problem. Theorem~\ref{theorem:main} shows that the property of having an invariant random Schreier decoration does not distinguish soficity and unimodularity. \begin{rema*} For a fixed connected, $2d$-regular infinite rooted or unrooted graph finding a Schreier decoration is simply a compactness argument once one knows the finite version. In fact rooted (possibly infinite), connected Schreier graphs are in one-to-one correspondence with subgroups of $F_d$. If one wants to build an invariant Schreier decoration however, one has to pick the individual Schreier decorations of the random instances of the unimodular random graph in a coherent way, so that the whole process becomes invariant. The additional freedom is that the choice can be random. \end{rema*} \subsection{Graphings} Graphings have quite a few equivalent definitions. We are going to stick with \cite{lovasz2012large}. \begin{defi}[Graphing] \label{def:graphing} Let $X$ be a standard Borel space and let $\nu$ be a probability measure on the Borel sets in $X$. A \emph{graphing} with degree bound $2d$ is a graph $\G$ on $V(\G) = X $ with Borel edge set $E(\G) \subset X \times X$ in which all degrees are at most $2d$ and \begin{equation}\label{eqn:graphing} \int_{A} \deg(x,B) \ d \nu (x) = \int_{B} \deg(x,A) \, d \nu (x) \end{equation} for all measurable sets $A,B \subseteq X$, where $\deg(x,S)$ is the number of edges from $x \in X$ to $S \subseteq X$. \end{defi} Formally the graphing consists of the quadruple $\G=(X,\clB, E, \nu)$, where $\clB$ denotes the Borel $\sigma$-algebra on $X$. We will suppress $\clB$ from the notation. Looking at the connected component of a random vertex will represent a unimodular random rooted graph. Recall that for $x\in X$ its connected component in $\G$ is denoted $C_{\G}(x)$. It is a basic property of Borel graphs that the map $f : X \to \GoG_{\circ}^{2d}$, defined by $f(x)=(C_{\G}(x),x)$ is Borel. This way we can define $\mu_{\G} = f_{*} \nu$ similarly to the finite graph case. The measure preserving property~\eqref{eqn:graphing} is closely related to the involution invariance that we used to define unimodularity. In fact~\eqref{eqn:graphing} implies that $\mu_{\G}$ is unimodular. In the other direction the connection is a bit more subtle. Fix a unimodular random rooted graph $\mu \in \clM(\GoG_{\circ}^{2d})$. We say that a graphing $\G$ represents $\mu$ if $\mu=\mu_{\G}$. \begin{theo}[\cite{aldous2007processes,elek2007note}] \label{theorem:representing_graphing} Every unimodular random rooted graph is represented by some graphing. \end{theo} As mentioned in the Introduction, the choice of a representing graphing is not unique. Graphings with distinctly different global measurable structure can represent the same unimodular random rooted graph. In~\cite[Theorem~18.37]{lovasz2012large} a construction of a representing graphing is carefully explained and motivated. The representing graphings described there always have the same vertex and edge sets, only the measure changes. The space is a vertex-labeled version of $\GoG_{\circ}^{2d}$, with edges connecting graphs that are the same up to a displacement of the root to a neighbor. Starting from a unimodular random rooted graph $\mu$ one uses further random vertex labels to break all potential symmetries of any realizations. This results in a measure $\nu$ on the space of vertex-labeled rooted graphs. The unimodularity of $\mu$ implies that~\eqref{eqn:graphing} is satisfied by $\nu$. We will adapt this construction to our situation in Subsection~\ref{subsection:constructing_graphings}. \subsection{Measuring edges of graphings} The property~\eqref{eqn:graphing} of graphings allows one to measure set of edges in a meaningful way. Let $\widetilde{\nu}$ be the measure on $E \subseteq X \times X$ obtained the following way. For a Borel subset $C \subseteq E$ of edges let \[ \widetilde{\nu} (C) = \frac{1}{2} \int_{X} \deg_{C}(x) \ d \nu(x). \] Here $\deg_{C}(x)$ denotes the degree of $x$ using the edge set $C$, that is the number of edges in $C$ adjacent to $x$. The normalization accounts for counting edges from both endpoints. Intuitively equation~\eqref{eqn:graphing} expresses that edges have the same weight from both endpoints. For the edge set $C=E(A,B)$ of edges between $A$ and $B$ it says that measuring them from $A$ and $B$ gives the same answer. In our case the measure $\widetilde{\nu}$ takes values in $[0,2d]$. \subsection{Sparse vertex labeling of graphings} We will use vertex labeling to break local symmetries of graphings. Proposition~\ref{corollary:sparse_labeling} below is a basic tool when working with graphings. We say a labeling of a graph is $r$-sparse, if vertices of distance at most $r$ always have distinct labels. A $1$-sparse labeling is traditionally called a \emph{proper} labeling. Concerning vertex labelings of Borel graphs Kechris, Solecki and Todorcevic \cite[Theorem~4.6]{kechris1999borel} show that if the degree is bounded by $\Delta$, then there is a proper Borel labeling of the vertices with $\Delta+1$ labels. One can also show that introducing additional edges in a Borel graph connecting vertices at distance at most $r$ gives a Borel graph. This together with the above coloring result has the following useful corollary. \begin{prop}\label{corollary:sparse_labeling} For every bounded degree Borel graph $\G$ and $r \in \N$ there is an $r$-sparse Borel labeling $l : V \to [k]$ for some $k \in \N$. \end{prop} See for example~\cite[Corollary~3.1]{csoka2016kHonig} for a more detailed exposition. \section{Orientation} \label{section:orientation} In this section we prove Theorem~\ref{theorem:balanced_orientation}. At first we exhibit a way to choose a random balanced orientation of rooted, even degree infinite graphs. The important property will be that for any even degree graph $G$ and vertices $v_1, v_2$ the random balanced orientations of $(G, v_1)$ and $(G,v_2)$ will be the same in distribution on the edges of $G$. We then explain how this allows one to construct a measurably orientable graphing to represent a unimodular random rooted graph. \subsection{Orienting even degree trees} \label{subsection:orienting_trees} Let $(T,o)$ be an infinite (connected) rooted tree with even degrees. We describe a random balanced orientation of $(T,o)$. For all vertices $v \in V(T)$ let $\deg(v)=2d_v$. We start at the root, and orient $d_o$ edges inwards and $d_o$ edges outwards randomly. We proceed to the neighbors of $o$. If $v$ is a neighbor of $o$, then one of the $2 d_v$ edges at $v$ is already oriented, say towards $v$. So from the $2d_v-1$ undirected ones we orient $d_v-1$ inwards and $d_v$ outwards randomly, independently of the previous choice. We continue this procedure radially outwards from $o$, independently randomizing at each vertex. As $T$ is a tree we will always have exactly 1 already oriented edge at each vertex. The result of this random procedure is a balanced orientation of $(T,o)$. \begin{lemm} The random orientation described above does not depend on the choice of root in $T$. More precisely, if $v_1$ and $v_2$ are two vertices of $T$, then the random orientations started at $v_1$ and $v_2$ are the same in distribution. \end{lemm} \begin{proof} Let $F \subseteq T$ be a \emph{saturated} finite subtree containing both $v_1$ and $v_2$ as internal vertices. By saturated we mean that vertices of $F$ are either leaves of $F$, or have all their neighbors in $F$ as well. The internal vertices of $F$ are the non-leaves. Fix any orientation $\ortt$ of the edges of $F$ that is balanced at internal vertices. We compute the probability of getting $\ortt$ of $F$ when starting our procedure at $v_1$. List the internal vertices of $F$ in a radially expanding order: $\{u_1, u_2,\,\ldots,\,u_n\}$, specifically $u_1 = v_1$. At $u_1$ we have to match 1 out of \[ \binom{2d_{u_1}}{d_{u_1}} \] possible orientations. At each later $u_i$ we have to match 1 out of the possible \[ \binom{2d_{u_i}-1}{d_{u_i}} \] orientations of the remaining edges. Note that this does not depend on whether the edge already oriented at $u_i$ is inwards or outwards. In total, the probability of generating our fixed orientation from $v_1$ is \[ \frac{1}{\binom{2d_{u_1}}{d_{u_1}}}\prod_{i=2}^{n}\frac{1}{\binom{2d_{u_i}-1}{d_{u_i}}}. \] Using that $\binom{2d_{u_1}}{d_{u_1}} = 2 \cdot \binom{2d_{u_1}-1}{d_{u_1}}$, we can rewrite this as \[ \frac{1}{2}\prod_{i=1}^{n}\frac{1}{\binom{2d_{u_i}-1}{d_{u_i}}}. \] Notice that this later expression does not change if we reorder the $u_i$, so starting from $v_2$ we will get the same probability. This holds for all finite subtrees $F$ and orientations $\ortt$ as above. Let $\Cyl(F,\ortt)$ denote the set of all orientations of $T$ (not necessarily balanced) that coincide with $\ortt$ at internal vertices of $F$. We proved that the two random orientations assign equal measure to all such $\Cyl(F,\ortt)$. (This holds also if $\ortt$ is not balanced at all internal vertices of $F$; then both random orientations assign measure 0 to $\Cyl(F,\ortt)$.) The sets $\Cyl(F,\ortt)$ form a base of the product topology on the set of (not necessarily balanced) orientations of $T$. Therefore the two random processes are the same in distribution. \end{proof} \subsection{Orienting even degree graphs} We now define a random balanced orientation of rooted, bounded even degree infinite graphs. Again, the random orientation will not depend on the choice of root in distribution. Given such a graph $(G,o)$, we will first orient cycles as long as there are any. Our procedure will consist of countably many stages, with each stage consisting of countably many steps. During the procedure, we will have both oriented and undirected edges. We say that at a certain point a cycle is undirected, if all its edges are undirected. Two cycles of the same length are neighbors, if they share an edge. After stage $n$, with probability 1 there will be no undirected cycles of length at most $n$. At every step of stage $n$ we consider currently undirected cycles of length $n$, and randomize a uniform $[0,1]$ label for each. If an undirected cycle has a higher label than all of its neighbors, then it gets oriented, randomly in one of the two possible directions. Since our graph has bounded degree, the number of neighbors of an undirected cycle considered during stage $n$ is bounded. So as long as it remains undirected, it has a positive probability (bounded away from 0) to get a higher label than all its neighbors at every step. Therefore staying undirected after countably many steps happens with probability 0. At every step the partial orientation is balanced. That is, the indegrees and outdegrees of vertices are the same. Clearly the undirected degree of each vertex is always even. By the end of our procedure with probability 1 the undirected edges contain no cycle, so they span a disjoint union of even degree trees. We can randomly orient these trees by choosing a root in each component: for example the closest one to $o$ in $G$, or if there are multiple ones, then picking one uniformly at random. Then we use the random orientation described in Subsection~\ref{subsection:orienting_trees} for the rooted trees. We call the random balanced orientation of $(G,o)$ described above the \emph{canonical} random balanced orientation of $(G,o)$. The distribution on the edges does not depend on the choice of $o$. This is obvious for the cycle removal, and the random orientation of the trees was shown to be invariant under changing the root. In the next subsection we show how the canonical random orientation allows us to build a measurably orientable graphing for any unimodular random network. \subsection{Constructing orientable graphings} \label{subsection:constructing_graphings} Theorem~\ref{theorem:representing_graphing} states that any unimodular random network can be represented by a graphing. The construction thoroughly explained in~\cite[Theorem~18.37]{lovasz2012large} can be adapted to our situation. We outline our construction and the key ideas, but do not burden the reader with lengthy exposition. The set of vertices of our graphing will be the space of $2d$-regular, oriented, connected rooted graphs with labels from $[0,1]$ on each vertex. That is, every node is a $2d$-regular rooted graph $(H,v)$ with an orientation $\orl: E(H) \to V(H)$ and a vertex labeling $l: V(H) \to [0,1]$. Let $\GoG^{\orl,\,l}_{\circ}$ denote the set of such quadruples. The Borel structure is generated by the following cylinder sets: for any $r \geq 0$, we fix the oriented isomorphism type of the ball with radius $r$ about the root, and also for every vertex in the ball we specify a Borel set in $[0, 1]$ from which the weight is to be chosen. For a node $(H,v,\orl, l)$ we introduce an edge to the nodes $(H,v',\orl, l)$, where $v'$ runs through the neighbors of $v$ in $H$. In other words, $(H,v,\orl, l)$ and $(H',v',\orl ', l')$ are connected if there is an isomorphism (of unrooted graphs) $\eta: H \to H'$, that preserves the orientation and the vertex labels, and $\eta(v) \sim_{H'} v'$. (The $\sim_G$ symbol indicates being neighbors in the graph $G$.) Starting from a unimodular measure $\mu$ on $\GoG_{\circ}^{2d}$ we construct a measure $\bar{\mu}$ on $\GoG^{\orl,\,l}_{\circ}$. We first choose $(G,o)$ according to $\mu$, then put i.i.d.\ $[0,1]$ labels on the vertices, and randomize an orientation according to the canonical balanced orientation of $(G,o)$. \begin{prop}\label{proposition:orientable_graphing} The Borel graph $\GoG^{\orl,\,l}_{\circ}$ with the measure $\bar{\mu}$ is a graphing, and it represents the unimodular random rooted graph $\mu$. Moreover, it has a measurable balanced orientation. \end{prop} \begin{proof} The measure $\bar{\mu}$ will be involution invariant on $\GoG^{\orl,\,l}_{\circ}$, because $\mu$ is involution invariant on $\GoG_{\circ}^{2d}$, and both the orientation an the labels are chosen in a way that is in distribution the same regardless of the position of the root. This makes sure that $(\GoG^{\orl,\,l}_{\circ}, \bar{\mu})$ is indeed a graphing. The labeling breaks all symmetries of $(G,o, \orl)$ almost surely, which makes sure that $(\GoG^{\orl,\,l}_{\circ}, \bar{\mu})$ represents $\mu$. Finally by construction the edges of $\GoG^{\orl,\,l}_{\circ}$ can be measurably oriented. The edge between $(H,v,\orl, l)$ and $(H,v',\orl, l)$ is oriented towards $(H,v,\orl, l)$ if and only if $(v,v')$ is oriented towards $v$ in $(H,v,\orl)$. \end{proof} %\medskip This finishes the proof of Theorem~\ref{theorem:balanced_orientation}. \section{Measurable colorings of bipartite graphings} \label{section:coloring} In this section we prove Theorem~\ref{theorem:almost_proper_coloring}. We will repeatedly make use of two results of Csóka, Lippner and Pikhurko~\cite[Theorems~1.9 and 4.2]{csoka2016kHonig}. Their main result is the following \begin{theo}\label{theorem:CSLP_main} For every $d \geq 1$ there is $r_0 = r_0(d)$ such that if $\G = (X_1, X_2,E,\linebreak\nu)$ is a bipartite graphing with maximum degree at most $d + 1$ such that the set $J$ of vertices of degree $d + 1$ is $r_0$-sparse, then there is a measurable proper edge coloring of $\G$ with $d+1$ colors. \end{theo} During the proof of Theorem~\ref{theorem:CSLP_main} they use the following theorem as an inductive step. \begin{theo}\label{theorem:CSLP_induction} For every $d > 2$ and $r > 1$, there is $r_1 = r_1(d, r)$ such that the following holds. Let $\G = (X_1,X_2, E, \nu)$ be a bipartite graphing with degree bound $d + 1$ that has no finite components. If the set $J \subseteq X_1 \cup X_2$ of vertices of degree $d + 1$ is $r_1$-sparse, then there is a Borel matching $M$ such that, up to removing a null-set, $\G \setminus M$ has maximum degree at most $d$ and its set of degree-$d$ vertices is $r$-sparse. \end{theo} We will follow the induction and make sure the color $(d+1)$ is used rarely. Note that vertices of high degree being sparse does not immediately imply that they have small density, there might be small connected components. However, if a component contains at least 2 such vertices, then the density can be bound in terms of the sparsity. Ruling out components with exactly one high degree vertex is key to our proof of Theorem~\ref{theorem:almost_proper_coloring}. %\medskip We start by proving two lemmas to take care of finite components in graphings. \begin{lemm}\label{lemma:finite_smart_coloring} Let $G=(S,T,E)$ be a finite bipartite graph with degrees bounded by $(d+1)$, and such that \begin{enumerate} \item \label{condition:bad_points_sparse} the vertices of degree $(d+1)$ are 3-sparse, and \item there are at most $\rho \cdot |V(G)|$ vertices of degree $(d+1)$ in total, $(0 \leq \rho \leq 1)$. \end{enumerate} Then there is a proper edge coloring of $G$ with $(d+1)$ colors such that there are at most $\rho \cdot |V(G)|$ edges of color $(d+1)$. \end{lemm} \begin{proof} For each vertex of degree $(d+1)$ choose an arbitrary adjacent edge and color it with $(d+1)$. As these points are 3-sparse, this coloring is so far proper. We colored at most $\rho \cdot |V(G)|$ edges with color $(d+1)$. The remaining graph has degrees at most $d$, so by Kőnig's line coloring theorem it can be properly colored with $d$ colors. Notice that if $\rho=0$ the statement is simply Kőnig's theorem. \end{proof} %\medskip \begin{lemm}\label{lemma:finite_components_smart_coloring} Let $\G=(X_1,X_2,E, \nu)$ be a bipartite graphing with all connected components finite and satisfying the conditions of Lemma~\ref{lemma:finite_smart_coloring}. Then it has a Borel proper edge coloring with $(d+1)$ colors such that the $\widetilde{\nu}$-measure of edges of color $(d+1)$ is at most $\rho$. \end{lemm} \begin{proof} For $i=1,2,\,\dots$ we edge color the components with exactly $i+1$ vertices. For each $i$ we fix an $i$-sparse Borel labeling $l: X_1 \cup X_2 \to [k_i]$. In components of size $i+1$ all vertices have different label. For each isomorphism type of such labeled graphs choose a way to color its edges as in Lemma~\ref{lemma:finite_smart_coloring}, and apply this coloring consistently everywhere. At each step the color classes are Borel, and there are countably many steps, so the color classes in the end are also Borel. At each step the measure of edges colored by $(d+1)$ is at most $\rho$ times the measure of vertices with components of size $i+1$. As $\mu(X_1 \cup X_2) = 1$, the measure of edges colored $(d+1)$ in the end is at most $\rho$. \end{proof} \begin{rema*} Lemma~\ref{lemma:finite_components_smart_coloring} can also be proved using uniformization, specificly the Lusin-Novikov Uniformization Theorem. \end{rema*} The following proposition is the first step of our inductive procedure to prove Theorem~\ref{theorem:almost_proper_coloring}. \begin{prop}\label{proposition:induction_start} Let $\G=(X_1,X_2,E, \nu)$ be a bipartite graphing with degrees $2$ or $3$. Assume that the vertices of degree~$3$ are $r$-sparse for $r \geq r_0(3)$, where $r_0$ is the constant from Theorem~\ref{theorem:CSLP_main}. Then it has a measurable proper edge coloring with 3 colors such that the $\widetilde{\nu}$-measure of edges of the 3rd color is at most $4/r$. \end{prop} \begin{proof} We will use 3 colors: red, blue and purple, with as few purple edges as possible. It suffices to prove the theorem when $\G$ only has finite components, and also when it only has infinite components. In general $\G$ can be split into two measurable parts according to the components being finite or infinite, and measurably coloring each side with few purple edges. %\smallskip \paragraph{Suppose all components are finite} Finite components that contain no vertices of degree~3 are even cycles, and can be properly edge-colored with red and blue, no purple edges needed. We also claim that finite components that contain a degree~3 vertex contain at least two. Indeed, the sum of degrees has to be even. This implies that the size of such a finite component is at least $r+1$, as degree~3 vertices are $r$-sparse. We claim that the density of degree~3 vertices is at most $2/r$. Indeed, because of the sparsity the balls of radius $r/2$ around the degree~3 points are disjoint, and these balls contain at least $r/2$ points each. By Lemma~\ref{lemma:finite_components_smart_coloring} we have a Borel proper edge coloring with only $2/r$ proportion of edges colored purple. %\smallskip \paragraph{Now assume that all components are infinite.} We simply apply Theorem~\ref{theorem:CSLP_main}. We get a measurable proper edge coloring $c:E \to \{\redl, \bluel, \purpll\}$. We will modify this coloring in finitely many steps so that purple edges become sparse. Call a purple edge \emph{standard}, if both of its endpoints have degree~2. Our procedure will consist of $r+1$ steps. In step 0 we will make sure that the neighbors of standard purple edges have different color. Standard purple edges that are between two blue edges can be recolored red. We will now argue that this recoloring maintains measurability. Let $R$, $B$, and $P$ denote the edge sets $c^{-1}(\{\redl\})$, $c^{-1}(\{\bluel\})$, and $c^{-1}(\{\purpll\})$ respectively. For a measurable set of edges $F$ let $V_F$ denote the set of endpoints of $F$, that is \[ V_F=\left\{x \in X_1 \cup X_2~\middle|~\exists y \in X_1 \cup X_2\, \text{ s.t. } (x,y) \in F\right\}. \] If $F$ is Borel, then so is $V_F$ since degrees in $\G$ are finite. Moreover, $\widetilde{\nu}(F)=0$ implies $\nu(V_F)=0$ by the definition of $\widetilde{\nu}$. Consequently if $F$ is $\widetilde{\nu}$-measurable, then $V_F$ is $\nu$-measurable. Let $A \subseteq X_1 \cup X_2$ denote the set of vertices that are the endpoints of a blue and a standard purple edge. Measurability of $A$ is shown by $A=V_{P} \cap V_{B} \setminus V_R$. The set of standard purple edges between two blue edges is $A^2 \cap P$, which is measurable. Therefore the recoloring preserves measurability. Similarly, standard purple edges between two red edges can be recolored blue. This finishes step 0. Generally for $n\geq 1$, during step $n$ we make sure that there are no standard purple edges at distance at most $n$. Since steps 1 through $n-1$ are already done, a path between two standard purple edges at distance $n$ is colored by red and blue in an alternating way. Step 0 has made sure that the neighbors of these purple edges are colored differently. \begin{figure}[h] \centering \begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm] \clip(-0.5,-1.) rectangle (12.5,1.); \draw [line width=1.pt,color=qqqqff] (4.,0.)-- (6.,0.); \draw [line width=1.pt,color=ffqqqq] (6.,0.)-- (8.,0.); \draw [line width=1.pt,color=yqqqyq] (4.,0.)-- (2.,0.); \draw [line width=1.pt,color=ffqqqq] (2.,0.)-- (0.,0.); \draw [line width=1.pt,color=yqqqyq] (8.,0.)-- (10.,0.); \draw [line width=1.pt,color=qqqqff] (10.,0.)-- (12.,0.); \draw [color=qqqqff](4.6,-0.2) node[anchor=north west] {\text{blue}}; \draw [color=yqqqyq](2.35,-0.2) node[anchor=north west] {\text{purple}}; \draw [color=qqqqff](10.6,-0.2) node[anchor=north west] {\text{blue}}; \draw [color=yqqqyq](8.35,-0.2) node[anchor=north west] {\text{purple}}; \draw [color=ffqqqq](6.7,-0.2) node[anchor=north west] {\text{red}}; \draw [color=ffqqqq](0.7,-0.2) node[anchor=north west] {\text{red}}; \begin{scriptsize} \draw [color=black] (4.,0.) circle (2pt); \draw [color=black] (6.,0.) circle (2pt); \draw [color=black] (8.,0.) circle (2pt); \draw [fill=black] (2.,0.) circle (2pt); \draw [color=black] (0.,0.) circle (2pt); \draw [color=black] (10.,0.) circle (2pt); \draw [color=black] (12.,0.) circle (2pt); \end{scriptsize} \end{tikzpicture} \caption{Path between standard purple edges at distance 2.}\label{figure:local_picture_2} \end{figure} So swapping the colors on the path between the purple edges results in them having neighbors of the same color, and then we can recolor them red or blue according to the color of their neighbors. The case of $n=2$ is illustrated in Figures~\ref{figure:local_picture_2} and~\ref{figure:local_picture_better_2}. \begin{figure}[h] \centering \definecolor{yqqqyq}{rgb}{0.5019607843137255,0.,0.5019607843137255} \definecolor{ffqqqq}{rgb}{1.,0.,0.} \definecolor{qqqqff}{rgb}{0.,0.,1.} \begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm] \clip(-0.5,-1.) rectangle (12.5,1.); \draw [line width=1.pt,color=ffqqqq] (0.,0.)-- (2.,0.); \draw [line width=1.pt,color=qqqqff] (2.,0.)-- (4.,0.); \draw [line width=1.pt,color=ffqqqq] (4.,0.)-- (6.,0.); \draw [line width=1.pt,color=qqqqff] (6.,0.)-- (8.,0.); \draw [line width=1.pt,color=ffqqqq] (8.,0.)-- (10.,0.); \draw [line width=1.pt,color=qqqqff] (10.,0.)-- (12.,0.); \draw [color=ffqqqq](0.7,-0.2) node[anchor=north west] {\text{red}}; \draw [color=qqqqff](2.6,-0.2) node[anchor=north west] {\text{blue}}; \draw [color=ffqqqq](4.7,-0.2) node[anchor=north west] {\text{red}}; \draw [color=qqqqff](6.6,-0.2) node[anchor=north west] {\text{blue}}; \draw [color=ffqqqq](8.7,-0.2) node[anchor=north west] {\text{red}}; \draw [color=qqqqff](10.6,-0.2) node[anchor=north west] {\text{blue}}; \begin{scriptsize} \draw [color=black] (4.,0.) circle (2pt); \draw [color=black] (6.,0.) circle (2pt); \draw [color=black] (8.,0.) circle (2pt); \draw [fill=black] (2.,0.) circle (2pt); \draw [color=black] (0.,0.) circle (2pt); \draw [color=black] (10.,0.) circle (2pt); \draw [color=black] (12.,0.) circle (2pt); \end{scriptsize} \end{tikzpicture} \caption{Path recolored.}\label{figure:local_picture_better_2} \end{figure} As before, we do not loose measurability. We execute steps $0,1,\,\ldots,\,r$, and estimate the measure of purple edges at the end. Purple edges are either standard, or have an endpoint of degree~3. We divide the set $P = \{e \in E~|~c(e)=``\purpll''\}$ accordingly: $P_1=\{e \in P~|~e \text{ is standard}\}$, $P_2= P\setminus P_1 =\{ e=(x,y) \in P~|~\deg(x)=3 \text{ or } \deg(y)=3\}$. As points of degree~3 are $r$-sparse in infinite components they have measure at most $2/r$. Each such point has exactly one edge from $P_2$, so $\widetilde{\nu}(P_2) \leq 2/r$. Edges in $P_1$ are also $r$-sparse, so $\widetilde{\nu}(P_1) \leq 2/r$. We indeed proved that $\widetilde{\nu}(P) \leq 4/r$. \end{proof} %\medskip \begin{proof}[Proof of Theorem~\ref{theorem:almost_proper_coloring}] The idea is to use Theorem~\ref{theorem:CSLP_induction} $(d-2)$ times to remove matchings from the edge set, coloring each one with a unique color. Whenever removing those matchings creates finite components we color those using Lemma~\ref{lemma:finite_components_smart_coloring}. In the end we will apply Proposition~\ref{proposition:induction_start} to the remaining graphing. Instead of re-normalizing every time we split our graphings, we will talk about \emph{density} of $(d+1)$-color edges. This means their $\widetilde{\nu}$-measure divided by the $\nu$-measure of the vertex set of the graphing in question. At each step the density of $(d+1)$-color edges will be at most $\varepsilon$, so in the end their density will still be at most $\varepsilon$, and this coincides with their $\widetilde{\nu}$-measure. To be precise we start by picking $r_2 \geq r_0(3)$ such that $4/r_2 \leq \varepsilon$. Looking to apply Theorem~\ref{theorem:CSLP_induction} repeatedly we define $r_i \geq r_1(i, r_{i-1})$ for $i=3,\,\ldots\,d$, also assuming $r_{i-1} \leq r_i$. The graphing $\G$ has no vertices of degree $(d+1)$, so in particular vertices of degree $(d+1)$ are $r_d$-sparse. The finite components can be colored with $[d]$ using Lemma~\ref{lemma:finite_components_smart_coloring} (choosing $\rho =0$). So without loss of generality we can assume that all components are infinite. Then $\G$ satisfies the conditions of Theorem~\ref{theorem:CSLP_induction}, so we find a measurable matching $M_1 \subseteq E(\G)$, such that the set of vertices of degree $d$ in $\G_1=\G \setminus M_1$ is $r_{d-1}$-sparse. We color $M_1$ with color $d$, and turn our attention to $\G_1$. Notice that all degrees in $\G_1$ are either $d$ or $d-1$. We claim that all finite components of $\G_1$ that contain a vertex of degree $d$ contain at least two. Assume towards contradiction that there was a finite component $G=(S,T, E')$, with a unique vertex $x$ of degree $d$. Without loss of generality we can assume $x \in S$. Double counting the edges we get $(d-1)|S|+1 = (d-1)|T|$, which is not possible if $d \geq 3$, as the right hand side is divisible by $(d-1)$, while the left hand side is not. This proves our claim. This rules out small components with vertices of degree $d$. We use this to argue that in the finite components vertices of degree $d$ are not only sparse, but have small density as well. Components having degree $d$ vertices have size at least $r_{d-1}+1$, since they have at least two vertices at distance at least $r_{d-1}$. The $r_{d-1}/2$ balls around degree $d$ vertices are disjoint, and have size at least $r_{d-1}/2$ as the component has at least $r_{d-1}+1$ points. So the density of degree $d$ points in finite components of $\G_1$ is at most $2 / r_{d-1}$. We split $\G_1$ into the disjoint union $\G_1 = \F_1 \cup \G'_1$, where $\F_1$ is the part with finite components, and $\G'_1$ is the one with infinite components. To $\F_1$ we apply Lemma~\ref{lemma:finite_components_smart_coloring} with $\rho = 2 / r_{d-1} \leq 4 / r_2 \leq \varepsilon$. We use the colors $\{1,\,\ldots,\,d-1\}$ for most edges, and $(d+1)$ with density at most $\varepsilon$. To $\G'_1$ we apply Theorem~\ref{theorem:CSLP_induction}, and find a measurable matching $M_2$ such that $\G_2 = \G'_1 \setminus M_2$ has maximum degree $(d-1)$, and degree $(d-1)$ vertices in $\G_2$ are $r_{d-2}$-sparse. We color $M_2$ with color $d-1$. Notice that all vertices in $\G_2$ are of degree either $d-2$ or $d-1$. As long as $i