Measurable Vizing’s theorem

Vizing’s theorem is a fundamental result in graph theory that relates the number of colors needed to properly color edges of a given graph $G$, the so-called chromatic index $\chi^{\prime}(G)$ of $G$, with its maximum degree; it states that if the maximum degree of $G$ is $\Delta\in\mathbb{N}$, then $\chi^{\prime}(G)\leqslant\Delta+1$. Together with König’s line coloring theorem (that states that $\chi^{\prime}(G)=\Delta$ under the additional assumption that $G$ is bipartite), these classical results laid the foundation of edge-colouring, an important and active area of graph theory; see, for example, the recent book on edge-colouring by Stiebitz, Scheide, Toft and Favrholdt [SSTF12].

In this paper we study Vizing’s theorem from the perspective of measurable graph combinatorics, a subfield of descriptive set theory that lies at the intersection of measure theory, random processes, dynamics, group theory, combinatorics and distributed computing; a (non-exhaustive) sample of results related to the field (and to our investigation) includes [Lac90, MU17, GMP17, DF92, MU16, Gab00, KST99, Mar16, CM17, CJM⁺23, CGM⁺17, GP20, Ber23, BCG⁺24]. In its most abstract form, measurable graph combinatorics systematically studies the existence of measurable or definable solutions to various graph coloring problems defined on so-called Borel graphs, graphs where the vertex set $(V,\mathcal{B})$ is a standard Borel space, for example the unit interval, and the edge relation $E$ is a Borel subset of $[V]^{2}$, where $[V]^{2}$ denotes the set of unordered pairs endowed with the canonical Borel structure coming from $V$. This study originated in the seminal paper of Kechris, Solecki and Todorčević [KST99] and since then found many applications in various areas of central mathematics, see the surveys of Kechris and Marks [KM20] and Pikhurko [Pik21].

Basic questions about vertex colorings of bounded degree Borel graphs are well-understood. Recall that the Borel chromatic number $\chi_{\mathcal{B}}(\mathcal{G})$ of a Borel graph $\mathcal{G}=(V,\mathcal{B},E)$ is the smallest $k\in\mathbb{N}$ such that there is a decomposition $V=V_{1}\sqcup\dots\sqcup V_{k}$, where $V_{i}$ is a Borel subset of $V$ that does not span any edge of $\mathcal{G}$ for every $i\in[k]$. In the paper [KST99] Kechris, Solecki and Todorčević showed that there is a Borel measurable version of the classical greedy algorithm for proper vertex coloring, thus proved that $\chi_{\mathcal{B}}(\mathcal{G})\leqslant\Delta+1$ for every Borel graph $\mathcal{G}=(V,\mathcal{B},E)$ of maximum degree $\Delta\in\mathbb{N}$. In the groundbreaking paper [Mar16], Marks found an example of acylic $\Delta$-regular Borel graph $\mathcal{G}$ such that $\chi_{\mathcal{B}}(\mathcal{G})=\Delta+1$ for every $\Delta\in\mathbb{N}$, thus concluding that there is no Borel analogue of the classical Brooks’ theorem from finite combinatorics. On the other hand, Conley, Marks and Tucker-Drob [CMTD16] proved that Brooks’ theorem holds once Borel measurability is relaxed either in the sense of measure theory or topology. For example, if $\mathcal{G}=(V,\mathcal{B},E)$ is a Borel graph of degree bounded by $\Delta\geqslant 3$ that does not contain a clique on $\Delta+1$ vertices and $\mu$ is a Borel probability measure on $(V,\mathcal{B})$, then there is a $\mu$-null Borel set $Y$ such that $\chi_{\mathcal{B}}(\mathcal{G}\upharpoonright(V\setminus Y))=\Delta$. Recently these results were refined by Bernshteyn [Ber23] and Brandt, Chang, the author, Grunau, Rozhoň, and Vidnyánszky [BCG⁺24] using ideas from the theory of distributed computing.

