Six Problems in Borel Graph Combinatorics

Definitions and mathematical statement

The supplied record collects six questions, some of which lack hypotheses needed for a unique precise formulation. The conventions below describe standard interpretations explicitly; they do not resolve omissions in the source.

A standard Borel space is a measurable space isomorphic to the Borel space of a Polish space. Under the usual simple-graph convention, a Borel graph is a pair $G=(X,E)$, where $X$ is a standard Borel space and $E\subseteq X\times X$ is Borel, symmetric, and irreflexive. Write $N_G(x)=\{y:(x,y)\in E\}$ and $\deg_G(x)=|N_G(x)|$. A proper Borel $k$-coloring is a Borel map $c:X\to\{1,\ldots,k\}$ satisfying $c(x)\ne c(y)$ whenever $(x,y)\in E$. The Borel chromatic number $\chi_B(G)$ is the least cardinality of a standard Borel color space admitting a proper Borel coloring. Only its finite values are needed below.

1. Borel Lovász Local Lemma for amenable actions. The source asks whether there is a Borel version of the Lovász Local Lemma for graphs generated by actions of amenable groups. In the customary setting, a countable discrete amenable group $\Gamma$ acts by Borel automorphisms on $X$, and a specified symmetric generating set $S\subseteq\Gamma$ gives the simple graph \[ E_S=\{(x,s\cdot x):x\in X,\ s\in S,\ s\cdot x\ne x\}. \] Here amenability may be defined as the existence of a left-translation-invariant finitely additive probability measure on all subsets of $\Gamma$. The source does not specify countability, the generating set, freeness of the action, the random variables and bad events, or the numerical local-lemma hypothesis. Consequently, it supplies a research question about a Borel local-lemma principle, but does not determine a particular quantified implication to formalize.

2. Borel Ruziewicz question. For every integer $n\geq2$, put \[ S^n=\{x\in{\mathbb{R}}^{n+1}:\|x\|_2=1\}, \] and let $\mathcal B(S^n)$ be its Borel $\sigma$-algebra. A nonnegative finitely additive measure is a map $\nu:\mathcal B(S^n)\to[0,\infty]$ with $\nu(\varnothing)=0$ and \[ \nu(A\cup B)=\nu(A)+\nu(B) \quad\text{for disjoint }A,B\in\mathcal B(S^n). \] The supplied wording asks whether Lebesgue measure on $S^n$ is the only finitely additive measure on this domain. It does not impose invariance, normalization, or finiteness, and does not specify the normalization of spherical Lebesgue measure. These are material omissions. For example, a possible intended formulation would fix a spherical probability measure $\sigma_n$ and a specified group $H$ acting on $S^n$, and ask whether \[ \left. \begin{gathered} \nu:\mathcal B(S^n)\to[0,1]\text{ is finitely additive},\\ \nu(S^n)=1,\\ \nu(hA)=\nu(A)\quad(h\in H,\ A\in\mathcal B(S^n)) \end{gathered} \right\} \Longrightarrow \nu=\sigma_n. \] This is only a conditional template: the record does not authorize choosing $H$, adding these hypotheses, or identifying this template with the intended question.

3. Unfriendly Borel colorings. Does every Borel graph $G=(X,E)$ satisfying $\sup_{x\in X}\deg_G(x)<\infty$ admit a Borel map $c:X\to\{0,1\}$ such that, for every $x\in X$, \[ \left|\{y\in N_G(x):c(y)\ne c(x)\}\right| \geq \left|\{y\in N_G(x):c(y)=c(x)\}\right|? \] Such a map is called an unfriendly coloring; it is not required to be proper.

4. Graphs generated by finitely many functions. One standard interpretation of generation by $n$ functions is that Borel maps $f_1,\ldots,f_n:X\to X$ generate the simple graph \[ E=\{(x,y):x\ne y\text{ and }\exists i\in\{1,\ldots,n\}\, (y=f_i(x)\text{ or }x=f_i(y))\}. \] Under this interpretation, the question is whether, for every such finite family and graph, \[ \chi_B(G)<\infty\quad\Longrightarrow\quad\chi_B(G)\leq2n+1. \] The source does not specify whether the generating functions must be total, may be partial, or satisfy additional restrictions. The displayed formulation is explicitly conditional on the total-Borel-function interpretation.

