%~Mouliné par MaN_auto v.0.27.3 2022-07-05 09:45:01
\documentclass[AHL,Unicode,longabstracts,published]{cedram}

%\usepackage{mathabx}
\usepackage{bm}






%\AtBeginDocument{
%%\newtheorem{myname}[cdrthm]{My beautiful theorem} }



\newcommand{\0}{\varnothing}
\newcommand{\set}[1]{\{#1\}}

\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\phi}{\varphi}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\newcommand{\defeq}{\coloneqq}
\newcommand{\bemph}[1]{{\normalfont#1}}
%\newcommand{\ep}[1]{\emph{(}#1\emph{)}}
\newcommand{\emphd}[1]{{\fontseries{b}\selectfont{#1}}}
\newcommand{\acts}{\mathrel{\reflectbox{$\circlearrowleft$}}}
\newcommand{\racts}{\circlearrowright}
\newcommand{\G}{\Gamma}
\newcommand{\pto}{\dashrightarrow}

\newcommand{\symdif}{\vartriangle}
\newcommand{\rest}[2]{{{#1}\vert_{#2}}}

\newcommand{\N}{{\mathbb{N}}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\bbT}{\mathbb{T}}


\newcommand{\dom}{\mathrm{dom}}
\newcommand{\Free}{\mathrm{Free}}
\newcommand{\rmB}{\mathrm{B}}
\newcommand{\rmd}{\mathrm{d}}

\newcommand{\bfun}{\mathbf{1}}

\newcommand{\frkA}{\mathfrak{A}}

\makeatletter
\def\editors#1{%
\def\editor@name{#1}
\if@francais
\def\editor@string{Recommand\'e par les \'editeurs \editor@name.}
\else
\def\editor@string{Recommended by Editors \editor@name.}
\fi}
\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}

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

\title{Borel fractional colorings of Schreier graphs}
\alttitle{Coloriages fractionnaires boréliens de graphes de Schreier}

\subjclass{03E15, 05C15, 37B10}
\keywords{fractional coloring, Borel sets, Borel combinatorics, Schreier graph, group action, symbolic dynamics}

\author[\initial{A.} \lastname{Bernshteyn}]{\firstname{Anton} \lastname{Bernshteyn}}
\address{School of Mathematics, Georgia\\ Institute of Technology,\\
Atlanta, GA, USA}
\email{bahtoh@gatech.edu}
\thanks{This research is partially supported by the NSF grant DMS-2045412.}


\begin{abstract}
Let $\Gamma$ be a countable group and let $G$ be the Schreier graph of the free part of the Bernoulli shift $\Gamma \curvearrowright 2^\Gamma$ (with respect to some finite subset $F \subseteq \Gamma$). We show that the Borel fractional chromatic number of $G$ is equal to $1$ over the measurable independence number of $G$. As a consequence, we asymptotically determine the Borel fractional chromatic number of $G$ when $\Gamma$ is the free group, answering a question of Meehan.
\end{abstract}

\begin{altabstract}
Soit $\Gamma$ un groupe dénombrable. Considérons $G$ le graphe de Schreier de la partie libre du décalage de Bernoulli $\Gamma \curvearrowright 2^\Gamma$ (par rapport à un ensemble fini $F \subseteq \Gamma$). Nous montrons que le nombre chromatique fractionnaire borélien de $G$ est égal à $1$ sur le nombre d'indépendance mesurable de $G$. Comme conséquence, nous déterminons l'asymptotique du nombre chromatique fractionnaire borélien de $G$ lorsque $\Gamma$ est le groupe libre, ce qui répond à une question de Meehan.
\end{altabstract}


\datereceived{2021-09-05}
\dateaccepted{2022-02-22}

\editors{S. Gou{\"e}zel and D. Aldous}
%\begin{DefTralics}
%
%\end{DefTralics}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\dateposted{2022-11-24}
\begin{document}
\maketitle

\section{Definitions and results}

All graphs in this paper are undirected and simple. Recall that for a graph $G$, a subset $I \subseteq V(G)$ is \emph{$G$-independent} if no two vertices in $I$ are adjacent in $G$. The \emph{chromatic number} of $G$, denoted by $\chi(G)$, is the least $\ell \in \N$ such that there exist $G$-independent sets $I_1,\,\ldots,\,I_\ell$ whose union is $V(G)$. (If no such $\ell$ exists, we set $\chi(G)
\defeq \infty$.) The sequence $I_1,\,\ldots,\, I_\ell$ is called an \emph{$\ell$-coloring} of $G$, where we think of the vertices in $I_i$ as being assigned the color $i$.

Fractional coloring is a well-studied relaxation of graph coloring. For an introduction to this topic, see the book~\cite{FracBook} by Scheinerman and Ullman. Given $k \in \N$, the \emph{$k$-fold chromatic number} of $G$, denoted by $\chi^k(G)$, is the least $\ell \in \N$ such that there are $G$-independent sets $I_1,\,\ldots,\,I_\ell$ which cover every vertex of $G$ at least $k$ times (such a sequence $I_1,\, \ldots, \, I_\ell$ is called a \emph{$k$-fold $\ell$-coloring}). Note that the sets $I_1,\, \ldots,\, I_\ell$ need not be distinct. In particular, if $I_1,\, \ldots,\, I_{\chi(G)}$ is a $\chi(G)$-coloring of $G$, then, by repeating each set $k$ times, we obtain a $k$-fold $k\chi(G)$-coloring, which shows that
\[
\chi^k(G) \,\leq\, k \chi(G) \quad \text{for all } k.
\]
This inequality can be strict; for example, the $5$-cycle $C_5$ satisfies $\chi(C_5) = 3$ but $\chi^2(C_5) = 5$. It is therefore natural to define the \emph{fractional chromatic number} $\chi^\ast(G)$ of $G$ by the formula
\[
\chi^\ast(G) \,
\defeq\, \inf_{k\,\geq\,1} \frac{\chi^k(G)}{k}.
\]

In this note we investigate fractional colorings from the standpoint of Borel combinatorics. For a general overview of Borel combinatorics, see the surveys~\cite{KechrisMarks} by Kechris and Marks and~\cite{Pikh_survey} by Pikhurko. The study of fractional colorings in this setting was initiated by Meehan~\cite{Mee}; see also~\cite[\S~8.6]{KechrisMarks}. We say that a graph $G$ is \emph{Borel} if $V(G)$ is a standard Borel space and $E(G)$ is a Borel subset of $V(G) \times V(G)$. The \emph{Borel chromatic number} $\chi_\rmB(G)$ of $G$ is the least $\ell \in \N$ such that there exist {Borel} $G$-independent sets $I_1,\, \ldots, \,I_\ell$ whose union is $V(G)$. The \emph{Borel $k$-fold chromatic number} $\chi^k_{\rmB}(G)$ is defined analogously, and the \emph{Borel fractional chromatic number} $\chi^\ast_{\rmB}(G)$ is
\[
\chi^\ast_{\rmB}(G) \,
\defeq\, \inf_{k\,\geq\,1} \frac{\chi^k_{\rmB}(G)}{k}.
\]

A particularly important class of Borel graphs are Schreier graphs of group actions. Let $\Gamma$ be a countable group with identity element $\bfun$ and let $F \subseteq \Gamma$ be a finite subset. The \emph{Cayley graph} $G(\Gamma, F)$ of $\Gamma$ is the graph with vertex set $\Gamma$ in which two distinct group elements $\gamma$, $\delta$ are adjacent if and only if $\gamma =\sigma \delta$ for some $\sigma \in F \cup F^{-1}$. This definition can be extended as follows. Let $\Gamma \curvearrowright X$ be a Borel action of $\Gamma$ on a standard Borel space $X$. The action $\Gamma \curvearrowright X$ is \emph{free} if
\[
\gamma \cdot x \,\neq\, x \quad \text{for all }\; x \in X\quad \text{and}\quad \bfun \neq \gamma \in \Gamma.
\]
The \emph{Schreier graph} $G(X,F)$ of an action $\Gamma \curvearrowright X$ is the graph with vertex set $X$ in which two distinct points $x$, $y \in X$ are adjacent if and only if $y = \sigma \cdot x$ for some $\sigma \in F \cup F^{-1}$. Note that the Cayley graph $G(\Gamma, F)$ is a special case of this construction corresponding to the left multiplication action $\Gamma \curvearrowright \Gamma$. More generally, when the action $\Gamma \curvearrowright X$ is free, $G(X, F)$ is obtained by putting a copy of the Cayley graph $G(\Gamma, F)$ onto each orbit.

A crucial example of a Borel action is the \emph{(Bernoulli) shift} $\Gamma \curvearrowright 2^\Gamma$, given by the formula
\[
(\gamma \cdot x)(\delta) \,
\defeq\, x(\delta \gamma) \quad \text{for all}\quad x \colon \Gamma \to 2 \quad\text{and}\quad \gamma,\ \delta \in \Gamma.
\]
We use $\beta$ to denote the ``coin flip'' probability measure on $2^\Gamma$, obtained as the product of countably many copies of the uniform probability measure on $2 = \set{0,1}$. Note that $\beta$ is invariant under the shift action. The \emph{free part} of $2^\Gamma$, denoted by $\Free(2^\Gamma)$, is the set of all points $x \in 2^\Gamma$ with trivial stabilizer. In other words, $\Free(2^\Gamma)$ is the largest subspace of $2^\Gamma$ on which the shift action is free. It is easy to see that the shift action $\Gamma \curvearrowright 2^\Gamma$ is free $\beta$-almost everywhere, i.e., $\beta(\Free(2^\Gamma)) = 1$.

Let $G$ be a Borel graph and let $\mu$ be a probability (Borel) measure on $V(G)$. The \emph{$\mu$-independence number} of $G$ is the quantity $\alpha_\mu(G)
\defeq \sup_I \mu(I)$, where the supremum is taken over all $\mu$-measurable $G$-independent subsets $I \subseteq V(G)$. Note that if $I_1,\, \ldots,\, I_\ell$ is a Borel $k$-fold $\ell$-coloring of $G$, then
\[
\ell \alpha_\mu(G) \,\geq\, \mu(I_1) + \cdots + \mu(I_\ell) \,\geq\, k,
\]
which implies $\chi^\ast_\rmB(G) \geq 1/\alpha_\mu(G)$. Our main result is a matching upper bound for Schreier graphs:

\begin{theo}\label{theo:main}
Let $\Gamma$ be a countable group and let $F \subseteq \Gamma$ be a finite set. If $\Gamma \curvearrowright X$ is a free Borel action on a standard Borel space, then
\begin{equation}\label{eq:all}
\chi^\ast_\rmB(G(X,F)) \,\leq\, \frac{1}{\alpha_\beta\left(G\left(\Free\left(2^{\Gamma}\right), F\right)\right)}.
\end{equation}
In particular,
\begin{equation}\label{eq:shift}
\chi^\ast_\rmB\left(G\left(\Free\left(2^{\Gamma}\right), F\right)\right) \,=\, \frac{1}{\alpha_\beta\left(G\left(\Free\left(2^{\Gamma}\right), F\right)\right)}.
\end{equation}
\end{theo}

While~\eqref{eq:shift} is a special case of~\eqref{eq:all}, it is possible to deduce~\eqref{eq:all} from~\eqref{eq:shift} using a theorem of Seward and Tucker--Drob~\cite{STD}, which asserts that every free Borel action of $\Gamma$ admits a Borel $\Gamma$-equivariant map to $\Free(2^\Gamma)$. Nevertheless, we will give a simple direct proof of~\eqref{eq:all} in \S~\ref{sec:proof}.

An interesting feature of Theorem~\ref{theo:main} is that it establishes a precise relationship between a \emph{Borel} parameter $\chi^\ast_\rmB$ and a \emph{measurable} parameter $\alpha_\beta$. We find this somewhat surprising, since ignoring sets of measure $0$ usually significantly reduces the difficulty of problems in Borel combinatorics. For instance, given a Borel graph $G$ and a probability measure $\mu$ on $V(G)$, one can consider the \emph{$\mu$-measurable chromatic number} $\chi_\mu(G)$, i.e., the least $\ell \in \N$ such that there exist $\mu$-measurable $G$-independent sets $I_1,\, \ldots,\, I_\ell$ whose union is $V(G)$. By definition, $\chi_\mu(G) \leq \chi_\rmB(G)$, and it is often the case that this inequality is strict---see~\cite[\S~6]{KechrisMarks} for a number of examples. By contrast, as an immediate consequence of Theorem~\ref{theo:main} we obtain the opposite inequality $\chi_\rmB^\ast(G) \leq \chi_\beta(G)$, where $G$ is the Schreier graph of the free part of the shift:

\begin{coro}
Let $\Gamma$ be a countable group and let $F \subseteq \Gamma$ be a finite set. Set $G
\defeq G(\Free(2^{\Gamma}), F)$. Then $\chi^\ast_\rmB(G) \leq \chi_\beta(G)$.
\end{coro}


\begin{proof}
Follows from Theorem~\ref{theo:main} and the inequality $\alpha_\beta(G) \geq 1/\chi_\beta(G)$.
\end{proof}

As a concrete application of Theorem~\ref{theo:main}, consider the free group case. For $n \geq 1$, let $\F_n$ be the free group of rank $n$ generated freely by elements $\sigma_1,\, \ldots,\,\sigma_n$ and let $G_n$ denote the Schreier graph of the free part of the shift action $\F_n \curvearrowright 2^{\F_n}$ with respect to the set $\set{\sigma_1,\,\ldots,\, \sigma_n}$. Then every connected component of $G_n$ is an (infinite) $2n$-regular tree. In particular, the chromatic number of $G_n$ is $2$. On the other hand, Marks~\cite{Marks} proved that $\chi_{\rmB}(G_n) = 2n+1$. Meehan inquired where between these two extremes the Borel fractional chromatic number of $G_n$ lies:

\begin{enonce}[plain]{Question}[{\cite[Question~4.6.3]{Mee}; see also~\cite[Problem~8.17]{KechrisMarks}}]\label{ques:Mee}
What is the Borel fractional chromatic number of $G_n$? Is it always equal to $2$?
\end{enonce}

Using Theorem~\ref{theo:main} together with some known results we asymptotically determine $\chi_\rmB^\ast(G_n)$ (and, in particular, give a negative answer to the second part of Question~\ref{ques:Mee}):

\begin{coro}\label{corl:free}
For all $n \geq 1$, we have
\[
\chi_\rmB^\ast(G_n) \,=\, (2+o(1))\frac{n}{\log n},
\]
where $o(1)$ denotes a function of $n$ that approaches $0$ as $n \to \infty$.
\end{coro}

In other words, the Borel fractional chromatic number of $G_n$ is less than its ordinary Borel chromatic number roughly by a factor of $\log n$. We present the derivation of Corollary~\ref{corl:free} in \S~\ref{sec:corl}.

\section{Proof of Theorem~\ref{theo:main}}\label{sec:proof}

We shall use the following theorem of Kechris, Solecki, and Todorcevic:

\begin{theo}[{Kechris--Solecki--Todorcevic~\cite[Proposition~4.6]{KST}}]\label{theo:KST}
If $G$ is a Borel graph of finite maximum degree $d$, then $\chi_\rmB(G) \leq d+1$.
\end{theo}

Fix a countable group $\Gamma$ and a finite subset $F \subseteq \Gamma$. Without loss of generality, we may assume that $\bfun \not \in F$. Say that a set $I \subseteq 2^\Gamma$ is \emph{independent} if $I \cap (\sigma \cdot I) = \0$ for all $\sigma \in F$ (when $I \subseteq \Free(2^\Gamma)$, this exactly means that $I$ is $G(\Free(2^\Gamma), F)$-independent). For brevity, let
\[
\alpha_\beta \,
\defeq\, \alpha_\beta\left(G\left(\Free\left(2^\Gamma\right), F\right)\right).
\]

\begin{lemm}\label{lemma:clopen}
For every $\alpha < \alpha_\beta$, there is a clopen independent set $I \subseteq 2^\Gamma$ such that $\beta(I) \geq \alpha$.
\end{lemm}


\begin{proof}
Let $J \subseteq \Free(2^\Gamma)$ be a $\beta$-measurable independent set with $\beta(J) > \alpha$. Since $\beta$ is regular~\cite[Theorem~17.10]{KechrisDST} and $2^\Gamma$ is zero-dimensional, there is a clopen set $C \subseteq 2^\Gamma$ with
\[
\mu(J \symdif C) \,\leq\, \frac{\beta(J) - \alpha}{|F| + 1}.
\]
Set $I
\defeq C \setminus \bigcup_{\sigma \in F} (\sigma \cdot C)$. By construction, $I$ is clopen and independent. Moreover, if $x \in J \setminus I$, then either $x \in J \setminus C$ or $x \in (\sigma \cdot C) \setminus (\sigma \cdot J)$ for some $\sigma \in F$. Therefore,
\[
\beta(I) \,\geq\, \beta(J) \,-\, (|F|+1) \beta(J \symdif C) \,\geq\, \alpha. \qedhere
\]
\end{proof}

Let $\Gamma \curvearrowright X$ be a free Borel action on a standard Borel space. Fix an arbitrary clopen independent set $I \subseteq 2^\Gamma$. We will prove that $\chi^\ast_\rmB(G(X,F)) \leq 1/\beta(I)$, which yields Theorem~\ref{theo:main} by Lemma~\ref{lemma:clopen}. Since $I$ is clopen, there exist finite sets $D \subseteq \Gamma$ and $\Phi \subseteq 2^D$ such that
\[
I \,=\, \left\{x \in 2^\Gamma \,:\, \rest{x}{D} \in \Phi\right\},
\]
where $\rest{x}{D}$ denotes the restriction of $x$ to $D$. Note that
\[
\beta(I) \,=\, \frac{|\Phi|}{2^{|D|}}.
\]
Let $N
\defeq |DD^{-1}|$ and consider the graph $H
\defeq G(X, DD^{-1})$. Every vertex in $H$ has precisely $N-1$ neighbors (we are subtracting $1$ to account for the fact that a vertex is not adjacent to itself). By Theorem~\ref{theo:KST}, this implies that $\chi_\rmB(H) \leq N$. In other words, we may fix a Borel function $f \colon X \to N$ such that $f(u) \neq f(v)$ whenever $u$, $v \in X$ are distinct points satisfying $v \in DD^{-1} \cdot u$. This implies that for each $x \in X$, the restriction of $f$ to the set $D \cdot x$ is injective. Now, to each mapping $\phi \colon N \to 2$, we associate a Borel $\Gamma$-equivariant function $\pi_\phi \colon X \to 2^\Gamma$ as follows:
\[
\pi_\phi(x)(\gamma) \,
\defeq\, (\phi \circ f)(\gamma \cdot x) \quad \text{for all}\quad x \in X \quad\text{and}\quad \gamma \in \Gamma.
\]
Let $I_\phi
\defeq \pi_\phi^{-1}(I)$. Since $\pi_\phi$ is $\Gamma$-equivariant, $I_\phi$ is $G(X, F)$-independent. Consider any $x \in X$ and let
\[
S_x \,
\defeq\, \set{f(\gamma \cdot x) \,:\, \gamma \in D}.
\]
By the choice of $f$, $S_x$ is a subset of $N$ of size $|D|$. Whether or not $x$ is in $I_\phi$ is determined by the restriction of $\phi$ to $S_x$; furthermore, there are exactly $|\Phi|$ such restrictions that put $x$ in $I_\phi$. Thus, the number of mappings $\phi \colon N \to 2$ for which $x \in I_\phi$ is
\[
|\Phi|2^{N - |D|} \,=\, \beta(I)2^N.
\]
Since this holds for all $x \in X$, we conclude that the sets $I_\phi$ cover every point in $X$ exactly $\beta(I)2^N$ times. Therefore, $\chi^\ast_\rmB(G(X,F)) \leq 1/\beta(I)$, as desired.

\section{Proof of Corollary~\ref{corl:free}}\label{sec:corl}

Thanks to Theorem~\ref{theo:main}, in order to establish Corollary~\ref{corl:free} it is enough to verify that
\[
\alpha_\beta\left(G_n\right) \,=\, \left(\frac{1}{2} + o(1)\right) \frac{\log n}{n}.
\]
There are a number of known constructions that witness the lower bound
\[
\alpha_\beta\left(G_n\right) \,\geq\, \left(\frac{1}{2} + o(1)\right) \frac{\log n}{n};
\]
see, e.g., \cite{LW} by Lauer and Wormald and~\cite{GG} by Gamarnik and Goldberg. Moreover, by~\cite[Corollary~1.2]{Ber}, even the inequality $\chi_\beta(G_n) \leq (2+o(1))n/\log n$ holds. For the upper bound
\begin{equation}\label{eq:upper}
\alpha_\beta(G_n) \,\leq\, \left(\frac{1}{2} + o(1)\right)\frac{\log n}{n},
\end{equation}
we shall use a theorem of Rahman and Virág~\cite{RV}, which says that the largest density of a factor of i.i.d.~independent set in the $d$-regular tree is at most $(1+o(1))\log d/d$. In the remainder of this section we describe their result and explain how it implies the desired upper bound on $\alpha_\beta(G_n)$.

Fix an integer $n \geq 1$. For our purposes, it will be somewhat more convenient to work on the space $[0,1]^{\F_n}$ instead of $2^{\F_n}$, where $[0,1]$ is the unit interval equipped with the usual Lebesgue probability measure. The product measure on $[0,1]^{\F_n}$ is denoted by $\lambda$. Let $H_n$ be the Schreier graph of the shift action $\F_n \curvearrowright [0,1]^{\F_n}$ corresponding to the standard generating set of $\F_n$. We remark that, by a theorem of Abért and Weiss~\cite{AW} (see also~\cite[Theorem~6.46]{KechrisMarks}), $\alpha_\beta(G_n) = \alpha_\lambda(H_n)$, so it does not really matter whether we are working with $G_n$ or $H_n$.

Set $d \defeq 2n$ and let $\bbT_d$ denote the Cayley graph of the free group $\F_n$ with respect to the standard generating set. In other words, $\bbT_d$ is an (infinite) $d$-regular tree. We view $\bbT_d$ as a \emph{rooted} tree, whose root is the vertex $\bfun$, i.e., the identity element of $\F_n$. Let $\frkA$ be the automorphism group of $\bbT_d$, i.e., the set of all bijections $\frkA \colon \F_n \to \F_n$ that preserve the edges of $\bbT_d$, and let $\frkA_\bullet \subseteq \frkA$ be the subgroup comprising the root-preserving automorphisms, i.e., those $\frkA \in \frkA$ that map $\bfun$ to $\bfun$. The space $[0,1]^{\F_n}$ is equipped with a natural right action $[0,1]^{\F_n} \racts \frkA$. Namely, for $\frkA \in \frkA$ and $x \in [0,1]^{\F_n}$, the result of acting by $\frkA$ on $x$ is the function $x \cdot \frkA \colon \F_n \to [0,1]$ given by
\[
(x \cdot \frkA)(\delta) \,
\defeq\, x(\frkA(\delta)) \quad \text{for all}\quad \delta \in \F_n.
\]
For each $\gamma \in \F_n$, there is a corresponding automorphism $\frkA_\gamma \in \frkA$ sending every group element $\delta \in \F_n$ to $\delta \gamma$. The mapping $\F_n \to \frkA \colon \gamma \mapsto \frkA_\gamma$ is an antihomomorphism of groups, that is, we have
\[
\frkA_{\gamma \sigma} \,=\, \frkA_\sigma \circ \frkA_\gamma \quad \text{for all}\quad\gamma
, \sigma \in \F_n,
\]
where $\circ$ denotes composition. In particular, $\set{\frkA_\gamma \,:\, \gamma \in \F_n}$ is a subgroup of $\frkA$ isomorphic to $\F_n$. The right action $[0,1]^{\F_n} \racts \frkA$ and the left action $\F_n \curvearrowright [0,1]^{\F_n}$ are related by the formula
\[
x \cdot \frkA_\gamma = \gamma \cdot x \quad \text{for all}\quad x \in [0,1]^{\F_n}.
\]
A set $X \subseteq [0,1]^{\F_n}$ is called \emph{$\frkA_\bullet$-invariant} if $x \cdot \frkA \in X$ for all $x \in X$ and $\frkA \in \frkA_\bullet$. The Rahman--Virág theorem can now be stated as follows:

\begin{theo}[{Rahman--Virág~\cite[Theorem~2.1]{RV}}]\label{theo:RV}
If $I \subseteq [0,1]^{\F_n}$ is an $\frkA_\bullet$-invariant $\lambda$-measurable $H_n$-independent set, then
\[
\lambda(I) \,\leq\, (1+o(1)) \frac{\log d}{d} \,=\, \left(\frac{1}{2} + o(1)\right) \frac{\log n}{n}.
\]
\end{theo}

Theorem~\ref{theo:RV} is almost the result we want, except that we need an upper bound on the measure of \emph{every} (not necessarily $\frkA_\bullet$-invariant) $\lambda$-measurable $H_n$-independent set $I$. To remove the $\frkA_\bullet$-invariance assumption, we use the following consequence of Theorem~\ref{theo:RV}:

\begin{coro}\label{corl:tree}
There exists a Borel graph $Q$ with a probability measure $\mu$ on $V(Q)$ such that:
\begin{itemize}
\item every connected component of $Q$ is a $d$-regular tree; and
\item $\alpha_\mu(Q) \leq (1/2 + o(1)) \log n/n$.
\end{itemize}
\end{coro}


\begin{proof}
We use a construction that was studied by Conley, Kechris, and Tucker--Drob in~\cite{Ultra}. Let $\Omega$ be the set of all points $x \in [0,1]^{\F_n}$ such that $x \cdot \frkA \neq x$ for every non-identity automorphism $\frkA \in \frkA$. Let us make a couple observations about $\Omega$. Notice that, by definition, the set $\Omega$ is invariant under the action $[0,1]^{\F_n} \racts \frkA$; in particular, it is invariant under the shift action $\F_n \curvearrowright [0,1]^{\F_n}$. Furthermore, the induced action of $\F_n$ on $\Omega$ is free (indeed, even the action $\Omega \racts \frkA$ is free). Since every injective mapping $\F_n \to [0,1]$ belongs to $\Omega$, we conclude that $\lambda(\Omega) = 1$. Now consider the quotient space $V
\defeq \Omega/\frkA_\bullet$. As the group $\frkA_\bullet$ is compact, the space $V$ is standard Borel~\cite[paragraph preceding Lemma~7.8]{Ultra}. Let $\mu$ be the push-forward of $\lambda$ under the quotient map $\Omega \to V$, and let $Q$ be the graph with vertex set $V$ in which two vertices $\bm{x}$, $\bm{y} \in V$ are adjacent if and only if there are representatives $x \in \bm{x}$ and $y \in \bm{y}$ that are adjacent in $H_n$. Conley, Kechris, and Tucker--Drob~\cite[Lemma~7.9]{Ultra} (see also~\cite[Proposition~1.9]{Thornton}) showed that every connected component of $Q$ is a $d$-regular tree. Furthermore, by construction, a set $I \subseteq V$ is $Q$-independent if and only if its preimage under the quotient map is $H_n$-independent. Since the quotient map establishes a one-to-one correspondence between subsets of $V$ and $\frkA_\bullet$-invariant subsets of $\Omega$, Theorem~\ref{theo:RV} is equivalent to the assertion that $\alpha_\mu(Q) \leq (1/2 + o(1)) \log n/n$, as desired.
\end{proof}

In view of Corollary~\ref{corl:tree}, the following lemma completes the proof of~\eqref{eq:upper}:

\begin{lemma}\label{lemma:AW}
Let $Q$ be a Borel graph in which every connected component is a $d$-regular tree and let $\mu$ be a probability measure on $V(Q)$. Then $\alpha_\mu(Q) \geq \alpha_\beta(G_n)$.
\end{lemma}

In the case when $Q$ is the Schreier graph of a free measure-preserving action of $\F_n$, the conclusion of Lemma~\ref{lemma:AW} follows from the Abért--Weiss theorem~\cite{AW}. To handle the general case, we rely on a strengthening of a recent result of Tóth~\cite{Toth} due to Greb\'ik~\cite{Jan}, which, roughly, asserts that every $d$-regular Borel graph is ``approximately'' induced by an action of $\F_n$.


To state this result precisely, we introduce the following terminology. A \emph{Borel partial action} $\bm{p}$ of $\F_n$ on a standard Borel space $X$, in symbols $\bm{p} \colon \F_n \curvearrowright^\ast X$, is a sequence of Borel partial injections $p_1,\,\ldots,\, p_n \colon X \pto X$. Given a Borel graph $Q$, we say that a Borel partial action $\bm{p} \colon \F_n \curvearrowright^\ast V(Q)$ is a \emph{partial Schreier decoration} of $Q$ if $p_i(x)$ is adjacent to $x$ for all $1 \leq i \leq n$ and $x \in \dom(p_i)$. If $\bm{p}$ is a partial Schreier decoration of a graph $Q$, then we let $C(Q, \bm{p})$ be the set of all vertices $x \in V(Q)$ such that $x$ belongs to both the domain and the image of every $p_i$ and the neighborhood of $x$ in $Q$ is equal to the set $\set{p_1(x),\, \ldots,\, p_n(x), p^{-1}_1(x), \,\ldots,\, p_n^{-1}(x)}$.\linebreak A \emph{Schreier decoration} of $Q$ is a partial Schreier decoration $\bm{p}$ such that $C(Q, \bm{p})\linebreak = V(Q)$. It is easy to see that $Q$ admits a Schreier decoration if and only if it is the Schreier graph of a Borel action of $\F_n$.

Now we can state Greb{\'\i}k's result:

\begin{theo}[{Greb{\'\i}k~\cite[Theorem~0.2(III)]{Jan}}]\label{theo:Jan}
Let $Q$ be a $d$-regular Borel graph and let $\mu$ be a probability measure on $V(Q)$. Then for every $\epsilon > 0$, $Q$ admits a partial Schreier decoration $\bm{p}$ such that $\mu(C(Q, \bm{p})) \geq 1 - \epsilon$.
\end{theo}

With Theorem~\ref{theo:Jan} in hand, we are ready to establish Lemma~\ref{lemma:AW}.

\begin{proof}[{Proof of Lemma~\ref{lemma:AW}}]
Recall that we denote the generators of $\F_n$ by $\sigma_1,\, \ldots, \,\sigma_n$. Let $Q$ be a Borel graph in which every connected component is a $d$-regular tree and let $\mu$ be a probability measure on $V(Q)$. Thanks to Lemma~\ref{lemma:clopen}, it suffices to show that $\alpha_\mu(Q) \geq \beta(I)$ for every clopen independent set $I \subseteq 2^{\F_n}$, where, as in \S~\ref{sec:proof}, we say that $I$ is independent if $I \cap (\sigma_i \cdot I) = \0$ for each $1 \leq i \leq n$.

Fix a clopen independent set $I \subseteq 2^{\F_n}$. Since $I$ is clopen, we can write
\[
I \,=\, \left\{x \in 2^{\F_n} \,:\, \rest{x}{D} \in \Phi\right\},
\]
where $D \subset \F_n$ and $\Phi \subseteq 2^D$ are finite sets. Furthermore, we may assume without loss of generality that $D = \set{\gamma \in \F_n \,:\, |\gamma| \leq k}$ for some $k \in \N$, where $|\gamma|$ denotes the word norm of $\gamma$. For a vertex $x \in V(Q)$, we let $N^k(x)$ be the set of all vertices that are joined to $x$ by a path of length at most $k$. Since every connected component of $Q$ is a $d$-regular tree, we have $|N^k(x)| = |D|$ for all $x \in V(Q)$. This allows us to define a probability measure $\mu_k$ on $V(Q)$ via
\[
\mu_k(A) \,
\defeq\, \int \frac{\left|A \cap N^k(x)\right|}{|D|} \,\rmd\mu(x) \quad \text{for all Borel }\; A \subseteq V(Q).
\]

We have now prepared the ground for an application of Theorem~\ref{theo:Jan}. Fix $\epsilon > 0$ and let $\bm{p}$ be a partial Schreier decoration of $Q$ such that
\[
\mu_k(C(Q, \bm{p})) \,\geq\, 1 - \frac{\epsilon}{|D|},
\]
which exists by Theorem~\ref{theo:Jan}. Let $C_k$ be the set of all $x \in V(Q)$ such that $N^k(x) \subseteq C(Q, \bm{p})$. Then
\begin{multline*}
1 - \frac{\epsilon}{|D|} \,\leq\, \mu_k\left(C\left(Q, \bm{p}\right)\right) \\
\begin{aligned}
&=\, \int \frac{\left|C\left(Q, \bm{p}\right) \cap N^k(x)\right|}{|D|} \,\rmd\mu(x)
\leq\, \mu(C_k) + \left(1 - \frac{1}{|D|}\right)\left(1 - \mu\left(C_k\right)\right)\\
&=\, \frac{1}{|D|} \mu(C_k) + 1 - \frac{1}{|D|},
\end{aligned}
\end{multline*}
which implies that $\mu(C_k) \geq 1 - \epsilon$. The importance of the set $C_k$ lies in the fact that for each $x \in C_k$ and $\gamma \in D$, there is a natural way to define the notation $\gamma \cdot x$. Namely, we write $\gamma$ as a reduced word:
\[
\gamma \,=\, \sigma_{i_1}^{s_1} \cdots \sigma_{i_\ell}^{s_\ell},
\]
where $0 \leq \ell \leq k$, each index $i_j$ is between $1$ and $n$, and each $s_j$ is $1$ or $-1$. Since $N^k(x) \subseteq C(Q, \bm{p})$, there is a unique sequence $x_0$, $x_1$, \ldots, $x_\ell$ of vertices with
\[
x_0 = x \quad \text{and} \quad x_{j} = p_{i_j}^{s_j}\left(x_{j-1}\right) \text{ for all } 1 \leq j \leq \ell.
\]
We then set $\gamma \cdot x
\defeq x_\ell$. Note that we have $N^k(x) = \set{\gamma \cdot x \,:\, \gamma \in D}$.

The remainder of the argument utilizes a construction similar to the one in the proof of Theorem~\ref{theo:main} given in \S~\ref{sec:proof}. Consider the graph $R$ with the same vertex set as $Q$ in which two distinct vertices are adjacent if and only if they are joined by a path of length at most $2k$ in $Q$. Since every connected component of $Q$ is a $d$-regular tree, each vertex in $R$ has the same finite number of neighbors, so, by Theorem~\ref{theo:KST}, the Borel chromatic number $\chi_\rmB(R)$ is finite. Let $N
\defeq \chi_\rmB(R)$ and fix a Borel function $f \colon V(Q) \to N$ such that $f(u) \neq f(v)$ whenever $u$ and $v$ are adjacent in $R$. Then for each $x \in V(Q)$, the restriction of $f$ to the set $N^k(x)$ is injective. Now, to each mapping $\phi \colon N \to 2$, we associate function $\pi_\phi \colon C_k \to 2^D$ as follows:
\[
\pi_\phi(x)(\gamma) \,
\defeq\, (\phi \circ f)(\gamma \cdot x) \quad \text{for all } x \in C_k \text{ and } \gamma \in D.
\]
Let $I_\phi
\defeq \set{x \in C_k \,:\, \pi_\phi(x) \in \Phi}$. The independence of $I$ implies that the set $I_\phi$ is $Q$-independent. We will show that for some choice of $\phi \colon N \to 2$, $\mu(I_\phi) \geq (1-\epsilon) \beta(I)$. Since $\epsilon$ is arbitrary, this yields the desired bound $\alpha_\mu(Q) \geq \beta(I)$ and completes the proof of Lemma~\ref{lemma:AW}.

Consider any $x \in C_k$ and let
\[
S_x \,
\defeq\, \left\{f(\gamma \cdot x) \,:\, \gamma \in D\right\}.
\]
Since $f$ is injective on $N^k(x)$, $S_x$ is a subset of $N$ of size $|D|$. Whether or not $x$ is in $I_\phi$ is determined by the restriction of $\phi$ to $S_x$; furthermore, there are exactly $|\Phi|$ such restrictions that put $x$ in $I_\phi$. Thus, the number of mappings $\phi \colon N \to 2$ for which $x \in I_\phi$ is
\[
|\Phi|2^{N - |D|} \,=\, \beta(I)2^N.
\]
Since this holds for all $x \in C_k$, we conclude that
\[
\sum_{\phi\,\colon\,N\,\to\,2} \mu(I_\phi) \,\geq\, \mu\left(C_k\right) \beta(I)2^N \,\geq\, (1-\epsilon)\beta(I)2^N,
\]
where the second inequality uses that $\mu(C_k) \geq 1 - \epsilon$. In other words, the average value of $\mu(I_\phi)$ over all $\phi \colon N \to 2$ is at least $(1-\epsilon) \beta(I)$. Thus, the maximum is at least $(1-\epsilon) \beta(I)$ as well, and the proof is complete.
\end{proof}

\subsubsection*{Acknowledgement}
I am grateful to the anonymous referees for carefully reading this paper and providing helpful feedback.



\bibliography{bernshteyn}
\end{document}