In contrast, similar questions about edge colorings are not yet fully understood. A Borel matching of a Borel graph $\mathcal{G}=(V,\mathcal{B},E)$ is a Borel subset $M\subseteq E$ that is a matching, i.e., every two edges $e,f\in M$ are either equal (as unordered pairs) or do not share a vertex. The Borel chromatic index $\chi^{\prime}_{B}(\mathcal{G})$ is defined to be the smallest $k\in\mathbb{N}$ such that there is a decomposition $E=E_{1}\sqcup\dots\sqcup E_{k}$, where $E_{i}$ is a Borel matching for every $i\in[k]$. Equivalently, this can be stated in the language of edge colorings as finding the smallest $k\in\mathbb{N}$ such that there is a Borel map $c:E\to[k]$ that is a proper edge coloring, i.e., $c(e)\not=c(f)$ whenever $e\not=f\in E$ share a vertex. The greedy upper bound [KST99] implies that $\chi^{\prime}_{B}(\mathcal{G})\leqslant 2\Delta-1$ for every Borel graph $\mathcal{G}$ of maximum degree bounded by $\Delta\in\mathbb{N}$. In the same paper [Mar16], Marks found an example of acylic $\Delta$-regular Borel graph $\mathcal{G}$ such that $\chi^{\prime}_{B}(\mathcal{G})=2\Delta-1$ for every $\Delta\in\mathbb{N}$. This shows that Borel analogue of Vizing’s theorem does not hold. Similarly as in the case of vertex colorings, it is natural to ask if Vizing’s theorem hold once Borel measurability is relaxed either in the sense of measure theory or topology. This question (for both measure and topology) is explicitly stated in the survey of Kechris and Marks [KM20, Problem 6.13]. Marks asked about the measurable relaxation for regular graphs [Mar16, Question 4.9], and, in fact, the same question for invariant measures, so-called graphings, was raised earlier by Abért [Abe10].

In this paper we completely resolve the measurable case, see Theorem 1.1. Before we state the result we formalize the definitions and discuss relevant results from recent years. Recall that we always assume that the Borel graph $\mathcal{G}=(V,\mathcal{B},E)$ in question has degree uniformly bounded by $\Delta\in\mathbb{N}$. Given a Borel probability measure $\mu$ on $(V,\mathcal{B})$, we define the $\mu$-chromatic index of $\mathcal{G}$, $\chi_{\mu}^{\prime}(\mathcal{G})$, to be the minimal $k\in\mathbb{N}$ such that there is a Borel map $c:E\to[k]$ that satisfies

where $c$ is not proper at $v\in V$ if there are edges $e\not=f\in E$ that are adjacent to $v$ and $c(e)=c(f)$. In another words, $c$ is a proper edge coloring at $\mu$-almost every vertex $v\in V$. We say that $\mu$ is $\mathcal{G}$-invariant, if $\mu(g(C))=\mu(C)$ for every $C\in\mathcal{B}$ and every Borel injection $g:C\to V$ that satisfies that $x$ and $g(x)$ are in the same connected component of $\mathcal{G}$ for every $x\in C$. In that case the quadruple $\mathcal{G}=(V,\mathcal{B},\mu,E)$ is called a graphing.

Csóka, Lippner and Pikhurko [CLP16] showed that $\chi^{\prime}_{\mu}(\mathcal{G})\leqslant\Delta+1$ for a graphing $\mathcal{G}=(V,\mathcal{B},\mu,E)$ that does not contain odd cycles and proved an upper bound of $\Delta+O(\sqrt{\Delta})$ colors for graphings in general. In a related result, Bernshteyn [Ber19, Theorem 1.3] proved that $\Delta+o(\Delta)$ colors are enough (even for the so-called list-colouring version) provided that the graphing factors to the shift action $\Gamma\curvearrowright[0,1]^{\Gamma}$ of a finitely generated group $\Gamma$. Answering the question of Abért, the author and Pikhurko [GP20] proved a measurable version of Vizing’s theorem for graphings, that is, $\chi^{\prime}_{\mu}(\mathcal{G})\leqslant\Delta+1$ for any graphing $\mathcal{G}=(V,\mathcal{B},\mu,E)$. Interestingly, the technique developed in [GP20] was greatly extended by Bernshteyn [Ber22] who found striking applications to the LOCAL model of distributed computing, see [Ber22, Chr23, BD23] for a current development in that direction.

Bernshteyn [Ber19], the author and Pikhurko [GP20], Tóth [T2́1] and the author [Gre22] investigated weaker notion of approximate edge colorings. In this setting, we require to find for each probability measure $\mu$ and $\epsilon>0$ a coloring of edges that is not correct or undefined for at most $\epsilon$ fraction of all edges. Here, the analogues of Vizing’s theorem as well as König’s line coloring theorem hold, see [GP20] and [Gre22].

Bowen and Weilacher [BW23] investigated Vizing’s theorem in the context of (Borel) asymptotic dimension introduced in [CJM⁺23]. As an application they derived that $\Delta+1$ colors are enough for edge colorings of bipartite graphs in the topological relaxation sense and for measures that are hyperfinite. Stronger results in the special case of free Borel $\mathbb{Z}^{d}$-actions, that is, Borel edge coloring with $2d$ colors which is the analogue of König’s line coloring theorem in this setting, were obtained independently around the same time in [BHT24, CU22, GR23, Wei21].

