The measure half of the 2n+1 problem

Abstract

Let F_0,...,F_{n-1} be Borel self-maps of a standard Borel space X, and let G_F be the graph they generate. We prove that the total measurable chromatic number of G_F is at most 2n+1 for every n, answering the measure half of Problem 5.14 of Kechris and Marks with the optimal constant. No local countability, invariance of the measure, or finiteness of the Borel chromatic number is assumed. We further prove the corresponding result for every Borel (2n+1)-fold DP-cover and derive measurable list-colouring consequences over arbitrary standard Borel palettes. The proof uses an envelope measure, a fiberwise minimum-demand recolouring argument, Borel–Cantelli, and finite compactness.