5. Baire measurable edge colorings. For every nonnegative integer $d$ and every Borel graph $G=(X,E)$ with $\deg_G(x)\leq d$ for all $x\in X$, does there exist a proper Baire measurable edge coloring \[ c:[E]\to\{1,\ldots,d+1\}, \] where $[E]=\{\{x,y\}:(x,y)\in E\}$, and properness means that distinct edges with a common endpoint receive distinct colors? For a specified topology on $[E]$, Baire measurability means that each color class has the Baire property, namely differs from an open set by a meagre set. A topology, or an equivalent convention for deriving an edge-space topology from a Polish vertex space, must be fixed. The supplied record specifies neither this topology nor whether the desired coloring is required on all edges or only after restriction to a comeagre vertex set. The displayed all-edges question follows the literal wording, subject to this unresolved topological qualification.

6. Bernoulli shift of the free group. Let $F_2=\langle a,b\rangle$, with usual symmetric generating set $\{a,a^{-1},b,b^{-1}\}$. For a specified probability space $(K,\kappa)$, its Bernoulli shift acts on $X=K^{F_2}$, with product measure $\mu=\kappa^{F_2}$, by \[ (g\cdot x)(h)=x(g^{-1}h). \] Let $G$ be the associated Schreier graph, under a specified convention concerning loops and the full space versus the free part of the action. The source asks for its measurable independence number and measurable chromatic number. A standard measurable independence number is \[ \alpha_\mu(G)=\sup\{\mu(A):A\subseteq X\text{ is }\mu\text{-measurable and independent in }G\}, \] where independence means that no edge has both endpoints in $A$. One common almost-everywhere chromatic convention asks for the least number of colors in a measurable proper coloring of $G\upharpoonright X_0$, where $X_0$ is a measurable invariant conull subset of $X$. Requiring properness everywhere is another convention. The record gives neither the Bernoulli base $(K,\kappa)$ nor these domain and measurability conventions. Thus it does not determine a single pair of numerical invariants to compute.

The registry labels this collection partially_solved and its statement corrected_verified. These are supplied curation labels, not mathematical conclusions established by this draft. The supplied assessment reports major partial or complete results for several topics, including measurable local lemmas, measurable edge colorings, and the classical Banach--Ruziewicz problem, while describing the full Borel and Bernoulli-shift questions as unresolved. It does not identify exact results resolving each formulation above.

Short English statement

This record collects six questions about Borel local lemmas, finitely additive measures on spheres, unfriendly colorings, Borel chromatic bounds, Baire measurable edge colorings, and measurable invariants of a free-group Bernoulli shift. The unfriendly-coloring question has a direct precise formulation under standard graph conventions. Several other questions require missing hypotheses or conventions, especially invariance and normalization for the measure question and the probability space for the Bernoulli shift. The supplied partial-resolution assessment requires independent review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30005021$, title Six Problems in Borel Graph Combinatorics, exact source problem code catalogue entry, in the collection Oberwolfach Reports Open Problems. No individual proposer is supplied.
• Supplied report citation: Mini-Workshop: Descriptive Combinatorics, LOCAL Algorithms and Random Processes (2023), Oberwolfach Reports, DOI 10.4171/owr/2022/8, pp. 429--455. Source URL and literature-source link: https://doi.org/10.4171/owr/2022/8. The record separately gives proposed year 2022 and an owr-year:2022 tag; the year discrepancy is unresolved here.
• Supplied literature source: Bernshteyn, measurable Lovász Local Lemma, https://doi.org/10.1016/j.aam.2019.06.031. No full bibliographic entry or precise theorem is supplied.
• Supplied literature source: Margulis, invariant measures and Ruziewicz problem, https://www.cambridge.org/core/journals/ergodic-theory-and-dynamical-systems/article/finitelyadditive-invariant-measures-on-euclidean-spaces/82B5E841B3A74C06F05313B67AC8885D. No precise theorem connecting this reference to the incompletely specified Borel question is supplied.
• Literature assessment date: 2026-08-22. This is supplied dated curation, not independently verified. Its assessment states that several questions have major partial or complete results and that full Borel and Bernoulli-shift questions remain unresolved; the record itself calls for independent verification of time-sensitive status and cited claims.
• The record states that its reconstructed statement was checked against the official report. That verification claim is supplied provenance only; no source was visited for this draft. The original excerpt also contains the heading "Problem Session Jan Grebík" and the beginning of a discussion of local problems on oriented paths. Its relationship to authorship of the six questions is unspecified.