Recently, Qian and Weilacher [QW22] found connections of the topological relaxation to computable combinatorics which allowed them to derive an upper bound of $\Delta+2$ colors for the Baire measurable analogue of Vizing’s theorem, the full topological analogue, that is $\Delta+1$ colors only, remains an interesting open problem.

Next, we state our main result, which is the full analogue of Vizing’s theorem in the measurable setting.

In the proof we combine the technique of augmenting iterated Vizing chains introduced by the author and Pikhurko in [GP20] together with the following result, Theorem 1.2, that is interesting in its own right and might be useful for other applications as well.¹¹1After the first version of this paper appeared on arXiv, we were informed by Gábor Elek that Gabriella Kuhn [Kuh94, Lemma 1] proved the same result in the context of group actions, see Remark 1.3. Before we state the result, we need several definitions. Let $\mathcal{G}=(V,\mathcal{B},E)$ be a Borel graph and $\mu$ be a Borel probability measure on $(V,\mathcal{B})$. Recall that $\mu$ is called $\mathcal{G}$-quasi-invariant if $\mu([A]_{\mathcal{G}})=0$, whenever $\mu(A)=0$, where $[A]_{\mathcal{G}}$ is the union of all connected component of $\mathcal{G}$ that have non-empty intersection with $A$. It is a standard fact, see eg [KM04, Chapter II, Section 8], that if $\mu$ is $\mathcal{G}$-quasi-invariant, then there is a function $\rho_{\mu}$, called the Radon–Nikodym cocycle of $\mathcal{G}$, that takes values in $(0,+\infty)$, is defined for every ordered pair of points $x,y\in V$ that are in the same connected component of $\mathcal{G}$ and satisfies the following mass transport principle:

for every $C\subseteq V$ and an injective Borel map $g:C\to X$ that satisfies for every $x\in C$ that $g(x)$ is in the same connected component of $\mathcal{G}$ as $x$. While in general $\rho_{\mu}$ can behave chaotically, the next result shows that one can always pass to an equivalent measure $\nu$ such that $\rho_{\nu}$ is bounded on edges of $\mathcal{G}$.

Similar, stronger conditions on the cocycle was used by Conley and Tamuz [CT21]. They designed a procedure for solving the unfriendly coloring problem on graphs of degree bounded by $\Delta$, and showed that this procedure terminates off of a $\mu$-null set for every quasi-invariant Borel probability measure $\mu$ under the assumption that $1-1/\Delta\leqslant\rho_{\mu}(x,y)\leqslant 1+1/\Delta$ for every edge $\{x,y\}$ (this includes for example the case when $\mu$ is invariant). Finding a measurable unfriendly coloring for a general Borel probability measure remains an interesting open problem. In general, it would be nice to investigate if our condition has another applications in the context of local graph coloring problems.

The paper is structured as follows: in Section 2 we set the notation and recall basic results, in Section 3 we define the augmenting chains that we consider in this paper, so-called $3$-step Vizing chains, and estimate how many of them can be attached to an uncolored edge, in Section 4 we describe an infinite procedure that improves a given coloring so that it does not contain augmenting chains of small weight, in Section 5 we prove Theorem 1.2, that is, we show how to modify a given quasi-invariant measure to an equivalent measure that has bounded cocycle on edges, in Section 6 we describe the double counting argument that estimates the number of uncolored edges, and finally in Section 7 we combine all the results to prove Theorem 1.1.

Our basic descriptive set theory reference is [Kec95], see also [KM20, Pik21]. We mostly follow the notation developed in [GP20]. Let us point out that $\mathbb{N}$ contains $0$. If $k\in\mathbb{N}\setminus\{0\}$, then we write $[k]=\{1,2,\dots,k\}$. If $S$ is a set, then we write $[S]^{k}$ for the set of $k$-element subsets of $S$. In particular, $[S]^{2}$ is the set of unordered pairs of $S$. We follow a standard graph theoretic notation, i.e., a graph is a pair $G=(V,E)$, where $V\subseteq[E]^{2}$, $\operatorname{deg}_{G}(x)$ is the number of neighbors of $x$ in $G$, $\operatorname{dist}_{G}(x,y)$ denotes the graph distance of $x,y\in V$ in $G$, and $N_{G}(x)$ denotes the set of all edges of $G$ that are adjacent to $x$, i.e., $N_{G}(x)=\{e\in E:x\in e\}$.

