Definable Analogues of Finite Combinatorial Theorems

Definitions and mathematical statement

A standard Borel space is a measurable space isomorphic to the Borel measurable space of a Polish space. In the usual terminology, 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. Its maximum degree is $\Delta(G)=\sup_{x\in X}|\{y\in X:(x,y)\in E\}|$.

For a map $f:X\to Y$ to a standard Borel space, Borel measurability means that inverse images of Borel sets are Borel. When a measure $\mu$ on $X$ is specified, $\mu$-measurability is commonly understood using the completion of that measure. When a topology $\tau$ on $X$ is specified, $\tau$-Baire measurability means that inverse images of Borel sets have the Baire property: each differs from a $\tau$-open set by a $\tau$-meagre set. For combinatorial objects on edges or other configuration spaces, the relevant domain and its measurable or topological structure must also be specified.

Research question. Which results of finite combinatorics admit analogous conclusions for Borel graphs in which the required combinatorial objects can be chosen to be Borel, $\mu$-measurable, or $\tau$-Baire measurable? For each such result, determine the hypotheses on the graph, measure, and topology under which the respective analogue holds.

This is a research program, rather than a specified universally quantified transfer theorem. The supplied record does not select a finite theorem, a class of combinatorial objects, a precise meaning of "analogue," or quantifiers over graphs, measures, and topologies. In particular, it does not specify whether $\mu$ must be a probability measure, which compatibility conditions $\tau$ must satisfy, or whether the requested combinatorial properties must hold everywhere or only on a conull or comeagre set. The terminology above explains the usual framework without resolving these missing choices.

Supplied contextual result, not the open question. The original excerpt also reports a theorem attributed there to "B., Weilacher [4]": for a bipartite Borel graph $G$, \[ \chi'_{\mathrm{BM}}(G)\leq\Delta(G)+1, \] and, if $G$ is $\mu$-hyperfinite, \[ \chi'_{\mu}(G)\leq\Delta(G)+1. \] These symbols refer to Baire-measurable and $\mu$-measurable edge-chromatic numbers, respectively; a proper edge coloring assigns different colors to distinct edges sharing an endpoint. In standard measured terminology, $\mu$-hyperfiniteness concerns a conull Borel restriction on which the connectedness equivalence relation is an increasing union of Borel equivalence relations with finite classes. The excerpt does not give its precise hyperfiniteness convention, the definitions of the two chromatic numbers, the underlying topology and measure hypotheses, or an explicit finite-degree hypothesis. Thus the displayed bounds are preserved as source-reported context, requiring verification of their full hypotheses, and are not asserted here as independently verified theorems.

Short English statement

Determine which finite combinatorial results have Borel, measure-measurable, or Baire-measurable analogues for Borel graphs, and under what hypotheses. The supplied question describes a broad research program; it does not specify a single theorem to prove. Its accompanying edge-coloring bounds are reported background with incomplete hypotheses.

Sources

• Local registry: data/unsolvedmath/problems.json, permanent UnsolvedMath ID $30004997$, title "Definable Analogues of Finite Combinatorial Theorems," source problem code catalogue entry. The supplied record labels the problem "open" and its statement corrected_verified; it says that the statement was reconstructed and checked against the official report. These are supplied registry assertions, not independent verification here.
• Supplied report citation: Groups and Dynamics: Topology, Measure, and Borel Structure (2023), Oberwolfach Reports, pp. 107--169, DOI 10.4171/owr/2022/3. https://doi.org/10.4171/owr/2022/3. The registry gives proposed year 2022 and an owr-year:2022 tag; the relationship between these dates and the citation's 2023 date is unresolved.
• The original excerpt includes "Measurable combinatorics in hyperfinite graphs," attributed to Matt Bowen, with joint-work credits to Gabor Kun and Marcin Sabok; Felix Weilacher; Antoine Poulin and Jenna Zomback. It attributes the contextual theorem to "B., Weilacher [4]." The supplied record does not include the bibliographic entry numbered [4] or name a proposer of the broad question.
• Supplied literature source: Bernshteyn, Distributed algorithms, the Lovasz Local Lemma, and descriptive combinatorics. https://arxiv.org/abs/2004.04905.
• Supplied literature source: Conley--Jackson--Marks--Seward--Tucker-Drob, Hyperfiniteness and Borel combinatorics. https://arxiv.org/abs/1611.02204.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the program open, states that many Borel, measurable, and Baire analogues are known, and states that no general transfer principle from finite combinatorics is established. This is supplied dated curation derived from the OWR material, not an independently verified literature assessment. Its time-sensitive status and cited claims require independent checking.