%~Mouliné par MaN_auto v.0.25.0 2022-02-10 13:28:44
\documentclass[AHL,Unicode,longabstracts,published]{cedram}





\DeclareMathOperator{\Corr}{\mathbf{Corr}}


\DeclareMathOperator{\out}{out}
\DeclareMathOperator{\inn}{in}
\DeclareMathOperator{\dom}{dom}
\DeclareMathOperator{\E}{\mathrm{E}}


\newcommand{\fE}{\operatorname{E}}


\newcommand{\bfa}{\mathbf{a}}
\newcommand{\clG}{\mathcal{G}}
\newcommand{\clB}{\mathcal{B}}
\newcommand{\clH}{\mathcal{H}}
\newcommand{\clD}{\mathcal{D}}
\newcommand{\clE}{\mathcal{E}}
\newcommand{\clC}{\mathcal{C}}
\newcommand{\clP}{\mathcal{P}}
\newcommand{\clQ}{\mathcal{Q}}

\newcommand{\bbZ}{\mathbb{N}}
\newcommand{\bbN}{\mathbb{N}}

\newcommand{\frkP}{\mathfrak{P}}
\newcommand{\frkM}{\mathfrak{M}}
\newcommand{\frkT}{\mathfrak{T}}
\newcommand{\frks}{\mathfrak{s}}
\newcommand{\frkC}{\mathfrak{C}}
\newcommand{\frkD}{\mathfrak{D}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\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}}
\let\oldforall\forall
\renewcommand*{\forall}{\mathrel{\oldforall}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title[Approximate Schreier decorations and approximate K{\H o}nig's line coloring Theorem]{Approximate Schreier decorations and approximate K{\H o}nig's line coloring Theorem}

\alttitle{Décorations de Schreier approchées et un théorème de coloriage de lignes de K{\H o}nig approché}

\subjclass{37A50, 03E15, 20E05, 05C15, 28A05}
\keywords{Schreier decoration, Borel graphs, local-global equivalence, edge colorings}



\author[\initial{J.} \lastname{Greb{\'I}k}]{\firstname{Jan} \lastname{Greb{\'I}k}}
\address{Mathematics Institute,\\
University of Warwick,\\
Coventry, CV4 7AL  (United Kingdom)}
\email{jan.grebik@warwick.ac.uk}

\thanks{The author was supported by Leverhulme Research Project Grant RPG-2018-424.}



\begin{abstract}
Following recent result of L.~M.~T{\'o}th~\cite[\emph{Annales Henri Lebesgue}, Volume~4 (2021)]{Laszlo} we show that every $2\Delta$-regular Borel graph $\clG$ with a (not necessarily invariant) Borel probability measure admits approximate Schreier decoration. In fact, we show that both ingredients from the analogous statements for finite graphs have approximate counterparts in the measurable setting, i.e., approximate K{\H o}nig's line coloring Theorem for Borel graphs without odd cycles and approximate balanced orientation for even degree Borel graphs.
\end{abstract}

\begin{altabstract}
À la suite d'un récent résultat de L.~M.~T{\'o}th~\cite[\emph{Annales Henri Lebesgue}, Volume~4 (2021)]{Laszlo}, nous montrons que tout graphe borélien $\clG$, $2\Delta$-régulier et muni d'une mesure de probabilité borélienne (pas nécessairement invariante) admet une décoration de Schreier approchée. En réalité, nous montrons que les deux ingrédients correspondants pour les graphes finis ont des analogues approchés dans le cadre mesurable, \emph{i.e.}, un théorème de coloriage de lignes de K{\H o}nig approché pour les graphes boréliens sans cycle impair, et une orientation équilibrée approchée pour les graphes boréliens de degré pair.
\end{altabstract}

\datereceived{2020-05-27}
\daterevised{2021-06-18}
\dateaccepted{2021-08-20}

\editor{D. Aldous}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{DefTralics}
\newcommand{\clG}{\mathcal{G}}
\end{DefTralics}


%%%%%%%%%%%%%%%%%%%%
\dateposted{2022-05-04}
\begin{document}
\maketitle


\section{Introduction}

It is a standard fact from finite combinatorics, known as Petersen's $2$-factor theorem, that every $2\Delta$-regular finite graph is a Schreier graph of the free group $F_\Delta$ on $\Delta$ generators. That is, every such graph admits an orientation and a $\Delta$-labeling of edges such that for every $\alpha\in \Delta$ and every vertex there is exactly one out-edge with label $\alpha$ and exactly one in-edge with label $\alpha$. Such an orientation and labeling is called a \emph{Schreier decoration}. Note that every Schreier decoration corresponds to an action of the free group $F_{\Delta}$ on the vertex set of the graph. We refer the reader to the introduction in~\cite{Laszlo} for more information about Schreier decorations.

The analogous statement for infinite graphs without any restriction on definability follows from the axiom of choice. In the measurable setting, i.e., when the vertex set is endowed with a standard probability (Borel) structure and we require the orientation and labeling to be measurable, the full analogue of the statement fails. This follows from the example of Laczkovich~\cite{Laczkovich} who constructed an acyclic $2$-regular bipartite graph on the unit interval that is not induced by an action of $\bbZ$ on any set of full measure. However, Tóth recently proved~\cite{Laszlo} that if the measure is invariant one can always find a measurable Schreier decoration on a different graph that has the same local statistics. This can be stated in a compact form as follows: every $2\Delta$-regular unimodular random rooted graph has an invariant random Schreier decoration, see~\cite[Theorem~1]{Laszlo}. An equivalent formulation in a language that is closer to the one in this paper is as follows, see~\cite[Corollary~4]{Laszlo}: Every $2\Delta$-regular graphing $(\clG,\mu)$ is a local isomorphic copy of some graphing $(\clG',\mu')$ that is induced by a Borel action of $F_\Delta$ that preserves $\mu'$.

The key steps in the proof of~\cite[Theorem~1]{Laszlo} are
\begin{enumerate}\Romanenumi
\item\label{IntroI} a consequence of~\cite[Theorem~3]{Laszlo}: for every $\Delta$-regular bipartite graphing $(\clG,\mu)$ and for every $\epsilon>0$ there is a Borel map $c:E\to \Delta$ that is a proper edge coloring on a set of $\mu$-measure at least $1-\epsilon$,
\item\label{IntroII} \cite[Theorem~2]{Laszlo}: every $2\Delta$-regular unimodular random rooted graph admits a graphing representation $(\clG,\mu)$ that admits measurable balanced orientation, where an orientation is \emph{balanced} if the in-degree is equal to out-degree at any vertex.
\end{enumerate}

The main purpose of this paper is to provide short and straightforward proofs of~\eqref{IntroI} and an approximate version of~\eqref{IntroII} that hold for any bounded degree Borel graph with any Borel probability measure. This implies immediately that every\linebreak $2\Delta$-regular graphing admits an approximate Schreier decoration. As a consequence of the ultrapower technique one can get a strengthening of~\cite[Corollary~4]{Laszlo}, and consequently~\cite[Theorem~1]{Laszlo}, see Section~\ref{sec:5}.

Recall that a \emph{Borel graph} is a triple $\clG=(V,\clB,E)$ where $(V,\clB)$ is a standard Borel space, $(V,E)$ is a graph and $E\subseteq V\times V$ is a Borel symmetric set in the product Borel structure. We denote as $\Delta(\clG)$ the maximum degree of $\clG$ and we say that $\clG$ is of \emph{bounded degree} if $\Delta(\clG)\in \bbZ$. An \emph{orientation} $S$ of $\clG$ is a Borel set $S\subseteq E$ such that for every $x,y\in V$ that form an edge in $E$ exactly one of $(x,y)$ or $(y,x)$ is in $S$. We define $\out_S(v)=\{(v,x)\in S\}$, $\inn_S(v)=\{(x,v)\in S\}$ and $\Corr(S)=\{v\in V:|\inn_S(v)|=|\out_S(v)|\}$.

Let $k\in \bbZ$. A partial Borel map $c;E\to k$ is called a \emph{partial edge coloring} if $\dom(c)\subseteq E$ is a Borel set and $c(x,y)=c(y,x)$ whenever $(x,y)\in \dom(c)$. We say that $c$ is \emph{proper} if $c(x,y)\not =c(x,z)$ for every $(x,y)\not=(x,z)\in \dom(c)$. For a partial edge coloring $c$ we define $x\in \Corr(c)$ if $(x,y)\in\dom(c)$ for every $(x,y)\in E$ and $c(x,y)\not =c(x,z)$ for every $(x,y)\not=(x,z)\in \dom(c)$. In another words, $x\in \Corr(c)$ if edges adjacent to $x$ are in $\dom(c)$ and the restriction of $c$ to these edges is a proper edge coloring. When $\dom(c)=E$, then we say that $c$ is an \emph{edge coloring}.

A pair $(S,c)$, where $S$ is an orientation and $c;E\to k$ is a partial edge coloring, is called a \emph{partial Schreier decoration}. Define $v\in \Corr(S,c)$ if $v\in \Corr(S)$ and $c$ is injective when restricted to both $\inn_S(v)$ and $\out_S(v)$. If $\clG$ is $2\Delta$-regular, then we say that $(S,c)$ is a \emph{Schreier decoration} if $c:E\to \Delta$ and $\Corr(S,c)=V$.

With this notation it is easy to see that $S$ is a \emph{balanced orientation} if $\Corr(S)=V$ and $c:E\to k$ is a proper edge coloring if $\Corr(c)=V$.

\begin{defi}
Let $\clG$ be a Borel graph of bounded degree. The \emph{approximate chromatic index} of $\clG$, in symbols $\chi'_{App}(\clG)$, is defined as the minimal $k\in \bbZ$ such that for every Borel probability measure $\mu$ and every $\epsilon>0$ there is an edge coloring $c:E\to k$ such that
\[
\mu\left(\Corr(c)\right)>1-\epsilon.
\]

We say that $\clG$ admits \emph{approximate balanced orientation} if for every Borel probability measure $\mu$ and every $\epsilon>0$ there is an orientation $S$ of $\clG$ such that
\[
\mu\left(\Corr(S)\right)>1-\epsilon.
\]

If $\clG$ is $2\Delta$-regular, then we say that $\clG$ admits \emph{approximate Schreier decoration} if for every Borel probability measure $\mu$ and every $\epsilon>0$ there is a partial Schreier decoration $(S,c)$ of $\clG$ where $c;E\to \Delta$ such that
\[
\mu\left(\Corr(S,c)\right)>1-\epsilon.
\]
\end{defi}

It follows from~\cite[Theorem~1.8]{Vizing} that $\chi'_{App}(\clG)\le
\Delta(\clG)+1$ for any bounded degree Borel graph $\clG$. This is the corresponding approximate version of Vizing's Theorem. Since we use this result in the proof of the approximate version of Kőnig line coloring Theorem (Theorem~\ref{th:main}$\MK$\eqref{theo1.2.I}) we would like to stress that its proof is significantly easier than the main result of~\cite[Theorem~1.6]{Vizing}. In particular, the combinatorial idea reflects the proof of the Vizing's Theorem for finite graphs in the same way as the proof of Theorem~\ref{th:main}$\MK$\eqref{theo1.2.I} reflects the proof of Kőnig's line coloring Theorem for finite bipartite graphs.

The result~\eqref{theo1.2.I}, a consequence of~\cite[Theorem~3]{Laszlo}, mentioned above is equivalent to saying that if we restrict our attention only to \emph{invariant} probability measures, then the approximate chromatic index of a bipartite $\Delta$-regular Borel graph is $\Delta$.

\begin{theo}\label{th:main}
Let $\clG=(V,\clB,E)$ be a bounded degree Borel graph.
\begin{enumerate}\Romanenumi
\item\label{theo1.2.I} Suppose that $\clG$ is bipartite. Then $\chi'_{App}(\clG)=\Delta(\clG)$.
\item\label{theo1.2.II} Every vertex of $\clG$ has even degree if and only if $\clG$ admits approximate balanced orientation.
\item\label{theo1.2.III} Suppose that $\clG$ is $2\Delta$-regular where $\Delta\in \bbZ$. Then $\clG$ admits approximate Schreier decoration.
\end{enumerate}
\end{theo}

Note that $\clG$ being bipartite is the same as saying that $\clG$ does not contain odd cycles. This is strictly weaker then $\clG$ being a Borel bipartite Borel graph.

Moreover, it will be obvious from the proof that in~\eqref{theo1.2.II} we can get a somewhat stronger statement: there is a sequence $\{S_n\}_{n\,\in\,\bbZ}$ of orientations such that $\mu(\Corr(S_n))\to 1$ for every Borel probability measure $\mu$ and $\mu(\Corr(S_n))\ge 1-\tfrac{1}{n}$ for every $\clG$-invariant measure $\mu$. Similarly, one can modify the proof of~\eqref{theo1.2.I} to get that there is a sequence of Borel colorings $\{c_n:E\to \Delta(\clG)\}_{n\,\in\,\bbZ}$ such that $\mu(\Corr(c_n))> 1-\tfrac{1}{n}$ for every $\clG$-invariant Borel probability measure $\mu$. Consequently, in~\eqref{theo1.2.III} there is a sequence $(S_n,c_n)$ of Schreier decorations such that $\mu(\Corr(S_n,c_n))>1-\tfrac{1}{n}$ for every $\clG$-invariant measure $\mu$. This follows from the same principle as the result of Elek and Lippner about a sequence of matchings without short augmenting paths, see~\cite{ElekLippner}.

\begin{rema}
Recently, Kun constructed $\Delta$-regular acyclic measurable bipartite graphing that does not admit bounded measurable circulation~\cite[Theorem~1]{Kun} for every $\Delta\ge 2$. This shows that~\eqref{theo1.2.I}, that is, Kőnig's line coloring theorem, \eqref{theo1.2.II} and, consequently, \eqref{theo1.2.III}, that is, the existence of a Schreier decoration, do not admit full measurable analogue for every $\Delta\ge 2$.
\end{rema}



\section*{Acknowledgement}
The author would like to thank Oleg Pikhurko and László Martón Tóth for\linebreak insightful conversations, and the anonymous referee for providing helpful suggestions.



\section{Preliminaries}

Let $\clG=(V,\clB,E)$ be a bounded degree Borel graph. Given a vertex $v\in V$, we write $N(v)\subseteq E$ for the set of edges adjacent to $v$, $N_0(v)\subseteq V$ for the set of neighbors of $v$, and $[v]_\clG$ for the \emph{$\clG$-connected component} of $v$. A set $A\subseteq V$ is \emph{$k$-sparse}, where $k\in \bbZ$, if every $x\not=y\in A$ are at least $k$ apart in the graph distance. A \emph{$\clG$-saturation} of a set $A\subseteq V$, denoted as $[A]_\clG$, is the union of $\clG$-connected components of elements from $A$. A set $A\subseteq V$ is \emph{$\clG$-invariant} if $A=[A]_{\clG}$. We denote as $F_\clG$ the countable Borel equivalence relation on $V$ that is generated by $E$.

A Borel probability measure $\mu$ on $(V,\clB)$ is called \emph{$\clG$-quasi-invariant} if for every $A\in \clB$ we have $\mu(A)=0$ if and only if $\mu([A]_\clG)=0$. We denote as $\rho_\mu:F_\clG\to (0,+\infty)$ the corresponding cocycle, see~\cite[Proposition~8.3]{KechrisMiller}, i.e., a Borel map that satisfies
\[
\mu(B)=\int_A \rho_\mu(\psi(v),v) \ d\mu
\]
for every $A,B\in \clB$ and a Borel bijection $\psi:A\to B$ such that $\psi(v)\in [v]_\clG$ for every $v\in A$. Moreover, $\mu$ is called \emph{$\clG$-invariant}, if $\rho_\mu=1$ when $F_\clG$ is restricted to some $\clG$-invariant $\mu$-conull set.


\begin{enonce}{Claim}[{\cite[Proposition~3.2]{Vizing}\label{cl:quasi invariant}}]
Let $\clG=(V,\clB,E)$ be a bounded degree Borel graph and $\mu$ be a Borel probability measure on $(V,\clB)$. Then there is a $\clG$-quasi-invariant Borel probability measure $\nu$ on $(V,\clB)$ that satisfies $\mu(A)\le 2\nu(A)$ for every $A\in \clB$.
\end{enonce}


We denote as $\clE=(\fE,\clC,I_\clG)$ the corresponding \emph{line graph}. That is, $\fE$ is the set of edges of $\clG$ viewed as unordered pairs, $\clC$ is the $\sigma$-algebra inherited from $[V]^2$ and $(e,f)\in I_{\clG}$ if $e\cap f\not =\emptyset$. It is easy to see that $\clE=(\fE,\clC,I_\clG)$ is a bounded degree Borel graph. Note that here we make a formal distinction between edges as ordered pairs $E$ and edges as unordered pairs $\fE$. However, in next sections we abuse the notation and write simply $E$ instead of $\fE$.

\begin{enonce}{Claim}[{\cite[Proposition~3.1]{Vizing}\label{cl:measure on edges}}]
Let $\clG=(V,\clB,E)$ be a bounded degree Borel graph and $\mu$ be a Borel probability measure on $(V,\clB)$. Then there is a Borel probability measure $\eta$ on $(\fE,\clC)$ that satisfies
\[
\mu\left(\{v\in V :\,\exists e\in A \, v\in e\}\right)\le \Delta(\clG)\eta(A)
\]
for every $A\in \clC$. Moreover, if $\mu$ is $\clG$-invariant (quasi-invariant), then $\eta$ is $\clE$-invariant (quasi-invariant).
\end{enonce}



\section{Approximate Kőnig's line coloring Theorem}

Let $c;E\to (\Delta(\clG)+1)$ be a proper partial edge coloring. We put
\[
m_c(v)=(\Delta(\clG)+1)\setminus \{c(e):e\in N(v)\}
\]
for the set of colors missing at $v\in V$. Note that $m_c(v)$ is always non-empty. We fix a distinguished color $\bfa\in (\Delta(\clG)+1)$. If $\beta,\gamma\in (\Delta(\clG)+1)$ and $v\in V$, then we write $P^c_{\beta/\gamma}(v)=(f_0,f_1,\,\dots)$ for the unique (finite or infinite) alternating $\beta/\gamma$-path that starts in $v$, i.e., $c(f_0)=\beta$, $c(f_1)=\gamma$, etc. In the case that $\beta=\gamma$ we let $P^c_{\beta/\gamma}(v)$ to be either an edge of color $\beta$ adjacent to $v$ or the empty sequence if such an edge does not exist.

Let $e\in E$ be such that $c(e)=\bfa$. Using~\cite[Theorem~18.10]{Kec} we find a Borel function that assigns to $e$ one of its endpoints $v(e)$ and colors $\beta(e),\gamma(e)\in (\Delta(\clG)+1)\linebreak\setminus \{\bfa\}$ such that $\gamma(e)\in m_c(v(e))$ and $\beta(e)\in m_c(w)$ where $e=(v(e),w)$. We put $P^c(e)=e^\frown P^c_{\beta(e)/\gamma(e)}(v(e))=(e,f_0,f_1,\,\dots)$. Note that $w$ is either the last vertex of $P^c(e)$, i.e., $P^c(e)$ is a cycle, or it does not appear in $P^c_{\beta(e)/\gamma(e)}(v(e))$.

Let $d;E\to (\Delta(\clG)+1)$ be a proper partial edge coloring. We say that $d$ \emph{improves} $c$ if $\dom(d)=\dom(c)$ and $d^{-1}(\bfa)\subseteq c^{-1}(\bfa)$. A particular way how to find $d$ that improves $c$ is as follows. Let $e\in E$ be such that $c(e)=\bfa$ and suppose that the last vertex (if it exists) of $P^c(e)$ is not $w\in V$ where $e=(v(e),w)$. Write $f$ for the last edge of $P^c(e)$ if it exists. Put $d(h)=c(h)$ for every $h\in \dom(c)\setminus P^c(e)$ and define $d(e)=\beta(e)$, $d(f_i)=c(f_{i+1})$ for every $f_i\in P^c(e)\setminus \{f\}$ and $d(f)\in\{\beta(e),\gamma(e)\}\setminus \{c(f)\}$. One can easily verify that $d$ is indeed a proper partial edge coloring, $\dom(d)=\dom(c)$ and $d^{-1}(\bfa)= c^{-1}(\bfa)\setminus \{e\}$.

\begin{enonce}{Claim}\label{cl:augment}
Let $\clG=(V,\clB,E)$ be a bounded degree Borel graph that does not contain odd cycles. Let $c;E\to (\Delta(\clG)+1)$ be a proper partial edge coloring and $A\subseteq c^{-1}(\bfa)$ be a Borel set such that $P^c(e)$ and $P^c(e')$ are vertex disjoint for every $e\not =e'\in A$. Then there is a proper partial edge coloring $d;E\to (\Delta(\clG)+1)$ that improves $c$ and $A\cap d^{-1}(\bfa)=\emptyset$.
\end{enonce}


\begin{proof}
The fact that the $\clG$ does not contain odd cycles implies that $w\in V$ is not the last vertex of $P^c(e)$ for any $e\in A$ where $(v(e),w)=e$. Running the augmenting procedure defined in the preceding paragraph for all $P^c(e)$ simultaneously gives a partial map $d;E\to (\Delta(\clG)+1)$. It follows from the fact that $\{P^c(e)\}_{e\,\in\,A}$ is a collection of pairwise vertex disjoint paths that $d$ is well-defined proper partial edge coloring with $\dom(d)=\dom(c)$ and $d^{-1}(\bfa)\cap A=\emptyset$. Moreover, since $e\mapsto P^c(e)$ is a Borel assignment we see that $d;E\to (\Delta(\clG)+1)$ is a partial Borel map and the proof is finished.
\end{proof}

\begin{prop}\label{pr:main}
Let $\clG=(V,\clB,E)$ be a bounded degree Borel graph that does not contain odd cycles, $c;E\to (\Delta(\clG)+1)$ be a proper partial edge coloring, $\eta$ be an $\clE$-quasi-invariant Borel probability measure on $(E,\clC)$, where $\clE=(E,\clC,I_\clG)$ is the line graph, and $\epsilon>0$. Then there is a proper partial edge coloring $d;E\to (\Delta(\clG)+1)$ that improves $c$ such that $\eta(d^{-1}(\bfa))<\epsilon$.
\end{prop}


\begin{proof}
First we show a sufficient condition for $d$ to satisfy the conclusion of the statement. Write $\rho$ for the cocycle of $\eta$.

\begin{enonce*}{Claim }
Let $L\in \bbZ$ and $d;E\to (\Delta(\clG)+1)$ be a proper partial edge coloring such that
\[
\sum_{f\,\in\,P^d(e)}\rho(f,e)\ge 2\Delta(\clG) L
\]
for every $e\in E$ such that $d(e)=\bfa$. Then $\eta(d^{-1}(\bfa))\le \frac{1}{L}$.
\end{enonce*}


\begin{proof}
Let $f\in E$. Then there are at most $2\Delta(\clG)$ edges $e\in E$ such that $d(e)=\bfa$ and $f\in P^d(e)$. This is because there are $\Delta$ choices for a color $\beta$ and two choices of a direction of the path that contains $f$ and alternates colors $\beta$ and $c(f)$. Each edge $e$ that satisfies $f\in P^c(e)$ must be incident to an endpoint of one of these paths.

The cocycle relation gives
\[
2\Delta(\clG) L\eta\left(d^{-1}(\bfa)\right) \le \int_{d^{-1}(\bfa)} \sum_{f\,\in\,P^d(e)}\rho(f,e) \, d\eta\le 2\Delta(\clG)
\]
and that finishes the proof.
\end{proof}

Let $L\in \bbZ$ be such that $\tfrac{1}{L}<\epsilon$. Set $d_0=c$ and $E_0=E$. We construct by induction on all countable ordinals a sequence $\{d_{\kappa}\}_{\kappa\,<\,\aleph_1}$ of proper partial edge colorings and a sequence $\{E_\kappa\}_{\kappa\,<\,\aleph_1}$ of Borel $\eta$-conull $\clE$-invariant subsets of $E$ such that
\begin{enumerate}
\item\label{proofprop3.2.1} $d_\kappa$ is an improvement of $c$,
\item\label{proofprop3.2.2} $E_\kappa \subseteq E_\lambda$ whenever $\lambda\le \kappa<\aleph_1$,
\item\label{proofprop3.2.3} if $\kappa<\aleph_1$ is a limit ordinal, then $\lim_{\lambda\,\to\,\kappa} d_\lambda(e)=d_\kappa(e)$ whenever $e\in E_\kappa\cap \dom(c)$,
\item\label{proofprop3.2.4} $E_\kappa\cap B_\kappa\subseteq E_\lambda \cap B_\lambda$ whenever $\lambda\le \kappa<\aleph_1$,
\item\label{proofprop3.2.5} if $\eta(A_\kappa)>0$, then $\eta(B_{\kappa}\setminus B_{\kappa+1})>0$
where 
\[
B_{\kappa}=d_\kappa^{-1}(\bfa)\quad \text{and} \quad A_{\kappa}=\left\{e\in B_\kappa:\sum_{f\,\in\,P^{d_\kappa}(e)}\rho(f,e)<2\Delta(\clG) L\right\}.
\]
\end{enumerate}
Once we have this then we take the minimal $\kappa_0<\aleph_1$ such that $\eta(A_{\kappa_0})=0$ and define $d=d_{\kappa_0}$. Note that such $\kappa_0<\aleph_1$ exists by~\eqref{proofprop3.2.4} and~\eqref{proofprop3.2.5}. By the Claim we have $\eta(d^{-1}(\bfa))\le \tfrac{1}{L}<\epsilon$. Hence, $d$ works as required.

Let $\kappa<\aleph_1$ and assume that $d_\kappa$ is defined and $\eta(A_\kappa)>0$. There is a pair $\beta,\gamma\in (\Delta(\clG)+1)\setminus \{\bfa\}$ and $k\in \bbZ\cup \{+\infty\}$ such that the Borel set $A'$ of those $e\in A_\kappa$ such that $P^{d_\kappa}(e)\setminus \{e\}$ is an alternating $\beta/\gamma$ path of length $k$ satisfies $\eta(A')>0$. If $k=+\infty$, then find $3$-sparse Borel set $A$ that is a subset of $A'$ and $\eta(A)>0$. This can be done by~\cite[Proposition~4.6]{KST}. Note that $\{P^{d_\kappa}(e)\}_{e\,\in\,A}$ is a collection of pairwise vertex disjoint paths. If $k<+\infty$, then find a $2k$-sparse Borel set $A$ that is a subset of $A'$ and $\eta(A)>0$, again by~\cite[Proposition~4.6]{KST}. Then $\{P^{d_\kappa}(e)\}_{e\,\in\,A}$ is a collection of pairwise vertex disjoint paths. Define $d_{\kappa+1}$ as in Claim~\ref{cl:augment} applied for $A$ and $d_\kappa$. Observe that
\[
C_\kappa=\left\{e\in \dom(c): d_{\kappa}(e)\not=d_{\kappa+1}(e)\right\}\quad\text{satisfies}\quad\eta(C_\kappa)\le 2\Delta(\clG) L\eta\left(B_\kappa\setminus B_{\kappa+1}\right).
\]

Let $\kappa<\aleph_1$ be a limit ordinal and $d_\lambda$ be defined for every $\lambda<\kappa$. We have
\[
\sum_{\lambda\,<\,\kappa}\eta(C_\lambda)\le 2\Delta(\clG) L\sum_{\lambda\,<\,\kappa}\eta\left(B_\lambda\setminus B_{\lambda+1}\right)\le 2\Delta(\clG) L,
\]
because $\{B_\lambda\setminus B_{\lambda+1}\}_{\lambda\,<\,\kappa}$ is a pairwise disjoint collection of sets when restricted to the $\eta$-conull set $\bigcap_{\lambda\,<\,\kappa}E_\lambda$ by~\eqref{proofprop3.2.2} and~\eqref{proofprop3.2.4}. The Borel--Cantelli lemma implies that there is a $\eta$-conull $\clE$-invariant set $H\subseteq E$ such that for every $e\in H\cap \dom(c)$ there is $\lambda_e<\kappa$ such that $e\not \in C_\lambda$ for every $\lambda_e\le \lambda<\kappa$. Define $E_\kappa=H\cap \bigcap_{\lambda\,<\,\kappa} E_{\lambda}$. It follows from~\eqref{proofprop3.2.2} and~\eqref{proofprop3.2.3}, that if $e\in E_\kappa\cap \dom(c)$, then $d_\lambda(e)$ is constant for every $\lambda_e\le \lambda <\kappa$, i.e., $d'(e)=\lim_{\lambda\to \kappa}d_{\lambda}(e)$ exists for every $e\in E_\kappa\cap \dom(c)$. Define $d_\kappa=d'$ on $E_\kappa$ and $d_\kappa=c$ outside of $E_\kappa$.
\end{proof}

We remark that for a $\clE$-invariant measures the proof can be modified as follows. Fix a sequence of $4\Delta(\clG)L$-sparse Borel sets $\{C_l\}_{l\,\in\,\bbZ}\subseteq \clC$ such that every $e\in E$ appears infinitely often. The induction runs over all natural numbers in the same spirit. Namely, define
\[
A_l=\left\{e\in B_l: \left|P^{d_l}(e)\right|<2\Delta(\clG)L\right\}\quad \text{and note that} \quad\left\{P^{d_l}(e)\right\}_{e\,\in\,A_l\,\cap\,C_l}
\]
is a collection of pairwise vertex disjoint paths. Use Claim~\ref{cl:augment} to define $d_{l+1}$. Define $d(e)=\lim_{l\,\to\,\infty} d_l(e)$. It is easy to see that $d$ is defined for every $e\in \dom(c)$ and $|P^d(e)|\ge 2\Delta(\clG)L$ for every $e\in d^{-1}(\bfa)$. This implies that $d$ improves $c$ and satisfies $\eta(d^{-1}({\bf(a)}))<\frac{1}{L}$ for every $\clE$-invariant measure $\eta$.

Before we formulate corollaries of the preceding result we would like to point out that the proof of the approximate version of Vizing's Theorem, see~\cite[Theorem~1.8,~Section~5]{Vizing}, follows the same strategy as the proof of Proposition~\ref{pr:main}. Namely, modify a given coloring such that it does not contain short weighted Vizing chains, see~\cite[Section~2.4]{Vizing}. Similarly as in the preceding paragraph, there is an improvement that works simultaneously for every $\clE$-invariant measure.

\begin{proof}[{Proof of Theorem~\ref{th:main}\emph{$\MK$\eqref{theo1.2.I}}}]
Since we consider any Borel probability measure and there is $v\in V$ of degree $\Delta(\clG)$ by the definition of $\Delta(\clG)$ we have that $\chi'_{App}(\clG)\ge \Delta(\clG)$.

Let $\mu$ be a Borel probability measure on $(V,\clB)$. By the approximate measurable version of Vizing's Theorem, see~\cite[Theorem~1.8]{Vizing}, we find a proper partial edge coloring $c;E\to (\Delta(\clG)+1)$ such that
\[
\mu\left(\left\{v\in V:N(v)\subseteq \dom(c)\right\}\right)>1-\frac{\epsilon}{2}.
\]
Consider the $\clE$-quasi-invariant Borel probability measure $\eta$ on $(E,\clC)$ that is given by a consecutive application of Claims~\ref{cl:quasi invariant}, \ref{cl:measure on edges} and apply Proposition~\ref{pr:main} with $\tfrac{\epsilon}{4\Delta(\clG)}$ in place of $\epsilon$. This yields a proper partial edge coloring $d';E\to (\Delta(\clG)+1)$ that improves $c$ and $\eta({d'}^{-1}(\bfa))<\tfrac{\epsilon}{4\Delta(\clG)}$. Consider an edge coloring $d:E\to \Delta(\clG)$ that agrees with $d'$ on the set
\[
\bigcup_{\beta\,\in\,\left(\Delta(\clG)+1\right)\setminus \{\bfa\}} d'^{-1}(\beta).
\]

Put 
\[
X=\left\{v\in V:N(v)\subseteq \dom(c)\right\}\quad \text{and}\quad Y=\left\{v\in V:N(v)\cap d'^{-1}(\bfa)=\emptyset\right\}.
\]
Let $v\in X\cap Y$. Then it is easy to see that $v\in \Corr(d)$ and we have
\[
\mu(V\setminus \Corr(d))\le \mu(V\setminus X)+\mu(V\setminus Y)< \frac{\epsilon}{2}+2\Delta(\clG)\frac{\epsilon}{4\Delta(\clG)}<\epsilon
\]
by the definition of $\eta$. That finishes the proof.
\end{proof}

\begin{coro}\label{cor:matchings}
Let $\clG=(V,\clB,E)$ be a Borel graph that is $\Delta$-regular and that does not contain odd cycles. Then for every Borel probability measure $\mu$ on $(V,\clB)$ and $\epsilon>0$ there is a Borel matching $M\subseteq E$ such that
\[
\mu(\{v\in V:M\cap N(v)=\emptyset\})<\epsilon.
\]
\end{coro}


\begin{proof}
By Theorem~\ref{th:main}$\MK$\eqref{theo1.2.I} we find an edge coloring $c:E\to \Delta$ such that $\mu(\Corr(c))>1-\epsilon$. Let $\beta\in \Delta$. Then $M=c^{-1}(\beta)$ works as required.
\end{proof}

Note the next result needs the full measurable Vizing's Theorem for graphings.

\begin{coro}[{\cite[Theorem~3]{Laszlo}}]
Let $\clG=(V,\clB,E)$ be a bounded degree Borel graph that does not contain odd cycles, $\mu$ be a $\clG$-invariant Borel probability measure on $(V,\clB)$ and $\epsilon>0$. Then there is a full $\mu$-measurable proper edge coloring $c:E\to (\Delta(\clG)+1)$ such that
\[
\mu \left(\left\{v\in V:\bfa\not\in m_c(v)\right\}\right)<\epsilon.
\]
\end{coro}


\begin{proof}
Combine measurable Vizing's Theorem for invariant measure $\mu$, see \cite[Theorem~1.6]{Vizing} or bipartite version~\cite[Theorem~1.5]{CLP}, and Proposition~\ref{pr:main}.
\end{proof}



\section{Approximate balanced orientation}

Recall that $(E,\clC)$ is a standard Borel space of edges of a Borel graph $\clG=(V,\clB,E)$ and $[E]^{<\,\infty}$ is the standard Borel space of all finite subsets of $E$. One can easily verify that the set of all finite paths $\frkT\subseteq [E]^{<\,\infty}$ and cycles $\frkC\subseteq [E]^{<\,\infty}$ of $\clG$ are Borel sets.

\begin{prop}\label{pr:no cycles}
Let $\clG=(V,\clB,E)$ be a bounded degree Borel graph such that every vertex has even degree. Then there is a Borel set $\frkM\subseteq \frkC$ such that $C\cap D=\emptyset$ for every $C\not=D\in \frkM$ that is maximal with this property. In particular, $\clH=(V,\clB,E\setminus \bigcup_{C\,\in\,\frkM} C)$ is an acyclic Borel graph such that every vertex has even degree bounded by $\Delta(\clG)$.
\end{prop}


\begin{proof}
It follows from~\cite[Lemma~7.3]{KechrisMiller} that the intersection graph on $\frkC$ has a countable Borel chromatic number, i.e., there is a sequence of Borel sets $\{\frkC_i\}_{i\,\in\,\bbZ}$ such that $C\cap D=\emptyset$ whenever $C\not=D\in \frkC_i$ and $\frkC=\bigcup_{i\,\in\,\bbZ}\frkC_i$. Let $\frkD_0=\frkC_0$ and define inductively
\[
\frkD_{i+1}=\frkD_i\cup \left\{C\in \frkC_{i+1}:\,\forall D\in \frkD_n \ C\cap D=\emptyset\right\}.
\]
It is easy to see that $\frkM=\bigcup_{i\,\in\,\bbZ} \frkD_i$ works as required.
\end{proof}

Let $\frkP\subseteq \frkT$ be a collection of finite paths. Then we define $\E(\frkP)$ to be the set of endpoints of $T\in \frkP$.


\begin{prop}\label{pr:paths}
Let $\clG=(V,\clB,E)$ be an acyclic bounded degree Borel graph such that every vertex has even degree. Then there is a sequence $\{\frkP_n\}_{n\,\in\,\bbZ}$ of Borel subsets of $\frkT$ such that
\begin{enumerate}
\item\label{prop4.2.1} $E\subseteq \bigcup\frkP_0$,
\item\label{prop4.2.2} $T\cap T'=\emptyset$ for any $T\not=T'\in \frkP_n$ and every $n\in \bbZ$,
\item\label{prop4.2.3} for every $n\in \bbZ$ and $T\in \frkP_n$ there is a unique $T'\in \frkP_{n+1}$ such that $T\subseteq T'$,
\item\label{prop4.2.4} $\bigcap_{n\,\in\,\bbZ} \E(\frkP_n)=\emptyset$.
\end{enumerate}
\end{prop}


\begin{proof}
If $e,f\in E$, then we define $d(e,f)$ as the minimal size of a path $P\in \frkT$ that connects $e$ and $f$. For $T\in \frkT$ we put $d(e,T)=\max\{d(e,f):f\in T\}$. Because $\clG$ is of bounded degree we find a sequence $\{A_n\}_{n\,\in\,\bbZ}$ of Borel subsets of $E$ such that $|\{n\in \bbZ:e\in A_n\}|=\infty$ for every $e\in E$ and
\[
\frks(n)=\min\left\{d(e,f):e\not =f\in A_n\right\}\to \infty,
\]
see~\cite[Proposition~4.6]{KST}.

As a first step we define inductively a collection $\{\clP_n\}_{n\,\in\,\bbZ}$ that satisfies~\eqref{prop4.2.1}--\eqref{prop4.2.3} and a relaxation of~\eqref{prop4.2.4}. Set $\clP_0=E$. Suppose that $\clP_n$ satisfies~\eqref{prop4.2.2} and~\eqref{prop4.2.3} and let $P\in \clP_n$ be such that $A_n\cap P\not=\emptyset$. Choose in a Borel way a $\subseteq$-maximal path extension $\widetilde{P}$ of $P$ that consists of elements from $\clP_n$, say
\[
\widetilde{P}={R_1}^\frown \dots ^\frown {R_l}^\frown {P} ^\frown {R_{l+1}}^\frown \dots ^\frown {R_k}
\]
where $R_i\in \clP_n$, such that for every $i\le k$ there is $e\in P\cap A_n$ such that $d(e,R_i)<\tfrac{\frks(n)}{3}$.

Let $P,Q\in \clP_n$ be such that $P\cap A_n\not=\emptyset\not=Q\cap A_n$ and $\widetilde{P}\cap \widetilde{Q}\not=\emptyset$. We show that $P=Q$. It follows from the inductive assumption~\eqref{prop4.2.2} that there is $R\in \clP_n$ such that $R\subseteq \widetilde{P},\widetilde{Q}$. If $R=P=Q$, then we are done. Suppose, e.g., that $R\not =P$, the case $R\not=Q$ is the same. By the definition of $\widetilde{P}$ we find $e\in A_n\cap P$ such that $d(e,h)\le \tfrac{\frks(n)}{3}$ for every $h\in R$. If $Q=R$, then we get a contradiction with the definition of $\frks(n)$ since $Q\cap A_n\not=\emptyset$. If $Q\not= R$, then we find $f\in A_n\cap Q$ such that $d(f,h)\le \tfrac{\frks(n)}{3}$ for every $h\in R$. Consequently, $d(e,f)\le d(e,h)+d(f,h)\le \tfrac{2\frks(n)}{3}$ for any $h\in R$ and we must have $e=f$ by the definition of $\frks(n)$. By the inductive assumption~\eqref{prop4.2.2} we conclude that $P=Q$.


Let
\begin{align*}
\clQ_{n+1} &=\left\{\widetilde{P}:P\in \clP_n \, \wedge \, A_n\cap P\not=\emptyset\right\}
\\
\intertext{and define}
\clP_{n+1} &=\clQ_{n+1}\cup \left\{P\in \clP_n\,:\,\forall Q\in \clQ_{n+1} \ P\cap Q=\emptyset\right\}.
\end{align*}

It follows from the previous argument that $\clP_{n+1}$ satisfies~\eqref{prop4.2.2} and~\eqref{prop4.2.3}.

The construction guarantees the following relaxation of~\eqref{prop4.2.4} . Let $e\in E$ and $n\in \bbZ$. It follows from~\eqref{prop4.2.1}--\eqref{prop4.2.3} that there is a unique $P_{e,\,n}\in \clP_n$ such that $e\in P_{e,\,n}$. Note that if $f\in P_{e,\,n}$, then $P_{e,\,n}=P_{f,\,n}$. Define $P_e=\bigcup_{n\,\in\,\bbZ} P_{e,\,n}$. Then $P_e$ is a path by~\eqref{prop4.2.1}--\eqref{prop4.2.3} and we show that it is infinite. Suppose for a contradiction that $P_e$ is finite, i.e., $|P_e|=m\in \bbZ$. Let $v\in V$ be an end point of $P_e$. By the assumption that the degree of $v$ is even we find $f\in N(v)\setminus P_e$ such that $v$ is an endpoint of $P_f$. Since $\clG$ is acyclic we have $P_f\not=P_e$. Let $n\in \bbZ$ be such that $f\in A_n$, $3m<\frks(n)$ and $P_e=P_{e,\,n}$. By the definition we have that $P_{f,\,n+1}\in \clP_{n+1}$ is a $\subseteq$-maximal extension of $P_{f,\,n}\in \clP_n$ that satisfies the condition above. However, $Q={P_{f,\,n+1}}^\frown P_{e,\,n}$ is an extension of $\clP_{f,\,n+1}$ and also satisfies the condition because $d(f,\,P_{e,\,n})\le m<\frac{\frks(n)}{3}$. This shows that $P_e$ is infinite for every $e\in E$.

Now we pair the one ended rays of $\{\clP_n\}_{n\,\in\,\bbZ}$ to obtain $\{\frkP_n\}_{n\,\in\,\bbZ}$ that satisfies \eqref{prop4.2.1}--\eqref{prop4.2.4}. Let $v\in V$ and $E(v)\subseteq N(v)$ be the set of edges $e\in N(v)$ such that $v$ is an endpoint of $P_e$. Since the degree of $v$ is even it follows that $|E(v)|$ is even for every $v\in V$. Note that $E(v)\cap E(w)=\emptyset$ for any $v\not=w \in V$ because $P_e$ has at most one endpoint for every $e\in E$. Let $I:E\to E$ be a Borel involution such that $I(e)\not =e$ if and only if there is $v\in V$ such that $e\in E(v)$ and in that case $I(e)\in E(v)$, i.e., $I$ is a pairing when restricted to any $E(v)$.

Let $M=\bigcup_{v\,\in\,V} E(v)$ and define
\[
\frkP_n=\left\{P_{e,\,n}\cup P_{I(e),\,n}\,:\,e\in M\right\}\cup \left\{P\in \clP_n\,:\,P\cap M=\emptyset\right\}.
\]
Property~\eqref{prop4.2.1} is trivially satisfied. Note that $|M\cap P_{e,\,n}|\le 1$ for every $e\in E$ and $n\in \bbZ$ since $P_e$ is infinite. This implies that if $P,Q\in \frkP_n$ and $P\cap Q\not=\emptyset$, then $P=Q$. Consequently we have~\eqref{prop4.2.2}. Similarly we get that $P_{e,\,n}\cup P_{I(e),\,n}\subseteq P_{e,\,n+1}\cup P_{I(e),\,n+1}$ for every $e\in M$ and that gives~\eqref{prop4.2.3}.

Let $v\in \bigcap_{n\,\in\,\bbZ}E(\frkP_n)$. Then there is a sequence $T_n\in \frkP_n$ such that $v$ is an endpoint of $T_n$. By~\eqref{prop4.2.3} we may assume that $T_n\subseteq T_{n+1}$ and there is $e\in N(v)$ such that $e\in T_n$ for every $n\in \bbZ$. Note that $P_{e,\,n}\subseteq T_n$ by the definition of $\frkP_n$. Consequently, $v$ is an endpoint of $P_e$. We have $T_0=\{e,I(e)\}$ by the definition of $\frkP_0$. That is a contradiction because $v$ is not an endpoint of $T_0$. This shows~\eqref{prop4.2.4} and finishes the proof of Proposition~\ref{pr:paths}.
\end{proof}
\vspace{30pt}
\pagebreak

\begin{theo}[{Theorem~\ref{th:main}$\MK$\eqref{theo1.2.II}}]\label{th:orientation}
Let $\clG=(V,\clB,E)$ be a bounded degree Borel graph such that every vertex has an even degree. Then there is a sequence $\{S_n\}_{n\,\in\,\bbZ}$ of orientations of $\clG$ such that
\[
\mu\big(\left\{v\in \Corr(S_n):N_0(v)\subseteq \Corr(S_n)\right\}\big)\to 1
\]
for every Borel probability measure $\mu$ on $(V,\clB)$. In particular, $\clG$ admits approximate balanced orientation.
\end{theo}


\begin{proof}
Proposition~\ref{pr:no cycles} produces a maximal Borel set $\frkM$ of pairwise disjoint cycles and Proposition~\ref{pr:paths} applied to the acyclic Borel graph $\clH=(V,\clB,E\setminus \bigcup_{C\,\in\,\frkM} C)$ produces a sequence $\{\frkP_n\}_{n\,\in\,\bbZ}$.

Note that since $\frkM\cup \frkP_n$ is a collection of finite paths and cycles that cover $E$ it is easy to produce an orientation $S_n$ of $\clG$ such that $v\not\in \Corr(S_n)$ only if $v$ is an endpoint of some $T\in \frkP_n$. This implies that
\begin{align*}
& \bigcap_{n\,\in\,\bbZ}V\setminus \left\{v\in \Corr(S_n)\,:\,N_0(v)\subseteq \Corr(S_n)\right\} \\
= &  \bigcap_{n\,\in\,\bbZ} \left\{v\in V\,:\,v\in \E(\frkP_n) \; \vee \; N_0(v)\cap \E(\frkP_n) \not=\emptyset \right\}=\emptyset
\end{align*}
and the proof is finished.
\end{proof}



\section{Approximate Schreier decoration}

Before proving the remaining part of Theorem~\ref{th:main} we remind the reader how to use~\eqref{theo1.2.I} and~\eqref{theo1.2.II} in the finite setting. Suppose that $G=(V,E)$ is a finite $2\Delta$-regular graph. Then by~\eqref{theo1.2.II} we find a balanced orientation $S\subseteq E$ of $G$. Consider now a bipartite graph $H=(V_0\sqcup V_1,F)$ where the bipartition is formed by two disjoint copies of $V$ and there is an edge $(v,w)\in F$, where $v\in V_0$ and $w\in V_1$, if and only if there is an oriented edge pointing from $v$ to $w$ in $S$. The fact that $S$ is balanced implies that $H$ is $\Delta$-regular. By~\eqref{theo1.2.I}, i.e., Kőnig's Theorem, we find a proper coloring $c':F\to \Delta$. This induces a coloring $c:E\to \Delta$ such that $(S,c)$ is a Schreier decoration of $G$.

\begin{theo}[{Theorem~\ref{th:main}$\MK$\eqref{theo1.2.III}}]\label{th:decoration}
Let $\clG=(V,\clB,E)$ be a $2\Delta$-regular Borel graph. Then $\clG$ admits approximate Schreier decoration.
\end{theo}


\begin{proof}
Let $\mu$ be a Borel probability measure on $(V,\clB)$ and $\epsilon>0$. Use Theorem~\ref{th:orientation} to find an orientation $S$ of $\clG$ such that
\[
\mu\left(\left\{v\in \Corr(S)\,:\,N_0(v)\subseteq \Corr(S)\right\}\right)>1-\frac{\epsilon}{2}.
\]
Define a bipartite Borel graph $\clH=(C^0\sqcup C^1,\clD,H)$ where $C^0,C^1$ are disjoint copies of $\Corr(S)$, $\clD$ is the corresponding $\sigma$-algebra and $(v^0,w^1),(w^1,v^0)\in H$ if and only if $(v,w)\in S$ where $v^0\in C^0$, $w^1\in C^1$ are the copies of $v,w\in \Corr(S)$. It follows from the definition of $\Corr(S)$ that the maximum degree of $\clH$ is bounded by $\Delta$. Define a Borel probability measure $\nu$ on $C^0\sqcup C^1$ as
\[
\nu(A\sqcup B)=\frac{\mu(A)+\mu(B)}{2\mu(\Corr(S))}
\]
whenever $A\subseteq C^0$ and $B\subseteq C^1$ are Borel sets. Theorem~\ref{th:main}$\MK$\eqref{theo1.2.I} gives an edge coloring $c':H\to \Delta$ such that $\nu(\Corr(c'))>1-\frac{\epsilon}{4\mu(\Corr(S))}$. Let $c:E\to \Delta$ be an edge coloring that extends $c'$, i.e., $c(v,w)=c(w,v)=c'(v^0,w^1)$ whenever $(v,w)\in S$ and $v,w\in \Corr(S)$.

Write 
\begin{align*}
X &=\left\{v\in \Corr(S)\,:\,N_0(v)\subseteq \Corr(S)\right\}\\
\intertext{and}
Y_i &=\left\{v\in V\,:\,v^i\in \Corr(c')\cap C^i\right\}
\end{align*}
where $i<2$. Let $v \in X\cap Y_0\cap Y_1$. Then it is easy to see that $v\in \Corr(S,c)$. We have
\[
\mu\left(V\setminus X\cap Y_0\cap Y_1\right)\le \mu(V\setminus X)+\mu\left(V\setminus Y_0\right)+\mu\left(V\setminus Y_1\right)<\epsilon
\]
because $\mu(V\setminus Y_0)+\mu(V\setminus Y_1)\le 2\mu(\Corr(S))\nu(C^0\sqcup C^1\setminus \Corr(c'))<\tfrac{\epsilon}{2}$. This finishes the proof of Theorem~\ref{th:main}$\MK$\eqref{theo1.2.III}.
\end{proof}



\section{Remarks}\label{sec:5}

The ultraproduct technique for graphings, see~\cite{Elek} or~\cite{KecConleyT-D}, implies that we can find a locally-globally equivalent graphing that is an extension of the original one and satisfies fully (not just approximately) the corresponding conditions in Theorem~\ref{th:main} or Corollary~\ref{cor:matchings}. We refer the reader to~\cite[Chapter~19]{Lovasz} for the corresponding definitions.

For example, if $(\clG,\mu)$ is a graphing where $\clG=(V,\clB,E)$ is a $2\Delta$-regular Borel graph, then there is a $2\Delta$-regular Borel graph $\clG'=(V',\clB',E')$, a $\clG'$-invariant Borel probability measure $\mu'$ and a Borel map $\varphi:V'\to V$ such that $\varphi$ is a local isomorphisms, $\varphi^*\mu'=\mu$, $(\clG,\mu)$, $(\clG',\mu')$ are locally-globally equivalent and $\clG$ admits a Schreier decoration, i.e., it is induced by a pmp action of the free group $F_{\Delta}$. This extends~\cite[Corollary~4]{Laszlo} and implies~\cite[Theorem~1]{Laszlo}.

Similar statement hold in the case of quasi-invariant probability measures when the notion of local-global equivalence is extended appropriately.

\vspace{20pt}


\bibliography{grebik}
\end{document}