Borel graphs    A Borel graph is a triplet $\mathcal{G}=(V,\mathcal{B},E)$, where $(V,\mathcal{B})$ is a standard Borel space, $(V,E)$ is a graph and $E$ is a Borel subset of $[V]^{2}$ (endowed with the natural $\sigma$-algebra inherited from the product $\sigma$-algebra $\mathcal{B}\times\mathcal{B}$ on $V\times V$). We say that $\mathcal{G}$ is of bounded maximum degree if there is $\Delta\in\mathbb{N}$ such that $\operatorname{deg}_{\mathcal{G}}(x)\leqslant\Delta$ for every $x\in V$. We write $\Delta(\mathcal{G})$ for smallest such $\Delta$. We denote the connectedness relation of $\mathcal{G}$ as $F_{\mathcal{G}}$. That is, $F_{\mathcal{G}}$ is an equivalence relation on $X$, and we write $[x]_{\mathcal{G}}$ for the $\mathcal{G}$-connectivity component of $x\in V$. If $\Delta(\mathcal{G})<\infty$, then $F_{\mathcal{G}}$ is a Borel subset of $V\times V$ and $|[x]_{\mathcal{G}}|$ is at most countable. Recall that an equivalence relation $F$ on a standard Borel space $(X,\mathcal{D})$ that is Borel as a subset of $X\times X$ and each $F$-equivalence class is at most countable is called a countable Borel equvialence relation (CBER) on $X$, see [Kec24]. In particular, if $\Delta(\mathcal{G})<\infty$, then $F_{\mathcal{G}}$ is a CBER on $V$. Given $A\subseteq X$, we write $[A]_{F}$ for the $F$-saturation of $A$ in $F$, i.e., the smallest $F$-invariant subset of $X$ that contains $A$. If $[A]_{F}=A$, then we say that $A$ is $F$-invariant. In case $F=F_{\mathcal{G}}$ we write simply $[A]_{\mathcal{G}}$, and say that $A$ is $\mathcal{G}$-invariant if it is $F_{\mathcal{G}}$-invariant. Observe that if $A$ is a Borel set, then so is $[A]_{F}$.

The line graph of a Borel graph $\mathcal{G}=(V,\mathcal{B},E)$ is the Borel graph $\mathcal{E}=(E,\mathcal{C},I_{\mathcal{G}})$, where $\mathcal{C}$ is the $\sigma$-algebra on $E$ inherited form $[V]^{2}$ and $(E,I_{\mathcal{G}})$ is the line graph of $(V,E)$, i.e., $\{e,f\}\in I_{\mathcal{G}}$ if and only if $e$ and $f$ share exactly one vertex. Observe that if $\Delta(\mathcal{G})<\infty$, then $\Delta(\mathcal{E})\leqslant 2\Delta(\mathcal{G})-2$. Similarly as above, $F_{\mathcal{E}}$ is the CBER on $E$ induced by the connectivity components of $\mathcal{E}$.

A Borel chromatic number $\chi_{\mathcal{B}}(\mathcal{G})$ of a Borel graph $\mathcal{G}$ is the minimal $k\in\mathbb{N}$ such that there is a Borel proper vertex coloring $d:V\to[k]$ of $\mathcal{G}$. Note that the subscript $\chi_{\mathcal{B}}$ refers to the corresponding $\sigma$-algebra. A Borel chromatic index $\chi^{\prime}_{\mathcal{B}}(\mathcal{G})$ is defined as $\chi_{\mathcal{C}}(\mathcal{E})$. That is $\chi^{\prime}_{\mathcal{B}}(\mathcal{G})=k$ if there is a Borel proper vertex coloring $c:E\to[k]$ of $\mathcal{E}$.

Measures    The set of all Borel probability measures on a standard Borel space $(X,\mathcal{B})$ is denoted as $\mathcal{P}(X)$. Let $F$ be a CBER on $X$ and $\mu\in\mathcal{P}(X)$. We say that $\mu$ is $F$-quasi invariant if $\mu([A]_{F})=0$, whenever $\mu(A)=0$. If $\mathcal{G}=(V,\mathcal{B},E)$ is a Borel graph then we say that $\mu\in\mathcal{P}(V)$ is $\mathcal{G}$-quasi-invariant if it is $F_{\mathcal{G}}$-quasi-invariant

A fundamental tool in the study of quasi-invariant measures is the Radon-Nikodym cocycle. Let $(X,\mathcal{B})$ be a standard Borel space, $F$ be a CBER on $X$ and $\mu\in\mathcal{P}(X)$ be $F$-quasi-invariant. Then the Radon–Nikodym cocycle (of $\mu$ with respect to $F$) is a Borel function $\rho_{\mu,F}:F\to\mathbb{R}_{>0}$ with the property that

