\begin{filecontents*}[overwrite]{\jobname.bib}
@article{Bernshteyn23,
  author={A. Bernshteyn},
  title={Distributed algorithms, the {Lov\'asz Local Lemma}, and descriptive combinatorics},
  journal={Inventiones Mathematicae},
  volume={233},
  pages={495--542},
  year={2023},
  doi={10.1007/s00222-023-01188-3},
  note={arXiv:2004.04905}
}

@article{Bernshteyn22,
  author={A. Bernshteyn},
  title={{Borel} fractional colorings of {Schreier} graphs},
  journal={Annales Henri Lebesgue},
  volume={5},
  pages={1151--1160},
  year={2022},
  doi={10.5802/ahl.145},
  note={arXiv:2105.11557}
}

@article{RahmanVirag17,
  author={M. Rahman and B. Vir\'ag},
  title={Local algorithms for independent sets are half-optimal},
  journal={The Annals of Probability},
  volume={45},
  pages={1543--1577},
  year={2017},
  doi={10.1214/16-AOP1094},
  note={arXiv:1402.0485}
}

@article{MartinssonSteiner25,
  author={A. Martinsson and R. Steiner},
  title={Random independent sets in triangle-free graphs},
  journal={Forum of Mathematics, Sigma},
  volume={13},
  pages={e156},
  year={2025},
  doi={10.1017/fms.2025.10112}
}

@article{Molloy19,
  author={M. Molloy},
  title={The list chromatic number of graphs with small clique number},
  journal={Journal of Combinatorial Theory, Series B},
  volume={134},
  pages={264--284},
  year={2019},
  doi={10.1016/j.jctb.2018.06.007},
  note={arXiv:1701.09133}
}

@article{PettieSu15,
  author={S. Pettie and H.-H. Su},
  title={Distributed coloring algorithms for triangle-free graphs},
  journal={Information and Computation},
  volume={243},
  pages={263--280},
  year={2015},
  doi={10.1016/j.ic.2014.12.018}
}

@article{ChungPettieSu17,
  author={K.-M. Chung and S. Pettie and H.-H. Su},
  title={Distributed algorithms for the {Lov\'asz} local lemma and graph coloring},
  journal={Distributed Computing},
  volume={30},
  pages={261--280},
  year={2017},
  doi={10.1007/s00446-016-0287-6}
}

@unpublished{DaviesPeckZhang26,
  author={P. Davies-Peck and X. Zhang},
  title={Triangle-Free Coloring in {LOCAL} via Resilient {Lov\'asz Local Lemma}},
  year={2026},
  note={arXiv:2608.13357}
}

@article{Freedman75,
  author={D. A. Freedman},
  title={On tail probabilities for martingales},
  journal={The Annals of Probability},
  volume={3},
  pages={100--118},
  year={1975},
  doi={10.1214/aop/1176996452}
}

@article{KechrisSoleckiTodorcevic99,
  author={A. S. Kechris and S. Solecki and S. Todorcevic},
  title={{Borel} chromatic numbers},
  journal={Advances in Mathematics},
  volume={141},
  pages={1--44},
  year={1999},
  doi={10.1006/aima.1998.1771}
}

@article{MoserTardos10,
  author={R. A. Moser and G. Tardos},
  title={A constructive proof of the general {Lov\'asz Local Lemma}},
  journal={Journal of the ACM},
  volume={57},
  pages={11:1--11:15},
  year={2010},
  doi={10.1145/1667053.1667060},
  note={arXiv:0903.0544}
}

@inproceedings{FischerGhaffari17,
  author={M. Fischer and M. Ghaffari},
  title={Sublogarithmic distributed algorithms for {Lov\'asz Local Lemma}, and the complexity hierarchy},
  booktitle={31st International Symposium on Distributed Computing},
  series={Leibniz International Proceedings in Informatics},
  volume={91},
  pages={18:1--18:16},
  year={2017},
  doi={10.4230/LIPIcs.DISC.2017.18},
  note={arXiv:1705.04840}
}

@inproceedings{Iliopoulos18,
  author={F. Iliopoulos},
  title={Commutative algorithms approximate the {LLL}-distribution},
  booktitle={Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques},
  series={Leibniz International Proceedings in Informatics},
  volume={116},
  pages={44:1--44:20},
  year={2018},
  doi={10.4230/LIPIcs.APPROX-RANDOM.2018.44},
  note={arXiv:1704.02796}
}

@article{BeiglbockNutz14,
  author={M. Beiglb{\"o}ck and M. Nutz},
  title={Martingale inequalities and deterministic counterparts},
  journal={Electronic Journal of Probability},
  volume={19},
  pages={1--15},
  year={2014},
  doi={10.1214/EJP.v19-3270},
  note={arXiv:1401.4698}
}

@book{Kechris95,
  author={A. S. Kechris},
  title={Classical Descriptive Set Theory},
  series={Graduate Texts in Mathematics},
  volume={156},
  publisher={Springer-Verlag},
  address={New York},
  year={1995},
  doi={10.1007/978-1-4612-4190-4}
}

@article{deBruijnErdos51,
  author={N. G. de Bruijn and P. Erd\H{o}s},
  title={A colour problem for infinite graphs and a problem in the theory of relations},
  journal={Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen, Series A},
  volume={54},
  pages={371--373},
  year={1951}
}

@inproceedings{ChungPettieSu14,
  author={K.-M. Chung and S. Pettie and H.-H. Su},
  title={Distributed algorithms for the {Lov\'asz} local lemma and graph coloring},
  booktitle={Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing},
  publisher={ACM},
  pages={134--143},
  year={2014},
  doi={10.1145/2611462.2611465}
}

% Further references used in the detailed proofs.
@book{Durrett19,
  author={R. Durrett},
  title={Probability: Theory and Examples},
  edition={Fifth},
  series={Cambridge Series in Statistical and Probabilistic Mathematics},
  volume={49},
  publisher={Cambridge University Press},
  address={Cambridge},
  year={2019},
  doi={10.1017/9781108591034},
  url={https://sites.math.duke.edu/~rtd/PTE/PTE5_011119.pdf},
  note={Author's 11 January 2019 version: \url{https://sites.math.duke.edu/~rtd/PTE/PTE5_011119.pdf}}
}


@article{ConleyKechrisTuckerDrob13,
  author={C. T. Conley and A. S. Kechris and R. D. Tucker-Drob},
  title={Ultraproducts of measure preserving actions and graph combinatorics},
  journal={Ergodic Theory and Dynamical Systems},
  volume={33},
  pages={334--374},
  year={2013},
  doi={10.1017/S0143385711001143},
  url={https://people.clas.ufl.edu/r-tuckerdrob/files/Conley-Kechris-Tucker_Drob.pdf},
  note={Author preprint: \url{https://people.clas.ufl.edu/r-tuckerdrob/files/Conley-Kechris-Tucker_Drob.pdf}}
}

@article{HatamiLovaszSzegedy14,
  author={H. Hatami and L. Lov{\'a}sz and B. Szegedy},
  title={Limits of locally--globally convergent graph sequences},
  journal={Geometric and Functional Analysis},
  volume={24},
  pages={269--296},
  year={2014},
  doi={10.1007/s00039-014-0258-7},
  note={arXiv:1205.4356}
}

@article{BackhauszSzegedyVirag15,
  author={{\'A}. Backhausz and B. Szegedy and B. Vir{\'a}g},
  title={Ramanujan graphings and correlation decay in local algorithms},
  journal={Random Structures \& Algorithms},
  volume={47},
  pages={424--435},
  year={2015},
  doi={10.1002/rsa.20562},
  note={arXiv:1305.6784}
}

@unpublished{Thornton24,
  author={R. Thornton},
  title={Factor maps for automorphism groups via {Cayley} diagrams},
  year={2024},
  note={arXiv:2011.14604v4}
}
@unpublished{FlinGhaffariHalldorssonMausNolin26,
  author={M. Flin and M. Ghaffari and M. M. Halld{\'o}rsson and Y. Maus and A. Nolin},
  title={{LOCAL LLL} in {$\operatorname{poly}(\log\log n)$} rounds},
  year={2026},
  note={arXiv:2610.17133}
}

@inproceedings{Davies23,
  author={P. Davies},
  title={Improved distributed algorithms for the {Lov\'asz Local Lemma} and edge coloring},
  booktitle={Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms},
  publisher={SIAM},
  pages={4273--4295},
  year={2023},
  doi={10.1137/1.9781611977554.ch163}
}

@unpublished{Davies22,
  author={P. Davies},
  title={Improved distributed algorithms for the {Lov\'asz Local Lemma} and edge coloring},
  year={2022},
  note={arXiv:2208.08701}
}

@article{ChangLiPettie20,
  author={Y.-J. Chang and W. Li and S. Pettie},
  title={Distributed {$(\Delta+1)$}-coloring via ultrafast graph shattering},
  journal={SIAM Journal on Computing},
  volume={49},
  pages={497--539},
  year={2020},
  doi={10.1137/19M1249527},
  note={arXiv:1711.01361}
}

@inproceedings{RozhonGhaffari20,
  author={V. Rozho{\v n} and M. Ghaffari},
  title={Polylogarithmic-time deterministic network decomposition and distributed derandomization},
  booktitle={Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing},
  publisher={ACM},
  pages={350--363},
  year={2020},
  doi={10.1145/3357713.3384298},
  note={arXiv:1907.10937}
}

@inproceedings{GhaffariHarrisKuhn18,
  author={M. Ghaffari and D. G. Harris and F. Kuhn},
  title={On derandomizing local distributed algorithms},
  booktitle={2018 IEEE 59th Annual Symposium on Foundations of Computer Science},
  publisher={IEEE},
  pages={662--673},
  year={2018},
  doi={10.1109/FOCS.2018.00069},
  note={arXiv:1711.02194}
}

@inproceedings{AssadiYazdanyar26,
  author={S. Assadi and H. Yazdanyar},
  title={Fully dynamic algorithms for coloring triangle-free graphs},
  booktitle={53rd International Colloquium on Automata, Languages, and Programming},
  series={Leibniz International Proceedings in Informatics},
  volume={374},
  pages={16:1--16:22},
  year={2026},
  doi={10.4230/LIPIcs.ICALP.2026.16},
  note={arXiv:2604.20648}
}

@article{BoucheronLugosiMassart00,
  author={S. Boucheron and G. Lugosi and P. Massart},
  title={A sharp concentration inequality with applications},
  journal={Random Structures \& Algorithms},
  volume={16},
  pages={277--292},
  year={2000},
  doi={10.1002/(SICI)1098-2418(200005)16:3<277::AID-RSA4>3.0.CO;2-1}
}

@article{BoucheronLugosiMassart09,
  author={S. Boucheron and G. Lugosi and P. Massart},
  title={On concentration of self-bounding functions},
  journal={Electronic Journal of Probability},
  volume={14},
  pages={1884--1899},
  year={2009},
  doi={10.1214/EJP.v14-690}
}

@unpublished{Vondrak10,
  author={J. Vondr{\'a}k},
  title={A note on concentration of submodular functions},
  year={2010},
  note={arXiv:1005.2791}
}
@article{Tropp11,
  author={J. A. Tropp},
  title={{Freedman}'s inequality for matrix martingales},
  journal={Electronic Communications in Probability},
  volume={16},
  pages={262--270},
  year={2011},
  doi={10.1214/ECP.v16-1624},
  url={https://tropp.caltech.edu/papers/Tro11-Freedmans-Inequality.pdf}
}

@article{KotzingKrejca19,
  author={T. K{\"o}tzing and M. S. Krejca},
  title={First-hitting times under drift},
  journal={Theoretical Computer Science},
  volume={796},
  pages={51--69},
  year={2019},
  doi={10.1016/j.tcs.2019.08.021},
  url={https://hpi.de/friedrich/docs/publications/2019/TCS_a.pdf}
}

@article{Hajek82,
  author={B. Hajek},
  title={Hitting-time and occupation-time bounds implied by drift analysis with applications},
  journal={Advances in Applied Probability},
  volume={14},
  pages={502--525},
  year={1982},
  doi={10.2307/1426671}
}

@article{McDiarmidReed06,
  author={C. McDiarmid and B. Reed},
  title={Concentration for self-bounding functions and an inequality of {Talagrand}},
  journal={Random Structures \& Algorithms},
  volume={29},
  pages={549--557},
  year={2006},
  doi={10.1002/rsa.20145}
}

@article{Rolin75,
  author={J.-M. Rolin},
  title={The inverse of a continuous additive functional},
  journal={Pacific Journal of Mathematics},
  volume={58},
  pages={585--604},
  year={1975},
  doi={10.2140/pjm.1975.58.585},
  url={https://msp.org/pjm/1975/58-2/pjm-v58-n2-p31-p.pdf}
}
@article{BernshteynWeilacher25,
  author={A. Bernshteyn and F. Weilacher},
  title={{Borel} versions of the {Local Lemma} and {LOCAL} algorithms for graphs of finite asymptotic separation index},
  journal={Transactions of the American Mathematical Society},
  volume={378},
  pages={8183--8221},
  year={2025},
  doi={10.1090/tran/9455}
}

@article{Marks16,
  author={A. S. Marks},
  title={A determinacy approach to {Borel} combinatorics},
  journal={Journal of the American Mathematical Society},
  volume={29},
  pages={579--600},
  year={2016},
  doi={10.1090/jams/836}
}

@unpublished{Weilacher26,
  author={F. Weilacher},
  title={{Borel} homomorphisms from forests to {Kneser} graphs},
  year={2026},
  note={arXiv:2601.19045}
}

@incollection{Pikhurko21,
  author={O. Pikhurko},
  title={{Borel} combinatorics of locally finite graphs},
  booktitle={Surveys in Combinatorics 2021},
  editor={K. K. Dabrowski and M. Gadouleau and N. Georgiou and M. Johnson and G. B. Mertzios and D. Paulusma},
  series={London Mathematical Society Lecture Note Series},
  volume={470},
  publisher={Cambridge University Press},
  pages={267--320},
  year={2021},
  doi={10.1017/9781009036214.008}
}

@article{Bollobas78,
  author={B. Bollob{\'a}s},
  title={Chromatic number, girth and maximal degree},
  journal={Discrete Mathematics},
  volume={24},
  pages={311--314},
  year={1978},
  doi={10.1016/0012-365X(78)90102-4}
}

@article{Bollobas81,
  author={B. Bollob{\'a}s},
  title={The independence ratio of regular graphs},
  journal={Proceedings of the American Mathematical Society},
  volume={83},
  pages={433--436},
  year={1981},
  doi={10.1090/S0002-9939-1981-0624948-6}
}
@article{AjtaiKomlosSzemeredi80,
  author={M. Ajtai and J. Koml{\'o}s and E. Szemer{\'e}di},
  title={A note on {Ramsey} numbers},
  journal={Journal of Combinatorial Theory, Series A},
  volume={29},
  pages={354--360},
  year={1980},
  doi={10.1016/0097-3165(80)90030-8}
}

@article{Shearer83,
  author={J. B. Shearer},
  title={A note on the independence number of triangle-free graphs},
  journal={Discrete Mathematics},
  volume={46},
  pages={83--87},
  year={1983},
  doi={10.1016/0012-365X(83)90273-X}
}

@article{Kim95,
  author={J. H. Kim},
  title={The {Ramsey} number {$R(3,t)$} has order of magnitude {$t^2/\log t$}},
  journal={Random Structures \& Algorithms},
  volume={7},
  pages={173--207},
  year={1995},
  doi={10.1002/rsa.3240070302}
}

@article{BohmanKeevash21,
  author={T. Bohman and P. Keevash},
  title={Dynamic concentration of the triangle-free process},
  journal={Random Structures \& Algorithms},
  volume={58},
  pages={221--293},
  year={2021},
  doi={10.1002/rsa.20973}
}

@article{FizPontiverosGriffithsMorris20,
  author={G. {Fiz Pontiveros} and S. Griffiths and R. Morris},
  title={The triangle-free process and the {Ramsey} number {$R(3,k)$}},
  journal={Memoirs of the American Mathematical Society},
  volume={263},
  pages={v+125},
  year={2020},
  doi={10.1090/memo/1274},
  note={Memoir 1274}
}

@unpublished{CamposJenssenMichelenSahasrabudhe25,
  author={M. Campos and M. Jenssen and M. Michelen and J. Sahasrabudhe},
  title={A new lower bound for the {Ramsey} numbers {$R(3,k)$}},
  year={2025},
  note={arXiv:2505.13371}
}

@unpublished{HeftyHornKingPfender25,
  author={Z. Hefty and P. Horn and D. King and F. Pfender},
  title={Improving {$R(3,k)$} in just two bites},
  year={2025},
  note={arXiv:2510.19718}
}

@book{MolloyReed02,
  author={M. Molloy and B. Reed},
  title={Graph Colouring and the Probabilistic Method},
  series={Algorithms and Combinatorics},
  volume={23},
  publisher={Springer-Verlag},
  address={Berlin},
  year={2002},
  doi={10.1007/978-3-642-04016-0}
}

@article{DaviesJenssenPerkinsRoberts18,
  author={E. Davies and M. Jenssen and W. Perkins and B. Roberts},
  title={On the average size of independent sets in triangle-free graphs},
  journal={Proceedings of the American Mathematical Society},
  volume={146},
  pages={111--124},
  year={2018},
  doi={10.1090/proc/13728},
  note={arXiv:1606.01043}
}

@article{KellyPostle24,
  author={T. Kelly and L. Postle},
  title={Fractional coloring with local demands and applications to degree-sequence bounds on the independence number},
  journal={Journal of Combinatorial Theory, Series B},
  volume={169},
  pages={298--337},
  year={2024},
  doi={10.1016/j.jctb.2024.07.002},
  note={arXiv:1811.11806}
}

@unpublished{GhaffariHalldorssonMausNolin26,
  author={M. Ghaffari and M. M. Halld{\'o}rsson and Y. Maus and A. Nolin},
  title={Robust shattering arguments},
  year={2026},
  note={arXiv:2606.27847}
}

@article{BernshteynBrazeltonCaoKang23,
  author={A. Bernshteyn and T. Brazelton and R. Cao and A. Kang},
  title={Counting colorings of triangle-free graphs},
  journal={Journal of Combinatorial Theory, Series B},
  volume={161},
  pages={86--108},
  year={2023},
  doi={10.1016/j.jctb.2023.02.004},
  note={arXiv:2109.13376}
}

@unpublished{BuysvanDenHeuvelKang25,
  author={P. Buys and J. van den Heuvel and R. J. Kang},
  title={Triangle-free graphs with the fewest independent sets},
  year={2025},
  note={To appear in Combinatorica; arXiv:2503.10002}
}

@unpublished{HarrisHeftyHornKingPfender26,
  author={S. Harris and Z. Hefty and P. Horn and D. King and F. Pfender},
  title={A short proof that {$R(3,k)=\Theta(k^2/\log k)$}},
  year={2026},
  note={arXiv:2609.01782}
}

@article{CsokaGrabowskiMathePikhurkoTyros26,
  author={E. Cs{\'o}ka and {\L}. Grabowski and A. M{\'a}th{\'e} and O. Pikhurko and K. Tyros},
  title={{Moser--Tardos Algorithm} with small number of random bits},
  journal={Journal of the European Mathematical Society},
  year={2026},
  doi={10.4171/JEMS/1815},
  note={Published online first; arXiv:2203.05888}
}

@article{conley2023borel,
  title={Borel asymptotic dimension and hyperfinite equivalence relations},
  author={Conley, Clinton T and Jackson, Steve C and Marks, Andrew S and Seward, Brandon M and Tucker-Drob, Robin D},
  journal={Duke Mathematical Journal},
  volume={172},
  number={16},
  pages={3175--3226},
  year={2023},
  publisher={Duke University Press}
}

@article{conley2017bound,
  title={A bound on measurable chromatic numbers of locally finite Borel graphs},
  author={Conley, Clinton T and Miller, Benjamin D},
  journal={Mathematical Research Letters},
  volume={23},
  number={6},
  pages={1633--1644},
  year={2016},
  publisher={International Press of Boston, Inc. Somerville, MA 02143, USA}
}


@article{ConleyMiller16,
  author={C. T. Conley and B. D. Miller},
  title={A bound on measurable chromatic numbers of locally finite {Borel} graphs},
  journal={Mathematical Research Letters},
  volume={23},
  pages={1633--1644},
  year={2016},
  doi={10.4310/MRL.2016.v23.n6.a3}
}

\end{filecontents*}
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern,amsmath,amssymb,amsthm}
\usepackage[margin=1in]{geometry}
\usepackage{microtype}
\usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}
\numberwithin{equation}{section}
\setlength{\emergencystretch}{2em}
\newcommand{\ai}[1]{{\color{red} AI: #1}}
\newcommand{\hide}[1]{}



\title{Local independent sets and colourings\\of triangle-free graphs}
\author{Matthew Bowen\thanks{Mathematics Institute, University of Warwick,  Coventry CV4 7AL, UK}
\and
Andr\'as M\'ath\'e\footnotemark[1] \and
Oleg Pikhurko\thanks{Mathematics Institute and DIMAP, University of Warwick,  Coventry CV4 7AL, UK}}
%\date{}
\hypersetup{pdftitle={Local independent sets and colourings of triangle-free graphs},
  pdfauthor={Matthew Bowen, Andr\'as M\'ath\'e and Oleg Pikhurko}}
\begin{document}
\maketitle
\begin{abstract}
This AI-assisted draft constructs, for every sufficiently large $D$, a local rule of radius $O((\ln D)^2)$ that produces, on any triangle-free graph $G$ of maximum degree at most $D$, a random independent set that includes each vertex with probability at least $(1-o_D(1))\ln D/D$. Further properties of the rule yield, for every fixed $\varepsilon>0$ and all sufficiently large $D$, a randomised LOCAL algorithm that colours any such finite graph $G$ with at most $(1+\varepsilon)D/\ln D$ colours, with high probability, in $O_\varepsilon(\ln D)+(\ln\ln |V(G)|)^{O(1)}$ communication rounds. Applying known transference principles for Borel graphs, we obtain the same asymptotic bound on the number of colours for measurable and Baire-measurable colourings, and for Borel colourings of graphs with finite asymptotic separation index.
\end{abstract}
\setcounter{tocdepth}{1}
{\small\tableofcontents}
\clearpage

\section{Introduction}\label{sec:introduction}
The study of independent sets in triangle-free graphs is closely related
to the Ramsey number $R(3,k)$, the least integer $n$ such that every
triangle-free graph on $n$ vertices has an independent set of size $k$.
Following the work of Ajtai, Koml\'os and Szemer\'edi
\cite{AjtaiKomlosSzemeredi80}, Shearer \cite[Theorem~1]{Shearer83}
proved that every triangle-free graph $G$ on $n$ vertices with average
degree $d$ satisfies, with $\alpha(G)$ denoting its independence number,
\begin{equation}\label{eq:intro-shearer}
 \alpha(G)\ge(1-o(1))\frac{n\ln d}{d}
 \quad\text{as }d\to\infty.
\end{equation}
Since each neighbourhood is independent, this also gives
$R(3,k)\le(1+o(1))k^2/\ln k$.
Kim's construction \cite[Theorem~1.1]{Kim95} established a matching
lower bound up to a constant factor. The lower coefficient was later
improved to $1/4$ by Bohman and Keevash
\cite[Theorem~1.3]{BohmanKeevash21} and, independently, Fiz Pontiveros,
Griffiths and Morris
\cite[Theorem~1.2]{FizPontiverosGriffithsMorris20}, then to $1/3$ by
Campos, Jenssen, Michelen and Sahasrabudhe
\cite[Theorem~1.1]{CamposJenssenMichelenSahasrabudhe25}, and to $1/2$ by
Hefty, Horn, King and Pfender
\cite[Theorem~1.2]{HeftyHornKingPfender25}. Thus the current bounds are
\begin{equation}\label{eq:intro-ramsey}
 \left(\frac12-o(1)\right)\frac{k^2}{\ln k}
 \le R(3,k)\le(1+o(1))\frac{k^2}{\ln k}.
\end{equation}
For a short proof of the order of magnitude, see Harris, Hefty, Horn,
King and Pfender
\cite[Theorem~1.2 and Corollary~5.2]{HarrisHeftyHornKingPfender26}.

For colouring, Johansson proved that every triangle-free graph of
maximum degree at most $D$ has chromatic number $O(D/\ln D)$;
see Molloy and Reed \cite[Theorem~13.1]{MolloyReed02} for a published
proof. Molloy \cite[Theorem~1]{Molloy19} strengthened this to
$(1+o(1))D/\ln D$, even for list colouring.
Related lower bounds on the number of proper colourings at this
scale were obtained by Bernshteyn, Brazelton, Cao and Kang
\cite[Theorem~1.2]{BernshteynBrazeltonCaoKang23}.
On the other hand, a theorem of Bollob\'as
\cite[Theorem~1 and Corollary~3]{Bollobas81} gives finite triangle-free graphs of
maximum degree $D$ with chromatic number at least
$(1/2-o(1))D/\ln D$.
The optimal leading coefficient for finite graphs is therefore still
unknown. We obtain the coefficient $1$ under additional requirements
of locality or definability, and show that it is optimal in several
of these settings.

The independent-set bound also has refinements concerning probability
distributions. Davies, Jenssen, Perkins and Roberts
\cite[Theorem~1]{DaviesJenssenPerkinsRoberts18} showed that a uniformly
random independent set in an $n$-vertex triangle-free graph of maximum degree
at most $D$ has expected size at least $(1-o(1))n\ln D/D$.
Lower bounds on the number of independent sets in terms of the
average degree were obtained by Buys, van den Heuvel and Kang
\cite[Theorem~1]{BuysvanDenHeuvelKang25}.
More recently, Martinsson and Steiner
\cite[Theorem~1.2]{MartinssonSteiner25} proved that every finite
triangle-free graph has a distribution on independent sets for which each vertex $v$ of positive degree is
included with probability at least
$(1-o(1))\ln d(v)/d(v)$, where the error tends to zero with $d(v)$.
This resolves the local fractional-colouring conjecture of Kelly
and Postle \cite[Conjecture~2.2]{KellyPostle24}.
For a fixed maximum-degree bound $D$, we seek the uniform marginal
$(1-o(1))\ln D/D$ under the additional requirement that each decision
be determined by independent labels in a ball whose radius depends
only on $D$.

Our first result produces such an independent set by a local rule.
We give each vertex an independent uniform label from a finite
alphabet $\Lambda$. Write $B_G(v,R)$ for the vertices at distance
at most $R$ from $v$.
A rule has \emph{determining radius} $R$ if its decision at $v$ is
determined by the labelled graph induced on $B_G(v,R)$, with $v$
distinguished as the root. The rule must be invariant under
isomorphisms of labelled rooted neighbourhoods. In particular, it
uses no vertex ordering or identifiers.
The construction is based on the ordered independent-set process of
Martinsson and Steiner \cite[Section~4]{MartinssonSteiner25}.
We adapt their forced-decline comparison and preservation of weights
in expectation \cite[Claims~4.2 and~4.3]{MartinssonSteiner25}, replacing
the vertex ordering by finitely many random priority classes and
capping the attempt probabilities. These changes give a bounded
determining radius and pointwise domination by independent
Bernoulli variables.

\begin{samepage}
\begin{theorem}[Local independent-set sampler]\label{thm:sampler}
For every sufficiently large integer $D$, put
\[
 \ell:=\lfloor\ln D\rfloor,\quad
 w:=\frac{2\ell}{D},\quad \eta:=\ell^{-6},\quad\text{and}\quad T:=\ell^2.
\]
There is a finite uniform label alphabet and a radius-$(T+2)$ rule,
depending only on $D$, such that the following hold for every triangle-free graph of maximum degree
at most $D$.
\begin{enumerate}
\item\label{it:sampler-independent} For \emph{every} label assignment, the output $I$ is independent.
\item\label{it:sampler-marginal} Under independent uniform labels, every vertex $v$ satisfies
\begin{equation}\label{eq:sampler-bound}
 \mathbb P(v\in I)\ge\frac{\ln D-7\ln\ln D-6}{D}.
\end{equation}
\item\label{it:sampler-cap} There are independent Bernoulli variables $K(v)$ of parameter
$\eta$, each determined by the label at $v$, for which
$\mathbf1_{\{v\in I\}}\le K(v)$ for every label assignment.
\end{enumerate}
Each probability on an infinite graph is the probability of an event
in a finite product of labels in a determining neighbourhood.
\end{theorem}
\end{samepage}

The independent cap in Part~(\ref{it:sampler-cap}) is a pointwise coupling with a
product measure. The output indicators themselves need not be
independent. This additional control will be used in the colouring
argument.

The second result concerns the \emph{randomised LOCAL model}.
In this model there is a processor at each vertex of a finite graph.
In one synchronous round, every processor may send messages to each
neighbour, receive its neighbours' messages, perform local computation,
and generate independent private random bits. Message length and
local computation are unrestricted. The cost is the number of
communication rounds, until all vertices output their colours.
The processors have distinct identifiers consisting of $O(\ln n)$
bits. They know $n$, the degree bound, and the requested number of
colours. A radius-$R$ rule can be executed in $O(R)$ rounds.

\begin{theorem}\label{thm:local-one}
For every $\varepsilon\in(0,1)$ there is $\Delta_0$ such that the
following holds. Let $G$ be an $n$-vertex triangle-free graph of maximum
degree $\Delta\ge\Delta_0$, and let
$1\le k\le(1-\varepsilon)\ln\Delta$. There is a randomised LOCAL
algorithm which, with probability at least $1-n^{-1}$, properly colours
$G$ with at most $\lfloor\Delta/k\rfloor$ colours in
\begin{equation}\label{eq:local-one-time}
 O_\varepsilon(k)+\ln^{O(1)}\ln n
\end{equation}
rounds. The exponent in the second term is absolute. 
%The processors have distinct $O(\ln n)$-bit identifiers and are given $n$, $\Delta$, and the desired palette size $\lfloor\Delta/k\rfloor$, as in the usual LOCAL model.
\end{theorem}
%Note that Theorem~\ref{thm:local-one} attains Molloy's leading coefficient $1$, with the stated distributed running time.

The earlier distributed work of Pettie and Su \cite[Theorem~1]{PettieSu15} and Chung, Pettie and Su
\cite[Theorem~9]{ChungPettieSu17} was developed further by
Davies-Peck and Zhang \cite[Theorem~1]{DaviesPeckZhang26}. The latter result, like Theorem~\ref{thm:local-one}, constructs a $(\Delta/k)$-colouring
using $O_\varepsilon(k)+\ln^{O(1)}\ln n$ rounds; however, their range of $k$ is bounded above by $(1/4-\varepsilon)\ln\Delta$.
Davies-Peck and Zhang \cite[Section~6.3]{DaviesPeckZhang26} asked if $1/4$ can be increased to $1$ here; thus Theorem~\ref{thm:local-one} answers this question.

Theorem~\ref{thm:local-one} also has consequences for definable colourings of
infinite graphs. A graph is \emph{Borel} if its vertex set is a
standard Borel space and its adjacency relation is Borel. We write
$\chi_B(G)$ for its Borel chromatic number, $\chi_B^f(G)$ for its
fractional Borel chromatic number, and $\chi_\mu(G)$ for its
chromatic number with colour classes measurable with respect to a
Borel probability measure $\mu$. Given a Polish topology compatible
with the Borel structure, we also consider \emph{Baire-measurable}
colourings, whose colour classes have the Baire property.
The asymptotic separation index $\operatorname{asi}(G)$ measures
whether, at each finite distance scale, the vertices can be
partitioned into a fixed finite number of Borel sets with finite
components. Precise definitions are given in Section~\ref{sec:borel}.

\begin{theorem}\label{thm:borel-measurable}
For every $\delta>0$ there is $D_0$ such that the following holds for
every integer $D\ge D_0$. Put
\begin{equation}\label{eq:borel-palette}
 q:=\left\lfloor(1+\delta)\frac{D}{\ln D}\right\rfloor.
\end{equation}
If $G$ is a triangle-free Borel graph of maximum degree at most $D$,
then
\begin{enumerate}
\item\label{it:borel-fractional} $\chi_B^f(G)\le q$;
\item\label{it:borel-measurable} $\chi_\mu(G)\le q$ for every Borel probability measure $\mu$;
\item\label{it:borel-finite-asi} $\chi_B(G)\le q$ if $\operatorname{asi}(G)<\infty$;
\item\label{it:borel-baire} for every Polish topology compatible with the Borel structure
of $V(G)$, the graph $G$ has a Baire-measurable proper $q$-colouring.
\end{enumerate}
The threshold $D_0$ depends only on $\delta$; in particular it is
independent of $G$, $\mu$, the chosen topology and the finite value
of $\operatorname{asi}(G)$.
\end{theorem}

These bounds all have the form $(1+o(1))D/\ln D$ as $D\to\infty$.
For the fractional Borel chromatic number, the sampler gives the
stronger explicit estimate
\[
 \chi_B^f(G)\le \frac{D}{\ln D-7\ln\ln D-6};
\]
see Corollary~\ref{cor:borel-fractional-explicit}. The measurable
assertion also holds for every $\sigma$-finite Borel measure.
The probability or $\sigma$-finiteness convention is necessary;
Remark~\ref{rem:borel-measure-convention} explains the obstruction
for arbitrary Borel measures.

The measurable and Baire-measurable assertions follow from
Bernshteyn's transfer theorem \cite[Theorem~2.14]{Bernshteyn23},
and the Borel assertion under finite ASI follows from the transfer
theorem of Bernshteyn and Weilacher
\cite[Theorem~1.42]{BernshteynWeilacher25}.
The measurable assertion answers Bernshteyn's
\cite[Open Problem~3.11]{Bernshteyn23}. Bernshteyn and Weilacher \cite[Theorem~1.18]{BernshteynWeilacher25}
proved $\chi_B(G)\le (4+o(1))D/\ln D$  for triangle-free graphs with finite ASI and then asked whether the coefficient $4$
could be replaced by $1$.
Theorem~\ref{thm:borel-measurable}(\ref{it:borel-finite-asi}) answers this question
affirmatively.

Section~\ref{sec:optimality} proves that the leading coefficient $1$
is optimal for the local independent-set marginal, for the number of colours of randomised LOCAL algorithms using $o(\ln n)$ rounds at
fixed degree, and for the fractional Borel and measurable bounds on
arbitrary triangle-free Borel graphs. These conclusions use the
factor-of-i.i.d. obstruction of Rahman--Vir\'ag
\cite{RahmanVirag17} and its Borel formulation due to Bernshteyn
\cite{Bernshteyn22} and in fact show that these bounds cannot be improved even for acyclic graphs. For the finite-ASI and Baire classes, the optimal leading coefficient remains
undetermined; see Section~\ref{sec:optimality}.


Our distributed application uses the Local Lemma of Flin, Ghaffari,
Halld\'orsson, Maus and Nolin
\cite[Theorem~1.1]{FlinGhaffariHalldorssonMausNolin26}, together with fast
degree-plus-one colouring
\cite{ChangLiPettie20,RozhonGhaffari20}.
We use the corrected colouring analysis of Ghaffari, Halld\'orsson,
Maus and Nolin \cite{GhaffariHalldorssonMausNolin26}.
The precise statements are given in Section~\ref{sec:local-one}.
Davies' resilient Local Lemma \cite{Davies23} also suffices here,
with a repair to its shattering argument; see Remark~\ref{rem:davies}.
Further algorithms for avoiding local bad events, and for replacing
random local choices by deterministic ones, are developed in
\cite{MoserTardos10,FischerGhaffari17,GhaffariHarrisKuhn18}.
For each fixed $\Delta$, one can also obtain an $o(\ln n)$ round bound
for Theorem~\ref{thm:local-one}, as needed for the deduction of
Theorem~\ref{thm:borel-measurable}, using the earlier distributed
Local Lemma of Fischer and Ghaffari \cite{FischerGhaffari17}, with
the corrected analysis in \cite{GhaffariHalldorssonMausNolin26}.

\section{Notation and preliminaries}\label{sec:preliminaries}
\label{sec:prob-background}
All graphs are simple and undirected. For a graph $G$, write $N_G(v)$
for the neighbourhood of $v$, $B_G(v,R)$ for its ball of radius $R$,
and $G[W]$ for the subgraph induced by $W\subseteq V(G)$. For $v\in V(G)$, 
we denote by $G-v$ the graph obtained by removing the vertex $v$ from $G$.
We may omit
the subscript $G$ when the graph is clear. The \emph{power graph} $G^r$ has the same vertex set $V(G)$ and joins
distinct vertices at distance at most $r$ in $G$.

We write $[q]:=\{1,\ldots,q\}$, $\ln$ for the natural logarithm,
and $\mathbf1_E$ for the indicator of an event $E$. Probability and expectation
are denoted by $\mathbb P$ and $\mathbb E$, respectively.

The parameter $D$ is a degree bound for the sampler; in the colouring
algorithm, $\Delta$ is the initial maximum degree and $D_j$ is the
degree bound at phase $j$. A subscript on $O$ specifies the permitted
dependence of its implicit constant. When we write $\ln^{O(1)}\ln n$, the exponent
is absolute; for small $n$ this notation means
$O((1+\ln\ln(\max\{n,3\}))^c)$ for some absolute $c$.
%Degree thresholds may depend on constants fixed earlier, but not on the graph.

All samplers used below have rational parameters. The exact encoding
in Lemma~\ref{lem:encoding} therefore allows their analysis on finite
probability spaces. We use the usual notation for filtrations,
conditional expectations and martingales. In particular, a process
$(M_i)$ adapted to $(\mathcal F_i)$ is a supermartingale if
$\mathbb E[M_{i+1}\mid\mathcal F_i]\le M_i$. We use the tower
property and the fact that a factor measurable with respect to the
conditioning sigma-algebra can be taken outside a conditional
expectation. We will also use the elementary inequality
\begin{equation}\label{eq:cap-jensen}
 \mathbb E[\min\{X,\eta\}\mid\mathcal F]
 \le\min\{\mathbb E[X\mid\mathcal F],\eta\}
 \quad(X\ge0),
\end{equation}
which follows by bounding the conditional expectation separately
by $\mathbb E[X\mid\mathcal F]$ and by $\eta$.
%The stopping argument needed for the sampler is proved below.

\section{The capped bucket process}\label{sec:bucket}
\subsection{Definition of the process}
Fix a positive integer $T$, a degree bound $D$, and parameters
$0<w<\eta<1$. Initially the parameters may be real; rationality will
be imposed when a finite uniform alphabet is required. On a finite
triangle-free graph $G$, independently at each vertex $u$, choose a
bucket $b(u)$ uniformly from $[T]$ and an independent uniform random
variable $U(u)$ on $[0,1]$.
These continuous variables are only a convenient description of threshold
trials. For rational parameters Lemma~\ref{lem:encoding} replaces them
exactly by finite uniform coordinates, which can be used throughout
all subsequent probability calculations.
A vertex is \emph{pending after Stage $i$}
if $b(u)>i$. Set $W_0(u):=w$ at every vertex.

At \emph{Stage $i$}, for $i=1,\dots,T$, every vertex $u$ in bucket $i$ makes an
\emph{attempt} if
\[
 U(u)<p_{i-1}(u),\quad\text{where}\quad
 p_{i-1}(u):=\min\{W_{i-1}(u),\eta\}.
\]
All these decisions use the weights from before the stage. In
particular, vertices in the same bucket $i$ do not change one another's
attempt probabilities during Stage~$i$. Conditional on all buckets
and on earlier trials, the current trials are independent Bernoulli
trials with the displayed parameters. Write $a(u)$ for the indicator
that $u$ attempts at Stage $b(u)$. Update the weight of each vertex $z$
that remains pending by
\begin{equation}\label{eq:update}
 W_i(z):=W_{i-1}(z)
 \prod_{\substack{u\in N(z)\\b(u)=i}}
 \frac{1-a(u)}{1-p_{i-1}(u)}.
\end{equation}
Weights of vertices already processed are frozen; they will not be
used for further attempts. The denominator in every factor is
positive because $p_{i-1}(u)\le\eta<1$.

For a vertex $z$ pending after Stage $i$, iterating the update gives
\begin{equation}\label{eq:iterated-pending-update}
 W_i(z)=w\prod_{\substack{u\in N_G(z)\\b(u)\le i}}
       \frac{1-a(u)}{1-p_{b(u)-1}(u)}.
\end{equation}
The factor associated with $u$ occurs once, at Stage $b(u)$.
Multiplication of the successive stage products therefore gives exactly
the displayed product. If a numerator is zero, the product is zero;
otherwise all numerators are one. A neighbour in a future bucket has
not yet contributed a factor.

Let $\mathcal A:=\{u:a(u)=1\}$ be the set of all attempts, and output
\begin{equation}\label{eq:output}
 I:=\{u\in\mathcal A:
       \text{there is no }z\in N(u)\cap\mathcal A
                     \text{ with }b(z)=b(u)\}.
\end{equation}
Thus both ends of an edge with simultaneous attempts are removed
from the output. An attempt that is removed from the output
\emph{still} contributed its factor zero in~\eqref{eq:update} to
later neighbours. Forgetting this distinction would define a
different process, for which the proof below does not apply.

\begin{lemma}[Independence, locality, and exact encoding]\label{lem:encoding}
The set $I$ is independent for every label assignment. Its membership
rule has determining radius at most $T+2$. Throughout the process,
\begin{equation}\label{eq:weight-bound}
 0\le W_i(u)\le w(1-\eta)^{-D}.
\end{equation}
If $w$ and $\eta$ are rational, the process has an exact finite uniform
label encoding. In that encoding there are independent Bernoulli
variables $K(u)$ of parameter $\eta$ such that
\begin{equation}\label{eq:cap}
 \mathbf1_{\{u\in I\}}\le a(u)\le K(u)
 \quad\text{for every assignment of labels}.
\end{equation}
\end{lemma}
\begin{proof}
If $uz$ is an edge with $b(u)<b(z)$ and $u$ attempts, then
\eqref{eq:update} sets the pending weight of $z$ to zero. This weight
remains zero, so $z$ cannot attempt. If $b(u)=b(z)$ and both vertices
attempt, \eqref{eq:output} removes both. Thus $I$ is independent.

The state at a vertex after Stage $i$ is determined by its label and
the states and labels of its neighbours before that stage. Induction
therefore bounds its determining radius by $i$. The final deletion
step inspects neighbouring attempt decisions, so radius $T+1$
suffices. In particular, the answer at $v$ is unchanged if the process
is run on $G[B_G(v,T+2)]$. This also justifies the rule on infinite
graphs. Each neighbour contributes to a pending weight at most once,
and every nonzero multiplier is at most $(1-\eta)^{-1}$, proving
\eqref{eq:weight-bound}.

For rational $w,\eta$, define finite sets of nonnegative rational
numbers by
\begin{align*}
 F_0&:=\{0,w\},\\
 F_{i+1}&:=F_i\cup\{0\}\cup
 \left\{x\prod_{r=1}^{k}\frac1{1-\min\{y_r,\eta\}}:
       x,y_1,\ldots,y_k\in F_i,\ 0\le k\le D\right\}.
\end{align*}
All denominators are positive. Induction using~\eqref{eq:update}
shows that every weight after Stage $i$ belongs to $F_i$; the terms
$F_i$ and $0$ account for frozen and extinguished weights. Thus the
possible attempt probabilities belong to the finite rational set
\[
 P:=\{\min\{x,\eta\}:x\in F_0\cup\cdots\cup F_T\},
\]
which depends only on $D,T,w,\eta$.
Choose an integer $N$ divisible by the denominators of the elements
of $P\cup\{\eta\}$. Independently at each vertex, choose
$J(u)$ uniformly from $[N]$ and replace the threshold trial by
$J(u)\le Np_{b(u)-1}(u)$. Since $J(u)$ is first consulted in
$u$'s bucket, this trial has exactly the prescribed conditional
probability. Hence the uniform label $(b(u),J(u))\in[T]\times[N]$
gives the same law as the original process.
Finally, $K(u):=\mathbf1_{\{J(u)\le N\eta\}}$ are independent
Bernoulli variables of parameter $\eta$, and every attempt satisfies
$a(u)\le K(u)$. Together with $I\subseteq\mathcal A$, this proves
\eqref{eq:cap}.
\end{proof}

The bounds above also explain precisely how the rule is interpreted
on an infinite graph. The output at one vertex can be defined from
a finite labelled ball. Definitions made from larger balls agree by
locality, and independence is checked edge by edge by the same
deterministic argument. The probability of membership at a root is therefore computed from
only finitely many independent labels.

\subsection{The cost of simultaneous attempts}
\begin{lemma}[Collision loss]\label{lem:collision}
For every vertex $v$ of a triangle-free graph of maximum degree at
most $D$,
\begin{equation}\label{eq:collision-loss}
 \mathbb P(v\in I)\ge
 \mathbb P(v\in\mathcal A)-\frac{Dw^2}{T}.
\end{equation}
\end{lemma}
\begin{proof}
Work first on a finite graph and condition on all buckets.
Let $\mathcal H_i$ record these buckets and the trial coordinates
through Stage $i$. Every multiplier in~\eqref{eq:update} has
conditional mean one, since
\[
 \mathbb E\left[\frac{1-a(u)}{1-p_{i-1}(u)}
                    \,\middle|\,\mathcal H_{i-1}\right]=1
 \quad\text{if }b(u)=i.
\]
Multipliers belonging to distinct current vertices are conditionally
independent.

Consider an edge $uv$ with $b(u)=b(v)=j$.
Triangle-freeness gives $N(u)\cap N(v)=\varnothing$. For each
$i<j$, the multipliers updating $u$ and $v$ therefore use disjoint
sets of fresh trial coordinates. Consequently
\[
 \mathbb E[W_i(u)W_i(v)\mid\mathcal H_{i-1}]
       =W_{i-1}(u)W_{i-1}(v).
\]
Iterating from $W_0(u)W_0(v)=w^2$ gives
\[
 \mathbb E[W_{j-1}(u)W_{j-1}(v)\mid\text{buckets}]=w^2.
\]
The two trials in Bucket $j$ are independent conditional on
$\mathcal H_{j-1}$, so
\begin{align*}
 \mathbb P(u,v\in\mathcal A\mid\text{buckets})
 &=\mathbb E[p_{j-1}(u)p_{j-1}(v)\mid\text{buckets}]\\
 &\le\mathbb E[W_{j-1}(u)W_{j-1}(v)\mid\text{buckets}]=w^2.
\end{align*}
Here the weights themselves need not be independent.
Since two independent uniform buckets coincide with probability
$1/T$, averaging gives
\[
 \mathbb P(u,v\in\mathcal A,\ b(u)=b(v))\le w^2/T.
\]
An attempted vertex $v$ is deleted only if this event occurs for one
of its at most $D$ neighbours. The union bound proves
\eqref{eq:collision-loss}. Locality extends the conclusion to
infinite graphs.
\end{proof}

\section{The marginal estimate}\label{sec:sharp}
\subsection{A forced-decline law and its likelihood factor}
Fix a root $v$ in a finite triangle-free graph, and write
$S:=N(v)$ and $n:=|S|\le D$. The set $S$ is independent: an edge inside
$S$, together with $v$, would be a triangle. Define another experiment
on $G-v$, with the same independent bucket distribution. Every vertex
in $S$ is \emph{forced to decline} when its bucket is processed,
regardless of its own trial coordinate. It still applies the usual
decline multiplier to its later neighbours. All vertices
outside $S$ make honest trials with the probabilities computed from
this modified history. Denote this law by $\mathbb Q$, its weights by
$\widetilde W_i(u)$, and its capped weights by
\[
 \widetilde p_i(u):=\min\{\widetilde W_i(u),\eta\}.
\]
The tilde is essential: these probabilities are computed in the
forced experiment and need not equal the probabilities in an
unrelated realisation of the original experiment. They do agree
on matched histories in the comparison below. An additional bucket
$b(v)$ is sampled independently of the entire forced experiment.

Recall that every vertex starts
with weight $w$. At a forced vertex $u\in S$, the number
$\widetilde p_{b(u)-1}(u)$ is still used in the denominator of the update
at later neighbours, but the attempt indicator is assigned zero.
Thus the transmitted multiplier is $1/(1-\widetilde p_{b(u)-1}(u))$.
An \emph{honest trial} means a decision using its stated probability
and its own previously unused trial coordinate. The bound
\eqref{eq:weight-bound} remains valid in the forced experiment:
each numerator is zero or one and each denominator is at least $1-\eta$.
Define
\begin{equation}\label{eq:X-L}
 X_i:=\sum_{\substack{u\in S\\b(u)\le i}}
       -\ln\bigl(1-\widetilde p_{b(u)-1}(u)\bigr),
 \quad 0\le i\le T.
\end{equation}
In particular $X_0=0$, and $X_i$ is nondecreasing.

\begin{lemma}[Change of measure]\label{lem:likelihood}
The attempt probability in the original experiment satisfies
\begin{equation}\label{eq:likelihood}
 \mathbb P(v\in\mathcal A)=
 \frac1T\sum_{i=0}^{T-1}
 \mathbb E_{\mathbb Q}\min\{w,\eta \mathrm{e}^{-X_i}\}.
\end{equation}
\end{lemma}
\begin{proof}
Condition on $b(v)=i+1$ and on the buckets of all other vertices.
Before Stage $i+1$, the vertex $v$ makes no trial or update, so
deleting it has no effect. Likewise, forcing a decline in a bucket
after $i$ has no effect on the history through Stage $i$.

Consider a history $h$ of attempt outcomes through Stage $i$ in which
every processed vertex of $S$ declines. We compare these outcome
histories, without including the unused raw coordinates at forced
vertices. On matching histories, the weights and all honest trial
probabilities agree. A forced decline at $u$ has probability one
under $\mathbb Q$ and probability
$1-\widetilde p_{b(u)-1}(u)$ under the original law. Therefore
\[
 \mathbb P(h\mid\text{buckets},b(v)=i+1)
 =\mathbb Q(h\mid\text{buckets})
   \prod_{\substack{u\in S\\b(u)\le i}}
       (1-\widetilde p_{b(u)-1}(u))
 =\mathbb Q(h\mid\text{buckets})\mathrm{e}^{-X_i(h)}.
\]
All factors are positive because $\widetilde p\le\eta<1$.
On this history, \eqref{eq:iterated-pending-update} gives
$W_i(v)=w\mathrm{e}^{X_i(h)}$. Multiplying the conditional attempt
probability by the likelihood factor yields
\[
 \mathrm{e}^{-X_i(h)}\min\{w\mathrm{e}^{X_i(h)},\eta\}
       =\min\{w,\eta \mathrm{e}^{-X_i(h)}\}.
\]
Every other original history contains an earlier neighbouring
attempt and has $W_i(v)=0$, so contributes nothing. Summing over
histories and averaging over the buckets of $G-v$ proves the
corresponding term of~\eqref{eq:likelihood}. Finally average over
the independent uniform choice of $b(v)$.
\end{proof}

\subsection{Deferred bucket exposure and normalised pending mass}
Until the end of the marginal proof, expectations are under
$\mathbb Q$ unless another law is specified. Instead of revealing all
buckets initially, reveal the first $i$ bucket classes and the trial
coordinates of the vertices in those classes. Let $\mathcal F_i$
be the sigma-algebra generated by this information. Coordinates at
forced vertices may be exposed too; the process does not consult
them. All weights right after Stage $i$ are $\mathcal F_i$-measurable.

Conditional on $\mathcal F_i$, the buckets of the pending vertices
are independent and uniform on $\{i+1,\ldots,T\}$, and their trial
coordinates remain independent and unused. 

For $i<T$ define the intermediate sigma-algebra
\begin{equation}\label{eq:intermediate-filtration}
 \mathcal G_{i+1}:=
 \mathcal F_i\vee
 \sigma\bigl(\mathbf1_{\{b(x)=i+1\}}:x\in V(G-v)\bigr).
\end{equation}
Thus $\mathcal G_{i+1}$ reveals the next bucket, but not its trial
coordinates, and
$\mathcal F_i\subseteq\mathcal G_{i+1}\subseteq\mathcal F_{i+1}$.

Let
\begin{equation}\label{eq:pending-mass-def}
 S_i:=\{u\in S:b(u)>i\},\quad
 B_i:=\sum_{u\in S_i}\widetilde p_i(u),\quad\text{and}\quad
 M_i:=\frac{B_i}{1-i/T}\quad(0\le i<T),
\end{equation}
and set $B_T:=0$ and $M_T:=0$. The denominator normalises for the expected
fraction $1-i/T$ of buckets still unprocessed.

\begin{lemma}[Capped pending mass and its noise]\label{lem:mass}
The process $(M_i)_{i=0}^T$ is a nonnegative supermartingale with
$M_0=nw$. Define
\begin{equation}\label{eq:Y-A-Z}
 Y_i:=\sum_{\substack{u\in S\\b(u)\le i}}
          \widetilde p_{b(u)-1}(u),\quad
 A_i:=\frac1T\sum_{r=0}^{i-1}M_r,\quad\text{and}\quad Z_i:=Y_i-A_i.
\end{equation}
Then $(Z_i)$ is a martingale with $Z_0=0$, and
\begin{align}
 \mathbb E_{\mathbb Q}Z_T^2&\le\eta nw\le\eta Dw,
                                                  \label{eq:noise-l2}\\
 \mathbb Q\left(\max_{0\le i\le T}|Z_i|>1\right)
     &\le\eta Dw,                 \label{eq:noise-max}\\
 X_i&\le\frac{Y_i}{1-\eta}.                       \label{eq:log-linear}
\end{align}
\end{lemma}
\begin{proof}
Fix $i<T$ and put $q_i:=1/(T-i)$.
Conditional on $\mathcal G_{i+1}$, consider a vertex $u\in S_i$
with $b(u)>i+1$. Since $S$ is independent, every current neighbour
of $u$ makes an honest trial. Their update multipliers are
conditionally independent and have mean one, whence
\[
 \mathbb E[\widetilde W_{i+1}(u)\mid\mathcal G_{i+1}]
       =\widetilde W_i(u).
\]
Applying~\eqref{eq:cap-jensen}, multiplying by the
$\mathcal G_{i+1}$-measurable indicator of $b(u)>i+1$, and summing,
we obtain
\begin{align*}
 \mathbb E[B_{i+1}\mid\mathcal F_i]
 \le\mathbb E\left[
       \sum_{u\in S_i}\widetilde p_i(u)
            \mathbf1_{\{b(u)>i+1\}}\,\middle|\,\mathcal F_i\right]=(1-q_i)B_i.
\end{align*}
For $i<T-1$, division by $1-(i+1)/T$ gives
$\mathbb E[M_{i+1}\mid\mathcal F_i]\le M_i$.
The last step follows from $M_T=0$. Thus $(M_i)$ is a nonnegative
supermartingale; it is bounded by $Tn\eta$, and $M_0=nw$.

Write $\Delta Y_{i+1}:=Y_{i+1}-Y_i$, and similarly for $Z$.
Conditional on $\mathcal F_i$, the indicators
$C_u:=\mathbf1_{\{b(u)=i+1\}}$, $u\in S_i$, are independent
Bernoulli variables of parameter $q_i$. Hence
\[
 \Delta Y_{i+1}=\sum_{u\in S_i}\widetilde p_i(u)C_u,
 \quad\text{and}\quad
 \mathbb E[\Delta Y_{i+1}\mid\mathcal F_i]
       =q_iB_i=M_i/T=A_{i+1}-A_i.
\]
This proves that $(Z_i)$ is a martingale. Conditional independence
and $\widetilde p_i(u)^2\le\eta\widetilde p_i(u)$ also give
\begin{align*}
 \mathbb E[(\Delta Z_{i+1})^2\mid\mathcal F_i]
 =q_i(1-q_i)\sum_{u\in S_i}\widetilde p_i(u)^2\le\eta q_iB_i=\eta M_i/T.
\end{align*}
Distinct martingale differences have zero expected product.
Consequently
\[
 \mathbb E Z_T^2
 =\sum_{i=0}^{T-1}\mathbb E(\Delta Z_{i+1})^2
 \le\frac\eta T\sum_{i=0}^{T-1}\mathbb E M_i
 \le\eta nw,
\]
which proves~\eqref{eq:noise-l2}.

Let $\sigma$ be the first $i$ with
$|Z_i|>1$, or $T$ if there is none.
Since $(Z_i^2)$ is a submartingale and
$\{\sigma\le i\}\in\mathcal F_i$,
\[
 \mathbb E(Z_T^2-Z_\sigma^2)
 =\sum_{i=0}^{T-1}
   \mathbb E\bigl[\mathbf1_{\{\sigma\le i\}}
                    (Z_{i+1}^2-Z_i^2)\bigr]\ge0.
\]
On the event $\max_i|Z_i|>1$, including a first crossing at $T$,
we have $Z_\sigma^2>1$. Thus
\[
 \mathbb Q(\max_i|Z_i|>1)
 \le\mathbb E Z_\sigma^2\le\mathbb E Z_T^2\le\eta Dw,
\]
proving~\eqref{eq:noise-max}.
Finally,
\[
 -\ln(1-p)=\int_0^p\frac{ds}{1-s}\le\frac p{1-\eta}
 \quad(0\le p\le\eta),
\]
and summing this inequality gives~\eqref{eq:log-linear}.
\end{proof}

\subsection{The time-budget inequality}
The next lemma gives a lower bound on the expected value of the time $\tau$ needed to spend a
fixed budget at a nonnegative supermartingale rate. We include a
self-contained proof, with the convention $\tau:=1$ if the budget is not exhausted.

\begin{lemma}[Time budget]\label{lem:budget}
Let $\mathcal F_0\subseteq\cdots\subseteq\mathcal F_T$ be a
filtration on a finite probability space, and let $(M_i)_{i=0}^T$
be a nonnegative supermartingale with respect to this filtration.
Thus $M_i$ is $\mathcal F_i$-measurable and
\begin{equation}\label{eq:budget-supermartingale}
 \mathbb E[M_{i+1}\mid\mathcal F_i]\le M_i
 \quad(0\le i<T).
\end{equation}
Suppose that $a,b>0$,
$\mathbb EM_0\le b$, and $b\ge2a$. Put
\begin{equation}\label{eq:budget-interpolation}
 t_i:=i/T,\quad A_i:=\frac1T\sum_{j=0}^{i-1}M_j,\quad\text{and}\quad
 A(t):=A_i+(t-t_i)M_i\quad(t_i\le t\le t_{i+1}).
\end{equation}
Define $\tau$ to be the first time that $A(t)$ reaches $a$, or
$1$ if it does not reach $a$ by time $1$. Then
\begin{equation}\label{eq:budget-consequence}
 \frac1T\sum_{i=0}^{T-1}\mathbb P(A_i<a)
 \ge\mathbb E\tau\ge\frac ab.
\end{equation}
\end{lemma}
\begin{proof}
Since $M_i\ge0$, the function $A$ is continuous and nondecreasing.
Set
\[
 r_i:=\max\{a-A_i,0\},\quad\text{and}\quad
 S:=\sum_{i=0}^{T-1}M_i(r_i-r_{i+1}).
\]
Then $0\le r_{i+1}\le r_i\le a$ and $r_0=a$.
Moreover, $r_{i+1}$ is $\mathcal F_i$-measurable, because
$A_{i+1}=T^{-1}\sum_{j=0}^{i}M_j$. It follows that
\begin{equation}\label{eq:budget-transform}
 \mathbb E[r_{i+1}(M_{i+1}-M_i)\mid\mathcal F_i]
 =r_{i+1}\bigl(\mathbb E[M_{i+1}\mid\mathcal F_i]-M_i\bigr)
 \le0.
\end{equation}
This is the predictable-transform calculation of
\cite[Theorem~4.2.8]{Durrett19}.
Discrete integration by parts gives
\[
 S+r_TM_T
 =aM_0+\sum_{i=0}^{T-1}r_{i+1}(M_{i+1}-M_i).
\]
Taking expectations, using~\eqref{eq:budget-transform} and
$r_TM_T\ge0$, yields
\begin{equation}\label{eq:budget-energy}
 \mathbb ES\le a\mathbb EM_0\le ab.
\end{equation}

Write $M(t):=M_i$ on $[t_i,t_{i+1})$, and put
$\lambda_i:=\min\{\tau,t_{i+1}\}-\min\{\tau,t_i\}$.
The amount spent in this interval before stopping is
$r_i-r_{i+1}=M_i\lambda_i$, also when $M_i=0$.
Therefore
\begin{equation}\label{eq:budget-energy-integral}
 S=\sum_{i=0}^{T-1}M_i^2\lambda_i=\int_0^\tau M(t)^2\,dt.
\end{equation}
Let $C:=\{A_T\ge a\}$.
We have $\tau>0$, and on $C$ the Cauchy--Schwarz inequality gives
\[
 a^2=\left(\int_0^\tau M(t)\,dt\right)^2
       \le\tau\int_0^\tau M(t)^2\,dt=\tau S.
\]
Outside $C$ we still have $S\ge0$. Hence
$a^2\mathbf1_C/\tau\le S$, and~\eqref{eq:budget-energy} implies
\begin{equation}\label{eq:budget-inverse-hit}
 \mathbb E[\mathbf1_C/\tau]\le b/a.
\end{equation}

Put $s:=a/b\le1/2$. Pointwise,
\[
 \tau\ge2s-\frac{s^2}{\tau}\mathbf1_C:
\]
on $C$ the difference equals $(\tau-s)^2/\tau$, while outside
$C$ we have $\tau=1\ge2s$. Taking expectations and
using~\eqref{eq:budget-inverse-hit} gives
$\mathbb E\tau\ge2s-s^2b/a=a/b$.
Finally, if $K$ is the first index with $A_K\ge a$, then exactly
$K$ of $A_0,\ldots,A_{T-1}$ are below $a$ and $\tau\le K/T$.
If there is no such index, all $T$ are below $a$ and $\tau=1$.
Thus $\tau\le T^{-1}\sum_{i<T}\mathbf1_{\{A_i<a\}}$,
which proves~\eqref{eq:budget-consequence} after taking expectations.
\end{proof}

\begin{remark}\label{rem:budget-sharpness}
The bound $\mathbb E\tau\ge a/b$ in Lemma~\ref{lem:budget} is sharp:
take $M_i=b$ deterministically, so that $\tau=a/b$.
\end{remark}


\subsection{Combining the likelihood, budget, and collision bounds}
\begin{proposition}[Quantitative marginal]\label{prop:marginal}
Suppose that $D,T$ are positive integers and $0<w<\eta<1$ are
rational. If $a>0$ satisfies
\begin{equation}\label{eq:local-budget-hyp}
 a\le(1-\eta)\ln(\eta/w)-1,\quad\text{and}\quad Dw\ge2a,
\end{equation}
then the output of the bucket process satisfies, at every vertex $v\in V(G)$,
\begin{equation}\label{eq:quantitative-marginal}
 \mathbb P(v\in I)
 \ge\frac aD-\eta Dw^2-\frac{Dw^2}{T}.
\end{equation}
\end{proposition}
\begin{proof}
Let $E:=\{\max_{0\le i\le T}|Z_i|>1\}$.
Outside $E$, whenever $A_i<a$,
\[
 Y_i=A_i+Z_i<a+1\le(1-\eta)\ln(\eta/w).
\]
Thus $X_i<\ln(\eta/w)$ by~\eqref{eq:log-linear}, so the minimum
in~\eqref{eq:likelihood} equals $w$. It follows that
\begin{align*}
 \mathbb P(v\in\mathcal A)
 \ge\frac wT\sum_{i=0}^{T-1}
          \mathbb Q(E^c\cap\{A_i<a\})
 \ge w\left(\frac1T\sum_{i=0}^{T-1}\mathbb Q(A_i<a)
                    -\mathbb Q(E)\right).
\end{align*}
Lemma~\ref{lem:budget} applies with $b:=Dw$, since $M_0=nw\le Dw$
and $Dw\ge2a$. Therefore
\begin{equation}\label{eq:marginal-error-event}
 \mathbb P(v\in\mathcal A)\ge\frac aD-w\mathbb Q(E)
                 \ge\frac aD-\eta Dw^2,
\end{equation}
where the last inequality uses~\eqref{eq:noise-max}.
Subtracting the collision loss from Lemma~\ref{lem:collision}
proves~\eqref{eq:quantitative-marginal}.
Locality extends the estimate from finite graphs to arbitrary
graphs of the specified maximum degree.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:sampler}]
Put $\ell:=\lfloor\ln D\rfloor$, $w:=2\ell/D$,
$\eta:=\ell^{-6}$ and $T:=\ell^2$.
For sufficiently large $D$ we have $\ell\ge2$ and $2\ell^7<D$,
so $0<w<\eta<1$. All parameters required for the exact encoding
are rational. Set
\[
 a:=(1-\ell^{-6})(\ln D-7\ln\ell-\ln2)-1
    =(1-\eta)\ln(\eta/w)-1.
\]
Then $a>0$ for sufficiently large $D$. Since $\ln D<\ell+1$,
we also have
\[
 a\le\ln D-7\ln\ell-\ln2-1<\ell.
\]
Thus $Dw=2\ell\ge2a$, and Proposition~\ref{prop:marginal} applies.
The two error terms satisfy
\[
 \eta D^2w^2=4\ell^{-4},\quad\text{and}\quad D^2w^2/T=4.
\]
Consequently
\begin{align*}
 D\mathbb P(v\in I)
 &\ge (1-\ell^{-6})(\ln D-7\ln\ell-\ln2)-1-4\ell^{-4}-4\\
 &=\ln D-7\ln\ell-\ln2-5
       -\ell^{-6}(\ln D-7\ln\ell-\ln2)-4\ell^{-4}.
\end{align*}
Since $0<\ln D-7\ln\ell-\ln2<\ell+1$, the last two loss terms
are at most
\[
 \ell^{-5}+\ell^{-6}+4\ell^{-4}\longrightarrow0.
\]
For sufficiently large $D$ this sum is at most $1-\ln2$.
Using also $\ln\ell\le\ln\ln D$, we obtain
\[
 D\mathbb P(v\in I)\ge\ln D-7\ln\ell-6
                         \ge\ln D-7\ln\ln D-6.
\]
The remaining assertions follow from Lemma~\ref{lem:encoding}.
\end{proof}

\section{Concentration for uncovered neighbours}\label{sec:concentration}

We will also need the following concentration result that follows
from Boucheron, Lugosi and Massart~\cite[Theorem~1]{BoucheronLugosiMassart09}.
For completeness, we include a self-contained proof using the exposure martingale.

\begin{lemma}[Uncovered-set tail]\label{lem:union}
Let $B>0$ and let $S_1,\ldots,S_m$ be independent random subsets of a finite set
$V_0$ of size $n$, and suppose that $|S_j|\le B$ almost surely for
every $j\in[m]$. Put
\[
 U:=\left|V_0\setminus (\cup_{j=1}^{m}S_j)\right|,
 \quad\text{and}\quad q:=n-\mathbb EU=\mathbb E\left|\cup_{j=1}^{m}S_j\right|.
\]
If $q=0$, then $U=n$ almost surely. If $q>0$, then, for every $t>0$,
\begin{equation}\label{eq:union-tail}
 \mathbb P(U-\mathbb EU\ge t)
 \le\exp\left(-\frac{t^2}{2Bq}\right)
 \le\exp\left(-\frac{t^2}{2Bn}\right).
\end{equation}
\end{lemma}
\begin{proof}
If $q=0$, the nonnegative random variable $n-U$ has expectation
zero and hence vanishes almost surely. Suppose that $q>0$.
For $u\in V_0$, write
\begin{equation}\label{eq:coverage-probabilities}
 p_j(u):=\mathbb P(u\in S_j)\quad(j\in[m]),\quad\text{and}\quad
 r_j(u):=\prod_{k=j+1}^{m}(1-p_k(u))
 \quad(0\le j\le m).
\end{equation}
Thus $r_j(u)$ is the probability that all sets after the $j$th miss
$u$, with $r_m(u)=1$. Expose the sets in order and put
$\mathcal F_j:=\sigma(S_1,\ldots,S_j)$. Independence between the
sets gives the conditional expectation martingale
\begin{equation}\label{eq:coverage-martingale}
 H_j:=\mathbb E[U\mid\mathcal F_j]
 =\sum_{u\in V_0\setminus(\cup_{k=1}^{j}S_k)}r_j(u),\quad j\in\{0,\ldots,m\}.
\end{equation}
 In particular, $H_0=\mathbb EU$ and $H_m=U$.
 

For $j\in[m]$, define
\begin{equation}\label{eq:coverage-new-contribution}
 C_j:=\sum_{u\in V_0\setminus(\cup_{k=1}^{j-1}S_k)}
             r_j(u)\mathbf1_{\{u\in S_j\}},
 \quad\text{and}\quad \mu_j:=\mathbb E[C_j\mid\mathcal F_{j-1}].
\end{equation}
Since $0\le r_j(u)\le1$, we have $0\le C_j\le|S_j|\le B$.
Using~\eqref{eq:coverage-martingale} and the identity
$r_{j-1}(u)=(1-p_j(u))r_j(u)$ gives
\begin{equation}\label{eq:coverage-increment}
 H_j-H_{j-1}=\mu_j-C_j,\quad\text{and}\quad
 \mu_j=\sum_{u\in V_0\setminus(\cup_{k=1}^{j-1}S_k)}p_j(u)r_j(u)
       \le\sum_{u\in V_0}p_j(u)r_j(u).
\end{equation}
The last bound is deterministic. Its sum telescopes:
\begin{equation}\label{eq:coverage-budget}
 \sum_{j=1}^{m}\sum_{u\in V_0}p_j(u)r_j(u)
 =\sum_{u\in V_0}\sum_{j=1}^{m}
                       \bigl(r_j(u)-r_{j-1}(u)\bigr)
 =\sum_{u\in V_0}(1-r_0(u))=q.
\end{equation}
The final equality holds because $r_0(u)$ is the probability that
$u$ remains uncovered.

Fix $\lambda>0$. Convexity gives the chord bound
\[
 \mathrm{e}^{-\lambda x}\le1+\frac{x}{B}(\mathrm{e}^{-\lambda B}-1)
 \quad(0\le x\le B).
\]
Also, for $y\ge0$,
\[
 \mathrm{e}^{-y}-1+y=\int_0^y(1-\mathrm{e}^{-s})\,ds\le\frac{y^2}{2}.
\]
Applying these inequalities to $C_j$, and using $1+x\le \mathrm{e}^x$,
we obtain
\begin{align}
 \mathbb E[\mathrm{e}^{\lambda(H_j-H_{j-1})}\mid\mathcal F_{j-1}]
 &=\mathrm{e}^{\lambda\mu_j}
       \mathbb E[\mathrm{e}^{-\lambda C_j}\mid\mathcal F_{j-1}]
       \notag\\
 &\le \mathrm{e}^{\lambda\mu_j}
          \left(1+\frac{\mu_j}{B}(\mathrm{e}^{-\lambda B}-1)\right)
       \notag\\
 &\le\exp\left(\frac{\mu_j}{B}
                      (\mathrm{e}^{-\lambda B}-1+\lambda B)\right)
       \notag\\
 &\le\exp\left(\frac{\lambda^2B\mu_j}{2}\right)
 \le\exp\left(\frac{\lambda^2B}{2}
                        \sum_{u\in V_0}p_j(u)r_j(u)\right).
 \label{eq:coverage-conditional-mgf}
\end{align}
The last expression is deterministic. For each $j\in[m]$, the
tower property and the $\mathcal F_{j-1}$-measurability of
$H_{j-1}$ give
\begin{align*}
 \mathbb E[\mathrm{e}^{\lambda(H_j-H_0)}]
 &=\mathbb E\left[\mathrm{e}^{\lambda(H_{j-1}-H_0)}
       \mathbb E[\mathrm{e}^{\lambda(H_j-H_{j-1})}\mid\mathcal F_{j-1}]\right]\\
 &\le\exp\left(\frac{\lambda^2B}{2}
                    \sum_{u\in V_0}p_j(u)r_j(u)\right)
       \mathbb E[\mathrm{e}^{\lambda(H_{j-1}-H_0)}].
\end{align*}
Iterating this inequality for $j=1,\ldots,m$, starting with
$\mathbb E[\mathrm{e}^{\lambda(H_0-H_0)}]=1$, and using
\eqref{eq:coverage-budget}, we obtain
\begin{equation}\label{eq:coverage-mgf}
 \mathbb E[\mathrm{e}^{\lambda(U-\mathbb EU)}]
 \le\exp(\lambda^2Bq/2).
\end{equation}
Markov's inequality with $\lambda:=t/(Bq)$ now gives the first
inequality in~\eqref{eq:union-tail}. The second follows from
$q\le n$. 
\end{proof}

\section{Local constraints}\label{sec:local-one}
We collect the local tools used in the colouring argument: a distributed
Local Lemma, a fast degree-plus-one colouring theorem, and two lemmas
that turn independent sampler runs into a degree reduction.

\subsection{A distributed Local Lemma}\label{sec:local-lll}

Let $\mathcal B$ be a finite indexed family of \emph{bad events},
that is, constraint failures to be avoided simultaneously. They are
determined by a finite set $\mathcal V$ of independent finite-valued
variables. For each $A\in\mathcal B$, specify a \emph{determining set}
$\mathcal V(A)\subseteq\mathcal V$: its coordinates suffice to decide
$A$, but may include variables not consulted by its predicate.
The \emph{dependency graph} has vertex set $\mathcal B$, with two
distinct events adjacent when their determining sets intersect.
We use the following result of Flin, Ghaffari, Halld\'orsson, Maus and
Nolin~\cite[Theorem~1.1]{FlinGhaffariHalldorssonMausNolin26}.

\begin{theorem}[Distributed Local Lemma]\label{ext:local-lll}
Let $N:=|\mathcal B|\ge2$. Suppose that the independent variables
have finite alphabets with given rational probability tables, that
the dependency graph has maximum degree at most an integer $d\ge2$,
and that $\mathbb P(A)\le p$ for every $A\in\mathcal B$. If
\begin{equation}\label{eq:local-lll-criterion}
 pd^{1000}<1,
\end{equation}
then a randomised LOCAL algorithm avoids all bad events with
probability at least $1-N^{-10}$ in
$O((1+\ln\ln(\max\{N,3\}))^c)$ rounds on the dependency graph,
where $c$ is an absolute constant.
Each event processor is given its predicate, determining variables
and their probability tables, and the bounds $N,d,p$.
The processors have distinct identifiers of $O(\ln N)$ bits.
\end{theorem}

\begin{remark}\label{rem:davies}
Davies' resilient Local Lemma~\cite[Theorem 5.1]{Davies23} also suffices for our
application. However, it relies on \cite[Theorem~V.1]{GhaffariHarrisKuhn18} whose
statement was identified in \cite[Section~3.2]{GhaffariHalldorssonMausNolin26} as false.
Although a version of~\cite[Theorem 5.1]{Davies23} that suffices for our purposes can be recovered with some extra work, we will use
Theorem~\ref{ext:local-lll} instead, in order to avoid this auxiliary argument.
\end{remark}

\subsection{Degree-plus-one colouring}\label{sec:local-completion}

\begin{theorem}[Fast degree-plus-one colouring]\label{ext:fast-colouring}
There is an absolute constant $c$ and a randomised LOCAL algorithm
which, on an $N$-vertex graph, $N\ge2$, of maximum degree at most an
integer $D\ge0$, finds a
proper colouring with $D+1$ colours in
$O((1+\ln\ln(\max\{N,3\}))^c)$ rounds, with failure probability at most
$N^{-c_0}$ for some absolute constant $c_0>0$.
The processors have distinct $O(\ln N)$-bit identifiers and know
$N$ and the degree bound $D$.
\end{theorem}
This follows from the Chang--Li--Pettie algorithm~\cite{ChangLiPettie20},
with the corrected shattering
analysis in \cite[Theorem~5]{GhaffariHalldorssonMausNolin26}, and
the deterministic network-decomposition result of Rozho\v{n} and
Ghaffari \cite{RozhonGhaffari20}.

The implicit exponents are absolute. We will use the fast colouring
theorem with failure probability at most $n^{-6}$. This follows from
its stated guarantee by polynomial padding. More generally, for any
fixed $A>0$, choose a positive integer $p$ with $pc_0\ge A$ and,
for $n\ge2$, pad an
$n$-vertex instance to $N:=n^p$ vertices with isolated vertices. Each original processor
simulates $n^{p-1}$ processors, one representing the original vertex
and the rest isolated,
using distinct $O(\ln N)$-bit identifiers $(\operatorname{ID}(v),j)$
and independent randomness at each virtual processor. Thus a virtual
round costs one physical round, and the restricted output fails with
probability at most
\begin{equation}\label{eq:padding-guarantee}
 N^{-c_0}\le n^{-A},\quad\text{and}\quad
 \ln\ln N=\ln\ln n+\ln p.
\end{equation}
The asymptotic round bound is unchanged. The same padding argument
works for Local Lemma instances by adding isolated identically false
events, although Theorem~\ref{ext:local-lll} already supplies
more than the failure probability needed below.

\subsection{Solving local degree constraints}\label{sec:local-constraints}

\begin{lemma}\label{lem:local-constraints}
Let $D\ge2$ be an integer, let $H$ be a finite graph of maximum degree at most $D$, and let
$R$ be a positive integer. Suppose that
$I_1,\ldots,I_m$ are independent runs of a radius-$(R-1)$ rule,
using mutually independent uniform labels $X_{u,j}$ from known finite
alphabets, where $u\in V(H)$ and $j\in[m]$.
Fix $\rho\in(0,1)$ and suppose that, for every $v\in V(H)$,
\begin{equation}\label{eq:local-degree-prob}
 \mathbb P\left(
 \left|N_H(v)\setminus(\cup_{j=1}^m I_j)\right|>\rho D
 \right)\le p,
 \qquad pd^{1000}<1,\quad\text{and}\quad d:=2D^{2R}.
\end{equation}
Then a LOCAL algorithm finds labels for which
\begin{equation}\label{eq:local-full-degree}
 \left|N_H(v)\setminus(\cup_{j=1}^m I_j)\right|\le\rho D
 \quad\hbox{for every }v,
\end{equation}
with failure probability at most $(\max\{n,2\})^{-10}$, in
$O\bigl(R(1+\ln\ln(\max\{n,3\}))^c\bigr)$ rounds
on $H$, where $n:=|V(H)|$ and $c$ is an absolute constant.

If $H$ is the active induced subgraph of an original communication
graph with $\bar n\ge n$ processors, the same conclusion holds with
$n$ replaced by $\bar n$ in both bounds.
\end{lemma}
\begin{proof}
If $|V(H)|\le1$, then every neighbourhood is empty and any labels
satisfy the conclusion. Otherwise, introduce one bad event at each vertex:
\begin{equation}\label{eq:local-full-bad-events}
 A_v:=\left\{
 \left|N_H(v)\setminus(\cup_{j=1}^{m}I_j)\right|>\rho D
 \right\},\quad\text{and}\quad
 \mathcal V(A_v):=\{X_{u,j}:u\in B_H(v,R),\ j\in[m]\}.
\end{equation}
This is a determining set: membership of each neighbour of $v$ in a
run is determined within distance $R$ of $v$.
If two determining sets intersect, their centres have distance at most
$2R$. Hence the number of events meeting any one determining set,
including itself, is at most
\begin{equation}\label{eq:local-dependency}
 \sum_{t=0}^{2R}D^t\le2D^{2R}=d.
\end{equation}
Thus Theorem~\ref{ext:local-lll} applies.

The simulation costs $O(R)$ physical rounds per virtual round.
The physical vertex $v$ simulates its event processor and first gathers
the required radius-$2R$ neighbourhood. Every edge of the dependency
graph joins centres within distance $2R$, so flooding delivers every
virtual message in at most $2R$ physical rounds. All such messages
are sent concurrently; their sizes are unrestricted in LOCAL.
After the solver has chosen consistent values for the labels, one
further execution of the local rule takes $O(R)$ rounds. This gives
the claimed bounds.

For the last assertion, retain one event processor at each inactive
vertex, with an identically false predicate and empty determining set.
These processors are isolated in the dependency graph, even if their
physical hosts have neighbours in the original graph. The solver now
runs on $\bar n$ event processors, so its size parameter and failure
bound refer to $\bar n$. The same simulation gives the round bound.
\end{proof}

\subsection{A degree reduction with a polynomially small cap}
\label{sec:local-concentration}

Here is the concentration estimate in the form required below.
It is convenient to retain a cap chosen from the initial degree, rather
than change it at every phase.


\begin{lemma}\label{lem:local-degree-tail}
Fix $b,C,\tau>0$, $\gamma,\theta\in(0,1)$,
and $\rho\in(0,1)$ such that
\begin{equation}\label{eq:local-rho-hyp}
 \mathrm{e}^{-\gamma C}<\rho.
\end{equation}
There are $c>0$ and $\Delta_0$, depending only on the above fixed constants,
such that the following holds for every $\Delta\ge\Delta_0$.
Suppose that
\[
 1\le k\le\ln\Delta,\quad
 \frac{\tau\Delta}{k}<D\le\Delta,\quad
 1\le h\le bk+1,\quad\text{and}\quad
 \eta:=\frac1{\lceil\Delta^\theta\rceil},
\]
where $D,h$ are integers. Suppose that a sampler on a graph $H$ of
maximum degree at most $D$ has marginal at least $\gamma h/D$ and
pointwise independent cap $\eta$: there are independent variables
$K(u)\sim\operatorname{Bernoulli}(\eta)$, each determined by the
label at $u$, with $\mathbf1_{\{u\in I\}}\le K(u)$ for every label
assignment. Take
\begin{equation}\label{eq:local-number-runs}
 m:=\left\lceil\frac{CD}{h}\right\rceil
\end{equation}
independent runs. Then, for every $v\in V(H)$,
\begin{equation}\label{eq:local-power-tail}
 \mathbb P\left(
 \left|N_H(v)\setminus(\cup_{j=1}^m I_j)\right|>\rho D
 \right)\le\exp(-c\Delta^\theta).
\end{equation}
\end{lemma}
\begin{proof}
The assertion is immediate when $N_H(v)=\varnothing$.
Fix a vertex $v$ with a non-empty neighbourhood. We have
\begin{equation}\label{eq:local-runs-mean}
 m\frac{\gamma h}{D}\ge\gamma C.
\end{equation}
For a run $j$, put
$Z_j:=\sum_{u\in N_H(v)}K_j(u)$ and
$B:=\lceil2D\eta\rceil$, where the $K_j(u)$ are the independent caps.
The caps inside this run are mutually independent. Hence
\[
 \mathbb E[2^{Z_j}]
 =\prod_{u\in N_H(v)}\mathbb E[2^{K_j(u)}]
 =(1+\eta)^{|N_H(v)|}\le \mathrm{e}^{D\eta}.
\]
Put $\xi:=\mathrm{e}^{-D\eta/3}$. Since $B\ge2D\eta$, Markov's
inequality gives
\begin{equation}\label{eq:cap-tail}
 \mathbb P(Z_j>B)\le \mathrm{e}^{D\eta}2^{-B}
 \le \mathrm{e}^{-(2\ln2-1)D\eta}\le \mathrm{e}^{-D\eta/3}=\xi.
\end{equation}
Here we used $2\ln2-1>1/3$.

Set $S_j:=I_j\cap N_H(v)$ if $Z_j\le B$, and $S_j:=\varnothing$
otherwise. These sets are independent between runs and have size at
most $B$. For every $u\in N_H(v)$,
\[
 \mathbb P(u\in S_j)\ge\frac{\gamma h}{D}-\xi.
\]
Define the uncovered counts for the clipped sets and for the actual
sampler outputs by
\begin{equation}\label{eq:local-uncovered-counts}
 U:=\left|N_H(v)\setminus(\cup_{j=1}^m S_j)\right|,
 \quad\text{and}\quad
 U_{\mathrm{actual}}
 :=\left|N_H(v)\setminus(\cup_{j=1}^m I_j)\right|.
\end{equation}
The clipped sets are used only in the analysis; the algorithm retains
the original outputs $I_j$. Since $S_j\subseteq I_j\cap N_H(v)$
for every outcome,
\begin{equation}\label{eq:local-clipping-domination}
 N_H(v)\setminus(\cup_{j=1}^m I_j)
 \subseteq N_H(v)\setminus(\cup_{j=1}^m S_j),
 \quad\text{and}\quad U_{\mathrm{actual}}\le U.
\end{equation}
The error $m\xi=o(1)$ uniformly in the stated range. Indeed,
$m\le C\Delta+1$, since $h\ge1$, while
\[
 D\eta\ge\frac{\tau\Delta^{1-\theta}}{2k}
       \ge\frac{\tau\Delta^{1-\theta}}{2\ln\Delta}.
\]
In particular,
\[
 m\xi\le(C\Delta+1)\exp\left(
             -\frac{\tau\Delta^{1-\theta}}{6\ln\Delta}\right)\longrightarrow0.
\]
The same estimate gives $\Delta\xi\to0$, and hence
$\gamma h/D-\xi\ge\gamma/\Delta-\xi>0$ eventually.

For each neighbour $u$, the events $\{u\notin S_j\}$ are independent
over the runs. Its probability of being missed is therefore
at most $(1-\gamma h/D+\xi)^{m}\le
\exp(-m(\gamma h/D-\xi))$. Summing over at most $D$ neighbours gives
\begin{equation}\label{eq:local-clipped-mean}
 \mathbb E U\le
 D\exp\left(-m\left(\frac{\gamma h}{D}-\xi\right)\right).
\end{equation}
No independence between different neighbours is needed.

Choose a fixed $\rho_0$ with
$\mathrm{e}^{-\gamma C}<\rho_0<\rho$ and put
$\delta:=\rho-\rho_0$. By \eqref{eq:local-runs-mean} and
\eqref{eq:local-clipped-mean}, eventually
$\mathbb EU\le\rho_0D$.

By \eqref{eq:local-clipping-domination}, the degree-failure event
$\{U_{\mathrm{actual}}>\rho D\}$ is contained in $\{U>\rho D\}$.
Also $D\eta\ge1$ eventually, so $B\le3D\eta$.
Lemma~\ref{lem:union}, with ground-set size $|N_H(v)|\le D$ and
$t:=\delta D$, gives
\[
 \mathbb P(U_{\mathrm{actual}}>\rho D)
 \le\mathbb P(U>\rho D)
 \le\exp\left(-\frac{\delta^2D^2}{2BD}\right)
 \le\exp\left(-\frac{\delta^2}{6\eta}\right).
\]
Since $\eta^{-1}\ge\Delta^\theta$, this is
\eqref{eq:local-power-tail} with $c:=\delta^2/6$.
No cap-failure probability is added to this bound:
\eqref{eq:local-clipping-domination} holds for every outcome, and
the loss $\xi$ has already been included in the clipped marginals.
All lower bounds imposed on $\Delta$ depend only on the fixed
constants, so a single $\Delta_0$ works uniformly in $k,D,h$ and $H$.
\end{proof}


\section{The colouring algorithm}
\label{sec:local-schedule}

\begin{proof}[Proof of Theorem~\ref{thm:local-one}]
We first prove the assertion when $k$ is rational and is supplied to
the processors; we remove this convention at the end.
Fix $\varepsilon\in(0,1)$. All constants chosen in the next paragraph
depend only on $\varepsilon$. Choose $b$ in the non-empty interval $(1,1/(1-\varepsilon))$.
Then choose $0<\theta<\min\{1/2,(1-b(1-\varepsilon))/2\}$, so that
\begin{equation}\label{eq:local-log-slack}
 b(1-\varepsilon)<1-2\theta.
\end{equation}
Choose $\gamma$ with $1/b<\gamma<1$.
Then $b\gamma>1$.
Since
\[
 \lim_{C\downarrow0}\frac{C}{b(1-\mathrm{e}^{-\gamma C})}
   =\frac1{b\gamma}<1,
\]
we can choose $C>0$ and then $\rho,\sigma$ with
\begin{equation}\label{eq:local-constant-choice}
 \mathrm{e}^{-\gamma C}<\rho<\sigma<1,\quad\text{and}\quad
 Q:=\frac{C}{b(1-\rho/\sigma)}<1.
\end{equation}
Let us show that this is possible. We have $1-\mathrm{e}^{-\gamma C}=\gamma C+o(C)$ as $C\downarrow0$. Choose $C$ so that
$C/[b(1-\mathrm{e}^{-\gamma C})]<1$. By continuity, the same strict inequality
still holds if $\mathrm{e}^{-\gamma C}$ in the denominator is replaced by
a slightly larger $\rho<1$. The function
$\sigma\mapsto C/[b(1-\rho/\sigma)]$ tends to
$C/[b(1-\rho)]<1$ as $\sigma\uparrow1$. Therefore some
$\rho<\sigma<1$ gives the required $Q<1$.
Finally choose $\tau\in(0,1)$ so that
\begin{equation}\label{eq:local-palette-slack}
 Q+3\tau<1.
\end{equation}
All these constants can be chosen rational, because the required inequalities are strict.

For a given $\Delta,k$, define the integer degree bounds, stopping
index, and sampler parameters by
\begin{align}
 D_0&:=\Delta,&
 D_{j+1}&:=\lfloor\rho D_j\rfloor,&
 s&:=\min\{j\ge0:D_j\le\tau\Delta/k\},
                                      \label{eq:local-degree-schedule}\\
 h_j&:=\lceil bk\sigma^j\rceil,&
 \eta&:=\frac1{\lceil\Delta^\theta\rceil},&
 T_j&:=\left\lceil\frac{8h_j}{1-\gamma}\right\rceil
 \quad(0\le j<s).                      \label{eq:local-h-schedule}
\end{align}
Set $w_j:=2h_j/D_j$. The same cap $\eta$ is used throughout. Since
$D_j\le\Delta\rho^j$ and $k\ge1>\tau$, we have
\begin{equation}\label{eq:local-s-bound}
 1\le s\le
 \left\lceil\frac{\ln(k/\tau)}{-\ln\rho}\right\rceil
 =O_\varepsilon(1+\ln k).
\end{equation}
At every executed phase,
\begin{equation}\label{eq:local-range}
 \frac{\tau\Delta}{k}<D_j\le\Delta,\quad\text{and}\quad
 1\le h_j\le bk+1\le b\ln\Delta+1.
\end{equation}
In particular $D_j$ tends to infinity uniformly in all these phases
and in the permitted choices of $k$.

We check the sampler hypotheses uniformly. Since
$\eta\ge\Delta^{-\theta}/2$, \eqref{eq:local-range} gives
\begin{align}
 \ln\left(\frac{\eta D_j}{2h_j}\right)
 &\ge (1-\theta)\ln\Delta
       -\ln k-\ln(bk+1)+\ln(\tau/4)\notag\\
 &\ge(1-\theta)\ln\Delta-2\ln\ln\Delta-O_\varepsilon(1).
                                                   \label{eq:local-L-bound}
\end{align}
Also $\ln(\eta D_j/(2h_j))\le\ln\Delta$, because
$\eta\le1$, $D_j\le\Delta$ and $h_j\ge1$.
By~\eqref{eq:local-log-slack},
\[
 h_j+1\le b(1-\varepsilon)\ln\Delta+2
       <(1-2\theta)\ln\Delta+2.
\]
It follows from~\eqref{eq:local-L-bound} that, eventually,
\begin{align*}
 &(1-\eta)\ln\left(\frac{\eta D_j}{2h_j}\right)-(h_j+1)\\
 &\quad\ge\theta\ln\Delta-2\ln\ln\Delta-O_\varepsilon(1)
                         -\eta\ln\Delta>0.
\end{align*}
Finally, $\eta h_j\le\Delta^{-\theta}(b\ln\Delta+1)\to0$.
Thus, after increasing $\Delta_0$, we have uniformly
\begin{equation}\label{eq:local-sampler-check}
 h_j\le(1-\eta)\ln(\eta/w_j)-1,
 \quad\text{and}\quad 8\eta h_j\le1-\gamma.
\end{equation}
In particular $0<w_j<\eta<1$ and $D_jw_j=2h_j$, so
Proposition~\ref{prop:marginal}, with $a:=h_j$, gives
\begin{equation}\label{eq:local-phase-marginal}
 D_j\mathbb P(v\in I)
 \ge h_j-4\eta h_j^2-\frac{4h_j^2}{T_j}
 \ge\gamma h_j.
\end{equation}
Indeed, \eqref{eq:local-sampler-check} and the choice of $T_j$ bound
each loss term by $(1-\gamma)h_j/2$. Since $w_j$ and $\eta$ are
rational, Lemma~\ref{lem:encoding} supplies a finite uniform label
alphabet and guarantees an independent set for every assignment,
pointwise domination by independent Bernoulli variables of parameter
$\eta$ read from individual vertex labels, and determining radius
$T_j+2$. Allowing this fixed relative
loss in the marginal makes the radius linear in $h_j$.

In phase $j$ the current graph $H_j$ is induced by the uncoloured
vertices. Take
\begin{equation}\label{eq:local-m-schedule}
 m_j:=\left\lceil\frac{CD_j}{h_j}\right\rceil
\end{equation}
runs of this sampler.
Choose their labels by one of the two procedures specified below, so
that all vertices of $H_j$ have at most $\rho D_j$ neighbours
uncovered by the runs. Give every covered vertex the colour of its
first covering run, using $m_j$ new colour names in this phase.
Each colour class is contained in an independent set. The graph left
uncoloured has maximum degree at most
$\lfloor\rho D_j\rfloor=D_{j+1}$.
At the end colour $H_s$ with $D_s+1$ further colours using the
fast degree-plus-one algorithm stated above.

The number of colours fits the claimed bound even with all rounding errors.
By \eqref{eq:local-degree-schedule},
\eqref{eq:local-h-schedule}, and \eqref{eq:local-m-schedule},
\begin{align}
 \sum_{j=0}^{s-1}m_j
 \le\sum_{j=0}^{s-1}\left(\frac{CD_j}{h_j}+1\right) \le\frac{C\Delta}{bk}\sum_{j=0}^{s-1}(\rho/\sigma)^j+s
 \le Q\frac{\Delta}{k}+s.                 \label{eq:local-colour-sum}
\end{align}
Moreover,
$D_s+1\le\tau\Delta/k+1$. Uniformly for $k\le\ln\Delta$,
\[
 \frac{k(s+1)}{\Delta}
 =O_\varepsilon\left(\frac{\ln\Delta(1+\ln\ln\Delta)}{\Delta}\right)
 \longrightarrow0.
\]
Increase $\Delta_0$ so that $s+1\le\tau\Delta/k$. Equations
\eqref{eq:local-palette-slack} and \eqref{eq:local-colour-sum} give
\begin{equation}\label{eq:local-total-colours}
 \sum_{j=0}^{s-1}m_j+D_s+1
 \le(Q+2\tau)\frac{\Delta}{k}<\frac{\Delta}{k}.
\end{equation}
The left-hand side is an integer, hence is at most
$\lfloor\Delta/k\rfloor$.

Write $R_j:=T_j+3$ for the radius of a degree constraint.
The total radius satisfies
\begin{align}
 \sum_{j=0}^{s-1}R_j
 \le\frac8{1-\gamma}\sum_{j=0}^{s-1}h_j+4s\le\frac8{1-\gamma}
          \left(\frac{bk}{1-\sigma}+s\right)+4s
 =O_\varepsilon(k).                         \label{eq:local-radius-sum}
\end{align}
Here \eqref{eq:local-s-bound} and $1+\ln k=O(k)$ for $k\ge1$
were used in the last step. This is the reason for decreasing $h_j$:
using $h_j$ of order $k$ in all $s$ phases would introduce a factor
of order $\ln k$.

We next justify the label choices and their probability of success.
Condition on the complete history before phase $j$, assuming all
previous reductions succeeded. Then $H_j$ is a fixed triangle-free
graph with maximum degree at most $D_j$, so the sampler estimates
and Lemma~\ref{lem:local-degree-tail} apply to fresh independent labels.
They apply uniformly over every such history.
To combine such bounds, consider the event that phase $j$ is
the first unsuccessful phase. Its probability is at most the
conditional failure bound for that phase. These first-failure
events are disjoint, so summing their bounds requires no
independence between phases. Let $c>0$ be the constant
in that lemma, fixed for the parameters already chosen.
For each vertex, the degree-failure probability
is at most $\mathrm{e}^{-c\Delta^\theta}$.

The corresponding dependency bound is
$d_j:=2D_j^{2R_j}$. Since $h_j\le bk+1$ and $k\le\ln\Delta$,
\begin{equation}\label{eq:local-log-dependency}
 \ln d_j\le\ln 2+2R_j\ln\Delta
            =O_\varepsilon((\ln\Delta)^2).
\end{equation}
As $\theta>0$ is fixed, $\Delta^\theta/(\ln\Delta)^2\to\infty$.
Consequently, uniformly in $j$,
\begin{equation}\label{eq:local-lll-holds}
 p_j:=d_j^{-1001},\quad \mathrm{e}^{-c\Delta^\theta}\le p_j,\quad\text{and}\quad p_jd_j^{1000}<1
\end{equation}
for all sufficiently large $\Delta$. Lemma~\ref{lem:local-constraints}
therefore applies. Notice that $d_j$ need not be a fixed power of
$\Delta$: the stronger probability estimate absorbs the radius in
the exponent of the dependency bound.

There are two regimes. Increase $\Delta_0$ once more so that
$s\le n$, which follows from \eqref{eq:local-s-bound} and
$\Delta\le n-1$.

\emph{If $\Delta^\theta\ge(8/c)\ln n$,} choose all labels independently
and directly execute the samplers in every phase.
Conditional on every preceding phase succeeding, the chance
that phase $j$ fails at any vertex is at most
$n \mathrm{e}^{-c\Delta^\theta}\le n^{-7}$. Summing over $s\le n$ phases
gives failure probability at most $n^{-6}$. The communication time for
these phases is $O_\varepsilon(k)$ by
\eqref{eq:local-radius-sum}.

\emph{If $\Delta^\theta<(8/c)\ln n$,} use Theorem~\ref{ext:local-lll}
in every phase, via Lemma~\ref{lem:local-constraints}. Keep one event
processor at every original vertex. At a vertex that has already been
coloured, its event is identically false and has an empty determining
set; labels are needed only on $H_j$. Thus the virtual instance has
$n$ processors, even if few original vertices remain uncoloured.
Each call then fails with probability at most $n^{-10}\le n^{-6}$. Equations
\eqref{eq:local-log-dependency} and
\eqref{eq:local-lll-holds} are unaffected by these isolated
events. A union bound over the phases gives failure probability at
most $n^{-5}$. In this regime,
\begin{equation}\label{eq:local-low-degree-log}
 \ln\Delta<\theta^{-1}\bigl(\ln\ln n+\ln(8/c)\bigr)
 =O_\varepsilon(1+\ln\ln n).
\end{equation}
For some absolute exponent $a_1$, Lemma~\ref{lem:local-constraints}
and~\eqref{eq:local-radius-sum} therefore bound the total phase time by
\begin{equation}\label{eq:local-low-degree-time}
 O_\varepsilon\left(\sum_{j=0}^{s-1}R_j
                         (1+\ln\ln n)^{a_1}\right)
 =O_\varepsilon\bigl(k(1+\ln\ln n)^{a_1}\bigr).
\end{equation}
Since $k\le\ln\Delta=O_\varepsilon(1+\ln\ln n)$ by
\eqref{eq:local-low-degree-log}, this is
$O_\varepsilon((1+\ln\ln n)^{a_1+1})$.
After increasing $\Delta_0$, we can absorb its
$\varepsilon$-dependent prefactor into one further power of
$1+\ln\ln n$, since $n\ge\Delta+1$. Thus the exponent in the
second term of~\eqref{eq:local-one-time} is absolute.

For the final degree-plus-one colouring, keep all original vertices,
making the previously coloured ones isolated, and use only the edges
of $H_s$. Ignore the new colours returned at previously coloured
vertices. This gives an $n$-processor invocation. Polynomial padding
by isolated vertices makes its failure probability at most $n^{-6}$,
and its time is $(1+\ln\ln n)^{O(1)}$. Palettes of different phases
and of this final step are disjoint, so their union is a proper
colouring whenever all steps succeed. The sum of the failure
probabilities is less than $n^{-1}$.

All instructions can be defined on unsuccessful histories as well.
For the exact finite alphabet, form the catalogue in
Lemma~\ref{lem:encoding} using the original degree bound $\Delta$,
while retaining $w_j=2h_j/D_j$, $\eta$ and $T_j$. This still gives the
same process on every graph of degree at most $D_j$, and makes every
trial well-defined even if a previous phase failed to attain its
advertised degree bound. Subroutines are run for their prescribed
number of rounds, and outputs on invalid inputs can be assigned
arbitrarily within the colour set. The success analysis uses
only the conditional guarantees on valid histories.

Finally, the two regimes and
\eqref{eq:local-radius-sum} give \eqref{eq:local-one-time}.

For general $k$, put $q:=\lfloor\Delta/k\rfloor$ and
$\kappa:=\Delta/q$. This is a rational input computable from $q,\Delta$.
For sufficiently large $\Delta$, uniformly in the stated range of $k$,
\[
 k\le\kappa\le\frac{k}{1-k/\Delta}\le2k,\quad\text{and}\quad
 \kappa-k\le\frac{k^2}{\Delta-k}=o(1).
\]
Indeed, $q\ge\Delta/k-1>0$ implies
$\kappa\le k/(1-k/\Delta)$; subtracting $k$ gives
$\kappa-k\le k^2/(\Delta-k)$.
This is at most $(\ln\Delta)^2/(\Delta-\ln\Delta)\to0$.
The gap $(\varepsilon/2)\ln\Delta$ eventually exceeds this error,
so $\kappa\le(1-\varepsilon/2)\ln\Delta$.
Apply the rational case, already proved for every fixed positive
error parameter, with $\varepsilon/2$ and $\kappa$.
It uses at most $\lfloor\Delta/\kappa\rfloor=q$ colours, and its
$O_{\varepsilon/2}(\kappa)$ term is $O_\varepsilon(k)$.
Increasing $\Delta_0$ to the threshold of that application completes
the proof for the stated finite input.
\end{proof}

\subsection{Implementation and comparison}
\label{sec:local-comparison}

The finite uniform labels can be sampled with private fair bits, using rejection sampling as follows.
For $M=1$ the only symbol is chosen deterministically. For $M\ge2$,
put $a:=\lceil\log_2 M\rceil$ and use $a$ fair bits to draw a
uniform integer $J$ from $\{0,\ldots,2^a-1\}$. If $J<M$, output
$J+1$; otherwise discard these bits and try again independently.
Each accepted value is
equally likely, and the acceptance probability $M/2^a$ is at least
$1/2$. The same construction samples any finite rational distribution
by using a common denominator.
Use implementations of the samplers and auxiliary algorithms with
a prescribed finite number of communication rounds and a bounded
number of draws from finite rational probability tables per round.
For fixed $n$ and
the input parameters, there are only finitely many inputs and
histories, so there is a finite deterministic upper bound $F\ge1$
on the total number of such draws. No polynomial bound on $F$ is required. To obtain fixed finite random
labels, stop each rejection sampler after
$\lceil\log_2 F+12\log_2 n\rceil$ trials and use a fixed default value
upon rejection throughout. Coupling with the untruncated procedure,
the probability of any discrepancy is at most
$F\,2^{-\lceil\log_2 F+12\log_2 n\rceil}\le n^{-12}$.
Thus this change adds at most $n^{-12}$ to the failure probability
and no communication rounds. The slack in the preceding proof still
gives the stated $1-n^{-1}$ guarantee.
Increasing the constant $8/c$ in the regime cutoff and the
rejection-sampling cutoff, and applying polynomial padding to both
auxiliary algorithms as in~\eqref{eq:padding-guarantee}, gives
$1-n^{-A}$ for any prescribed fixed $A>0$, with constants depending
also on $A$.

All event predicates and their probability tables are finite, so the
local computations required by the Local Lemma can be performed by
finite enumeration. No polynomial bound is claimed for this local
computation, for the alphabet size, or for message lengths. These
resources are unrestricted in LOCAL. The communication bound is
obtained on the original graph, with the factor $R_j$ in the virtual
simulation explicitly included.

Taking $k:=(1-\varepsilon)\ln\Delta$ gives, in particular, a colouring
with at most
$\lfloor\Delta/((1-\varepsilon)\ln\Delta)\rfloor$ colours in
$O_\varepsilon(\ln\Delta)+\ln^{O(1)}\ln n$ rounds.
Together with Theorem~\ref{thm:local-one}, this gives the full
constant-one range. The capped sampler supplies the marginal and independent cap;
Lemma~\ref{lem:local-degree-tail} supplies the small failure
probabilities required by the distributed Local Lemma.

\section{Borel and measurable colourings}\label{sec:borel}

A \emph{standard Borel space} is a set equipped with the Borel
$\sigma$-algebra of some Polish topology. A graph $G$ on a standard
Borel space $X$ is \emph{Borel} if its adjacency relation is a Borel
subset of $X\times X$. A colouring with finitely many colours is Borel if
each colour class is Borel. The smallest possible number of colours is the
\emph{Borel chromatic number} $\chi_B(G)$. Given a Borel probability
measure $\mu$ on $X$, we define the \emph{measurable chromatic number}
$\chi_\mu(G)$ in the same way, requiring the colour classes to belong
to the completion of the Borel $\sigma$-algebra with respect to $\mu$.

Let $\tau$ be a Polish topology on $X$ whose Borel $\sigma$-algebra
is the specified one. A subset of $X$ has the \emph{Baire property}
in $\tau$ if its symmetric difference with some open set is meagre,
that is, a countable union of nowhere dense sets. A finite colouring
is \emph{Baire-measurable} with respect to $\tau$ if each colour
class has the Baire property. All colourings considered here are
proper everywhere, including on any exceptional null or meagre set.

For positive integers $a,b$, a \emph{Borel $b$-fold colouring with
$a$ colours} is a Borel map
$f:X\to\binom{[a]}{b}$ such that $f(u)\cap f(v)=\varnothing$ whenever
$uv\in E(G)$. The \emph{fractional Borel chromatic number} is
\begin{equation}\label{eq:fractional-borel-definition}
 \chi_B^f(G):=\inf\left\{\frac ab:
       G\text{ has a Borel $b$-fold colouring with $a$ colours}\right\}.
\end{equation}
Equivalently, one may use $a$ Borel independent sets covering each
vertex at least $b$ times: a fixed ordering of the sets allows one to
keep precisely the first $b$ memberships at each vertex. See
\cite{Bernshteyn22} for fractional Borel colourings of Schreier graphs
and \cite[Section~2.2]{Weilacher26} for their relation to homomorphisms
to Kneser graphs.

For a positive integer $r$, the graph $G^r$ joins distinct vertices at
distance at most $r$ in $G$. The \emph{asymptotic separation index}
$\operatorname{asi}(G)$ is the least nonnegative integer $s$ such that,
for every $r$, there is a Borel partition
$X=X_0\sqcup\cdots\sqcup X_s$ for which every component of each
$G^r[X_i]$ is finite. The partition may depend on $r$, and no uniform
bound on the sizes of its components is required. If there is no such
$s$, put $\operatorname{asi}(G):=\infty$. This is the convention of
\cite[Definition~1.11]{BernshteynWeilacher25}.

\subsection{Finite averaging and fractional colourings}

The following elementary observation turns a finite local random
construction into a fractional Borel colouring. A \emph{partial
$q$-colouring} takes values in $\{0\}\cup[q]$, where $0$ means
uncoloured; it is proper if adjacent coloured vertices have different
colours.

\begin{lemma}[Finite averaging]\label{lem:borel-finite-averaging}
Let $G$ be a Borel graph of bounded degree and let $R\ge1$.
Suppose that a radius-$R$ rule with a finite uniform label alphabet $\Lambda$ produces a proper
partial $q$-colouring for every label assignment. Suppose also that,
under independent uniform labels, every vertex is coloured with
probability at least $p>0$. Then
\begin{equation}\label{eq:borel-finite-averaging}
 \chi_B^f(G)\le \frac qp.
\end{equation}
\end{lemma}
\begin{proof}
The graph $G^{2R}$ is Borel and has bounded degree. Hence it has a
Borel proper colouring $h:X\to[L]$ for some finite $L$, by
\cite[Proposition~4.6]{KechrisSoleckiTodorcevic99}. In particular,
$h$ is injective on every ball $B_G(v,R)$.

Put $\Sigma:=\Lambda^{[L]}$ and $M:=|\Sigma|$. For each
$\sigma\in\Sigma$, give $v$ the label $\sigma(h(v))$, apply the rule,
and let $I_{\sigma,j}$ be the set assigned colour $j$, for $j\in[q]$.
Each $I_{\sigma,j}$ is independent. It is also Borel: the labels are
Borel, and a bounded-radius rule on a bounded-degree Borel graph with
a finite alphabet is Borel. One can verify the latter assertion by
partitioning vertices according to the finitely many possible
labelled rooted neighbourhood types; these partitions are Borel by
the Lusin--Novikov theorem, since all neighbourhoods are finite
\cite[Theorem~18.10]{Kechris95}.

Choose $\sigma$ uniformly from $\Sigma$. The labels on $B_G(v,R)$
are then independent and uniform, since the values of $h$ on that
ball are distinct. Consequently, if
\[
 m(v):=|\{\sigma\in\Sigma:v\text{ is coloured under }\sigma\}|,
\]
then $m(v)\ge pM$. If $X$ is empty there is nothing to prove. Otherwise, put
$b:=\lceil pM\rceil$. Since $m(v)$ is integral, $m(v)\ge b$
for every $v$.
Every vertex belongs to exactly $m(v)$ of
the $qM$ sets $I_{\sigma,j}$. Keeping its first $b$ memberships gives
a Borel $b$-fold colouring with $qM$ colours. Thus
$\chi_B^f(G)\le qM/b\le q/p$. 
\end{proof}

\begin{corollary}\label{cor:borel-fractional-explicit}
For every sufficiently large integer $D$, every triangle-free Borel
graph $G$ of maximum degree at most $D$ satisfies
\begin{equation}\label{eq:borel-fractional-explicit}
 \chi_B^f(G)\le
 \frac{D}{\ln D-7\ln\ln D-6}
 =\bigl(1+o(1)\bigr)\frac{D}{\ln D}.
\end{equation}
\end{corollary}
\begin{proof}
Regard the independent set in Theorem~\ref{thm:sampler} as a proper
partial $1$-colouring, and apply
Lemma~\ref{lem:borel-finite-averaging} with
$p:=(\ln D-7\ln\ln D-6)/D$.
\end{proof}

\subsection{Transferring the LOCAL algorithm}

A colouring problem is \emph{locally checkable} if a fixed-radius
neighbourhood determines whether the constraints at a vertex are
satisfied. In particular, proper $q$-colouring is locally checkable
with radius $1$.
We use two transfer theorems in the following form. Let $\mathcal C$
be a class of finite graphs of bounded degree, closed under adding
isolated vertices, and suppose that a locally checkable problem on
$\mathcal C$ has a randomised LOCAL algorithm taking $o(\ln n)$
rounds on $n$-vertex graphs, with failure probability at most $1/n$. If every finite
induced subgraph of a bounded-degree Borel graph $G$ belongs to
$\mathcal C$, then:
\begin{enumerate}
\item\label{it:transfer-measurable} the problem has a $\mu$-measurable solution on $G$ for every
Borel probability measure $\mu$, by
\cite[Theorem~2.14(i)]{Bernshteyn23};
\item\label{it:transfer-baire} the problem has a Baire-measurable solution on $G$ for every
Polish topology compatible with its Borel structure, by
\cite[Theorem~2.14(ii)]{Bernshteyn23};
\item\label{it:transfer-finite-asi} if $\operatorname{asi}(G)<\infty$, the problem has a Borel
solution on $G$, by
\cite[Theorem~1.42]{BernshteynWeilacher25}.
\end{enumerate}
The little-$o$ condition concerns $n\to\infty$ with the degree bound
and the colouring problem fixed. The solution may depend on the
measure or the chosen topology.\footnote{The fixed-parameter
distributed Local Lemma input in \cite[Theorem~5.10]{Bernshteyn23}
also follows from the corrected analysis. If
$p(d+1)^8\le2^{-15}$ with fixed $d\ge2$, take
$q_0:=1/[4(d+1)]$ and $\zeta:=1/\ln d$ in the technical form of
\cite[Theorem~1, Section~5.4]{GhaffariHalldorssonMausNolin26}.
Then $q_0<1/[\mathrm{e}(d+1)]$ and
$p\,2(d+1)d^{6+\zeta}/q_0\le8\mathrm{e}\,2^{-15}<1$.
Together with their Lemma~9(1), whose slack condition holds since
$\mathrm{e}q_0d(1+1/4)<5\mathrm{e}/16<1$, this gives $o(\ln n)$ rounds for fixed
$d$, as required by the transfer argument. The cases $d\le1$ are
elementary.}

The randomised model in these transfer statements uses independent
finite random labels in place of preassigned distinct identifiers.
We make the normalisation explicit. Fix a degree bound $D$ and a
palette supplied by Theorem~\ref{thm:local-one}. Given an $n$-vertex
triangle-free graph $H$ of maximum degree at most $D$, where $n\ge1$, advertise
$N:=4n^3+D+1$ vertices. For the analysis, pad $H$ with a disjoint
$D$-star and isolated vertices to obtain a graph on $N$ vertices
whose maximum degree is exactly $D$. Each actual processor chooses
an independent uniform identifier in $[N]$ and runs the algorithm
with advertised size $N$ and degree bound $D$, using the finite
private random strings from Section~\ref{sec:local-comparison}.
The added components need not be simulated, since they have no edges
to $H$. Conditional on the actual identifiers being distinct, they
extend to distinct identifiers on the padded graph, so the
conditional failure probability on $H$ is at most $1/N$.
The union bound for identifier collisions therefore gives
\begin{equation}\label{eq:borel-id-normalisation}
 \mathbb P(\text{failure on }H)
 \le\frac1N+\frac{\binom n2}{N}\le\frac1n.
\end{equation}
This produces a rule with independent finite uniform labels. Since
$\ln N=O_D(\ln n)$ as $n\to\infty$, the running time remains
$o(\ln n)$ for fixed $D$.


\begin{proof}[Proof of Theorem~\ref{thm:borel-measurable}]
Set $\varepsilon:=\delta/(1+\delta)$ and
$k:=\ln D/(1+\delta)=(1-\varepsilon)\ln D$. For sufficiently large
$D$, we have $k\ge1$. Theorem~\ref{thm:local-one}, together with the
normalisation above, gives a randomised algorithm for proper
$q$-colouring on the class $\mathcal C_D$ of all finite triangle-free
graphs of maximum degree at most $D$. For fixed $D$ its running time
satisfies
\begin{equation}\label{eq:borel-sublog-time}
 t_D(n)=O_\delta(\ln D)+\ln^{O(1)}\ln(n+D)
       =o(\ln n).
\end{equation}
Every finite induced subgraph of $G$ belongs to $\mathcal C_D$.
Thus~\cite[Theorem~2.14]{Bernshteyn23} proves Parts~(\ref{it:borel-measurable}) and~(\ref{it:borel-baire}), and \cite[Theorem~1.42]{BernshteynWeilacher25} proves Part~(\ref{it:borel-finite-asi}).

For Part~(\ref{it:borel-fractional}), increase $D_0$ so that
\[
 \frac{D}{\ln D-7\ln\ln D-6}
 \le\left(1+\frac\delta2\right)\frac{D}{\ln D}
 \le\left\lfloor(1+\delta)\frac{D}{\ln D}\right\rfloor=q.
\]
Then Corollary~\ref{cor:borel-fractional-explicit} applies.
\end{proof}



\begin{remark}[The measure convention]\label{rem:borel-measure-convention}
Part~(\ref{it:borel-measurable}) holds also for every $\sigma$-finite Borel measure $\mu$.
Indeed, if $\mu$ is nonzero, choose a Borel partition
$X=\bigsqcup_{j\ge1}A_j$ with $\mu(A_j)<\infty$, and put
\[
 \nu_0(B):=\sum_{j\ge1}
    \frac{2^{-j}\mu(B\cap A_j)}{1+\mu(A_j)},
 \quad\text{and}\quad \nu(B):=\frac{\nu_0(B)}{\nu_0(X)}.
\]
Then $\nu$ is a Borel probability measure with the same null Borel
sets as $\mu$, so their completed Borel $\sigma$-algebras agree. A
$\nu$-measurable colouring is therefore $\mu$-measurable. For the
zero measure, every subset is measurable, and an ordinary
$q$-colouring exists by the finite result and compactness
\cite[Theorem~1]{deBruijnErdos51}.

One cannot interpret ``every Borel measure'' as including arbitrary
non-$\sigma$-finite measures. For counting measure on the Borel sets
of an uncountable standard Borel space, the only null set is the
empty set, so measurable colourings are exactly Borel colourings.
Marks constructed, for every positive integer $D$, a Borel forest
of maximum degree $D$ with Borel chromatic number $D+1$
\cite[Theorem~1.3]{Marks16}. These graphs
exclude the asserted asymptotic bound for that interpretation.
\end{remark}


\section{Optimality of the constants}\label{sec:optimality}

Let us discuss the optimality of the leading constants in our results.

The coefficient $1$ in Theorem~\ref{thm:sampler} is optimal.
Indeed, Rahman and Vir\'ag \cite[Theorem~2.1]{RahmanVirag17} proved
that every factor of i.i.d.\ independent set on the infinite
$D$-regular tree has density at most $(1+o(1))\ln D/D$ as
$D\to\infty$; see also \cite[Theorem~3.1]{Bernshteyn22}.
Applying any isomorphism-invariant finite-radius sampler to this
tree gives such a factor. A finite uniform label can be sampled from
a uniform label in $[0,1]$, so the conclusion applies to the label
convention used here. There is no restriction on how the radius
depends on $D$. This does not assert optimality of the additive
$\ln\ln D$ term, the determining radius, or the independent cap.

The fractional Borel and measurable lower bounds follow directly
from Bernshteyn \cite[Corollaries~1.2 and~1.4]{Bernshteyn22}.
For $m\ge2$, let $F_m$ be the free group of rank $m$, and let $G_m$
be the Schreier graph of the free part of the Bernoulli shift
$F_m\curvearrowright\{0,1\}^{F_m}$, with respect to the standard
free generators. Let $\beta_m$ be the fair-coin product
probability measure restricted to the free part. Every component of
$G_m$ is a $2m$-regular tree, and the cited corollaries give
\begin{equation}\label{eq:bernoulli-fractional-lower}
 \chi_{\beta_m}(G_m)\ge\chi_B^f(G_m)
       =(2+o(1))\frac{m}{\ln m}.
\end{equation}
The comparison between the measurable and fractional Borel
chromatic numbers in~\eqref{eq:bernoulli-fractional-lower} is specific
to these shift graphs. Taking $m:=\lfloor D/2\rfloor$ shows that both
parameters can be at least $(1-o(1))D/\ln D$ for forests of maximum
degree at most $D$. Thus the coefficient $1$ in
Theorem~\ref{thm:borel-measurable} Items~\ref{it:borel-fractional} and \ref{it:borel-measurable}
is best possible, even for acyclic graphs.


The same examples give a lower bound for randomised algorithms with
sublogarithmic running time. Here the degree is fixed before the
number of vertices tends to infinity.

\begin{proposition}\label{prop:local-palette-optimality}
Suppose that, for each sufficiently large $D$, an integer $q_D$ and
a randomised LOCAL algorithm are given such that every $n$-vertex
triangle-free graph of maximum degree at most $D$ is properly
$q_D$-coloured with probability at least $1-1/n$ in $t_D(n)$ rounds.
If $t_D(n)=o(\ln n)$ for every fixed $D$, then
\begin{equation}\label{eq:local-palette-optimality}
 q_D\ge(1-o(1))\frac{D}{\ln D}
       \quad\text{as }D\to\infty.
\end{equation}
\end{proposition}
\begin{proof}
Fix $D$ and put $m:=\lfloor D/2\rfloor$. All finite induced
subgraphs of $G_m$ are triangle-free and have maximum degree at
most $D$. We first put the algorithm in the finite-random-label
model used by the transfer theorem.
For an $n$-vertex input, advertise $N:=4n^3+D+1$ vertices, padding
with a disjoint $D$-star and isolated vertices, and give each actual
processor an independent uniform identifier in $[N]$.
For each fixed $N$, there are only finitely many input graphs and
assignments of distinct identifiers from $[N]$. On every successful
execution only finitely many private random bits and local
computation steps are used. Hence common finite cutoffs for this
finite collection of inputs add at most $1/N$ to the global failure
probability. If a cutoff is exceeded, use fixed default messages
and output a fixed colour. The cutoffs need not be efficient or
uniform in $N$, since the transfer theorem only
requires a finite-alphabet radius rule for each chosen input size.
Distinct identifiers on the actual input extend to distinct
identifiers on the padded graph. Thus the total failure probability
on the actual input is at most
\[
 \frac2N+\frac{\binom n2}{N}\le\frac1n.
\]
Since $\ln N=O_D(\ln n)$, the running time remains $o(\ln n)$ for
fixed $D$.

The measurable transfer theorem
\cite[Theorem~2.14]{Bernshteyn23}, in the form stated in
Section~\ref{sec:borel}, now gives a $\beta_m$-measurable proper
$q_D$-colouring of $G_m$. Consequently,
\[
 q_D\ge\chi_{\beta_m}(G_m)
       \ge\chi_B^f(G_m)
       =(1+o(1))\frac{D}{\ln D},
\]
where the last equality follows from
\eqref{eq:bernoulli-fractional-lower}.
\end{proof}

For every fixed $D$ and $\varepsilon>0$, the running time in
Theorem~\ref{thm:local-one} is $o(\ln n)$. Taking
$k:=(1-\varepsilon)\ln D$ and then letting $\varepsilon$ tend to zero
shows that its leading coefficient is optimal in this class of
running times. This does not establish optimality of the precise
round complexity in~\eqref{eq:local-one-time} or of the number of
colours for finite graphs without a locality restriction.


The shift graphs above do not give the same lower bounds for
Baire-measurable colourings. Conley and Miller
\cite{ConleyMiller16} proved that every locally finite Borel graph
$G$ with $\chi(G)<\infty$ has a Baire-measurable colouring with at
most $2\chi(G)-1$ colours, for every compatible Polish topology.
In particular, every locally finite Borel forest has such a
$3$-colouring.

For Borel colourings, Conley, Jackson, Marks, Seward and Tucker-Drob
\cite[Theorem~8.1]{conley2023borel} proved that every locally finite
Borel graph $G$ with $\chi(G)<\infty$ satisfies
\[
 \chi_B(G)\le(\operatorname{asi}(G)+1)(\chi(G)-1)+1
 \quad\text{if }\operatorname{asi}(G)<\infty.
\]
In particular, this gives $2\chi(G)-1$ when
$\operatorname{asi}(G)\le1$, and $\operatorname{asi}(G)+2$ for forests.
However, the above shift graphs $G_m$ have infinite ASI.
\hide{Eg Marks's result \cite{Marks16} that
$\chi_B(G_m)=2m+1$
contradicts the finite-ASI version of Brooks's theorem
\cite[Theorem~1.17]{BernshteynWeilacher25} if their ASI is finite.}

Finite graphs have asymptotic separation index zero. A classical
result of Bollob\'as \cite[Theorem~1 and Corollary~3]{Bollobas81}
(see also \cite{Bollobas78}) implies that, for every sufficiently
large $D$, there is a finite triangle-free graph $F_D$ of maximum
degree $D$ with
\begin{equation}\label{eq:finite-asi-lower}
 \chi(F_D)>\frac{D}{2\ln D}.
\end{equation}
Such graphs can be chosen $D$-regular and with any prescribed lower
bound on their girth. Equipped with the discrete topology, finite
graphs give the same lower bound for Baire-measurable colourings.
Hence the optimal leading coefficient in
each of the finite-ASI and Baire-measurable bounds lies between
$1/2$ and $1$. Determining these coefficients remains open.


\section*{Acknowledgements}
Oleg Pikhurko was supported by ERC Advanced Grant 101020255 and by a
grant of access to OpenAI models through the ChatGPT for Academic
Researchers program.

\section*{AI disclosure}

AI tools (ChatGPT 6) were used in various ways in this project, including generation of candidate proofs and writing of this manuscript. Although almost all key mathematical ideas of this manuscript were suggested by AI, iterative guidance was required in order to obtain these. The current draft was primarily written by AI, with the authors doing some further editing to improve the presentation. The authors plan to produce a properly written manuscript in the near future.

\bibliographystyle{alpha}
\bibliography{\jobname}
\end{document}