for every $C\in\mathcal{B}$ and injective Borel map $g:C\to X$ such that $(x,g(x))\in F$. It is a standard fact that the Radon–Nikodym cocycle exists and it is unique up to null-sets, that is, if $\rho$ and $\rho^{\prime}$ are two Radon–Nikodym cocycles of $\mu$ with respect to $F$, then there is a $\mu$-conull $F$-invariant set $A\subseteq X$ such that

see [KM04]. The following statement summarizes the properties of cocycles that we need.

In case that $F=F_{\mathcal{G}}$, we write $\rho_{\mu,\mathcal{G}}$ instead of $\rho_{\mu,F_{\mathcal{G}}}$. If $F$ is clear from context, then we write simply $\rho_{\mu}$.

We show in Theorem 5.1 that every $\mathcal{G}$-quasi-invariant $\mu\in\mathcal{P}(V)$ is equivalent with a $\mathcal{G}$-bounded measure $\nu\in\mathcal{P}(V)$.

Let $\mathcal{G}=(V,\mathcal{B},E)$ be a Borel graph such that $\Delta(\mathcal{G})<\infty$. A partial (Borel proper edge) coloring of $\mathcal{G}$ is a partial Borel (with respect to the $\sigma$-algebra $\mathcal{C}$ on $E$, in particular, $\operatorname{dom}(c)\in\mathcal{C}$) map $c;E\to[\Delta(\mathcal{G})+1]$ that assigns different colors to different edges that share a vertex. Usually we use lower case Greek letters for colors, e.g. $\alpha,\beta\in[\Delta(\mathcal{G})+1]$. Given a partial coloring $c$, we define $m_{c}(x)$ to be the set of missing colors at $x\in V$, i.e., $m_{c}(x)=[\Delta(\mathcal{G})+1]\setminus\{c(e):e\in N_{\mathcal{G}}(x)\}$. We also write $U_{c}$ for the set of uncolored edges, i.e., $U_{c}=E\setminus\operatorname{dom}(c)$.

In order to improve a given partial coloring $c$, we utilize an idea from the proof of Vizing’s theorem, so called Vizing chains. In general, given an uncolored edge $e\in U_{c}$, we want to find an injective augmenting sequence of edges $W_{c}(e)=(e_{i})_{i\leqslant k}$ such that $e_{0}=e$, $e_{i}\cap e_{i+1}\not=\emptyset$ for $i\leqslant k$ and $e_{i}\not\in U_{c}$ for every $1\leqslant i\leqslant k$ with the property that keeping the colors outside of $W_{c}(e)$ intact but shifting the colors from $e_{i+1}$ to $e_{i}$ produces a different partial (proper) coloring $c^{\prime}$ such that $m_{c^{\prime}}(z_{0})\cap m_{c^{\prime}}(z_{1})\not=\emptyset$, where $\{z_{0},z_{1}\}=e_{k}$ is the last edge of $W_{c}(e)$. Extending $c^{\prime}$ by assigning any color from $m_{c^{\prime}}(z_{0})\cap m_{c^{\prime}}(z_{1})$ to $e_{k}$ then improves $c$ as we decreased the number of uncolored edges. Observe that the difference between $c$ and $c^{\prime}$ is contained in $W_{c}(e)$.

Various types of sequences $W_{c}(e)$ have been used in the literature. In order to prove classical Vizing’s theorem, one chooses $W_{c}(e)$ to be a concatenation of a so-called fan and an alternating path, also known as a Vizing chain. To prove an analogue of Vizing’s theorem for graphings, the author and Pikhurko [GP20] iterated this process two times. Namely, first we fix a Vizing chain, then truncate it at any edge on the alternating path, and then grow a second Vizing chain from that place; such a sequence is called an iterated Vizing chain. In order to devise efficient (both deterministic and randomized) local algorithms that produce a proper edge colorings with $\Delta+1$ colors on finite graphs, Bernshteyn [Ber22] iterated this process $\log(n)$ times, where $n$ is the number of vertices of the graph. Bernshteyn called the produced injective sequence a multi-step Vizing chain. In this paper, being ideologically more closer to [GP20], we iterate the process $3$ times. We follow the terminology of Bernshteyn and call this augmenting chain a $3$-step Vizing chain. The estimate for the number of $3$-step Vizing chains that can be assigned to a given uncolored edge follows the computation from [GP20]. It seems plausible that one can get similar estimate by adapting the results from finite graphs, but we decided to follow the more direct path of generalizing [GP20].