HEXAGONbeta

Local independent sets and colourings of triangle-free graphs

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatoricsmath.LO — Logiccs.DM — Discrete Mathematicscs.DS — Data Structures and Algorithms

Contributed by Matthew Bowen, András Máthé, Oleg Pikhurko ↗

Version 1 / Oct 31, 2026 / CC BY 4.0

Abstract

This AI-assisted draft constructs, for every sufficiently large DD, a local rule of radius O((ln⁡D)2)O((\ln D)^2) that produces, on any triangle-free graph GG of maximum degree at most DD, a random independent set that includes each vertex with probability at least (1−oD(1))ln⁡D/D(1-o_D(1))\ln D/D. Further properties of the rule yield, for every fixed ε>0\varepsilon>0 and all sufficiently large DD, a randomised LOCAL algorithm that colours any such finite graph GG with at most (1+ε)D/ln⁡D(1+\varepsilon)D/\ln D colours, with high probability, in Oε(ln⁡D)+(ln⁡ln⁡∣V(G)∣)O(1)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.

Provenance statement

The contributors have convinced themselves that all main results (Theorems 1.1-1.3) are correct but have not verified all intermediate auxiliary steps to the letter.

Tools used

OpenAI
ChatGPTVersion Astra 6

References

  1. M. Ajtai, J. Koml ó s, and E. Szemer é di. A note on Ramsey numbers. Journal of Combinatorial Theory, Series A , 29:354--360, 1980.
  2. A. Bernshteyn, T. Brazelton, R. Cao, and A. Kang. Counting colorings of triangle-free graphs. Journal of Combinatorial Theory, Series B , 161:86--108, 2023. arXiv:2109.13376.arXiv
  3. A. Bernshteyn. Borel fractional colorings of Schreier graphs. Annales Henri Lebesgue , 5:1151--1160, 2022. arXiv:2105.11557.arXiv
  4. A. Bernshteyn. Distributed algorithms, the Lovász Local Lemma , and descriptive combinatorics. Inventiones Mathematicae , 233:495--542, 2023. arXiv:2004.04905.arXiv
  5. T. Bohman and P. Keevash. Dynamic concentration of the triangle-free process. Random Structures & Algorithms , 58:221--293, 2021.
  6. S. Boucheron, G. Lugosi, and P. Massart. On concentration of self-bounding functions. Electronic Journal of Probability , 14:1884--1899, 2009.
  7. B. Bollob á s. Chromatic number, girth and maximal degree. Discrete Mathematics , 24:311--314, 1978.
  8. B. Bollob á s. The independence ratio of regular graphs. Proceedings of the American Mathematical Society , 83:433--436, 1981.
  9. P. Buys, J. van den Heuvel, and R. J. Kang. Triangle-free graphs with the fewest independent sets. To appear in Combinatorica; arXiv:2503.10002, 2025.arXiv
  10. A. Bernshteyn and F. Weilacher. Borel versions of the Local Lemma and LOCAL algorithms for graphs of finite asymptotic separation index. Transactions of the American Mathematical Society , 378:8183--8221, 2025.
Show all 41 referencesShow fewer references
  1. Clinton T Conley, Steve C Jackson, Andrew S Marks, Brandon M Seward, and Robin D Tucker-Drob. Borel asymptotic dimension and hyperfinite equivalence relations. Duke Mathematical Journal , 172(16):3175--3226, 2023.
  2. M. Campos, M. Jenssen, M. Michelen, and J. Sahasrabudhe. A new lower bound for the Ramsey numbers R(3,k)R(3,k) . arXiv:2505.13371, 2025.arXiv
  3. Y.-J. Chang, W. Li, and S. Pettie. Distributed (Δ+1)(\Delta+1) -coloring via ultrafast graph shattering. SIAM Journal on Computing , 49:497--539, 2020. arXiv:1711.01361.arXiv
  4. C. T. Conley and B. D. Miller. A bound on measurable chromatic numbers of locally finite Borel graphs. Mathematical Research Letters , 23:1633--1644, 2016.
  5. K.-M. Chung, S. Pettie, and H.-H. Su. Distributed algorithms for the Lovász local lemma and graph coloring. Distributed Computing , 30:261--280, 2017.
  6. P. Davies. Improved distributed algorithms for the Lovász Local Lemma and edge coloring. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms , pages 4273--4295. SIAM, 2023.
  7. N. G. de Bruijn and P. Erdős. A colour problem for infinite graphs and a problem in the theory of relations. Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen, Series A , 54:371--373, 1951.
  8. E. Davies, M. Jenssen, W. Perkins, and B. Roberts. On the average size of independent sets in triangle-free graphs. Proceedings of the American Mathematical Society , 146:111--124, 2018. arXiv:1606.01043.arXiv
  9. P. Davies-Peck and X. Zhang. Triangle-free coloring in LOCAL via resilient Lovász Local Lemma . arXiv:2608.13357, 2026.arXiv
  10. R. Durrett. Probability: Theory and Examples , volume 49 of Cambridge Series in Statistical and Probabilistic Mathematics . Cambridge University Press, Cambridge, fifth edition, 2019. Author's 11 January 2019 version: https://sites.math.duke.edu/~rtd/PTE/PTE5_011119.pdf.link
  11. M. Fischer and M. Ghaffari. Sublogarithmic distributed algorithms for Lovász Local Lemma , and the complexity hierarchy. In 31st International Symposium on Distributed Computing , volume 91 of Leibniz International Proceedings in Informatics , pages 18:1--18:16, 2017. arXiv:1705.04840.arXiv
  12. M. Flin, M. Ghaffari, M. M. Halld ó rsson, Y. Maus, and A. Nolin. LOCAL LLL in poly⁡(log⁡log⁡n)\operatorname{poly}(\log\log n) rounds. arXiv:2610.17133, 2026.arXiv
  13. G. Fiz Pontiveros , S. Griffiths, and R. Morris. The triangle-free process and the Ramsey number R(3,k)R(3,k) . Memoirs of the American Mathematical Society , 263:v+125, 2020. Memoir 1274.
  14. M. Ghaffari, D. G. Harris, and F. Kuhn. On derandomizing local distributed algorithms. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science , pages 662--673. IEEE, 2018. arXiv:1711.02194.arXiv
  15. M. Ghaffari, M. M. Halld ó rsson, Y. Maus, and A. Nolin. Robust shattering arguments. arXiv:2606.27847, 2026.arXiv
  16. S. Harris, Z. Hefty, P. Horn, D. King, and F. Pfender. A short proof that R(3,k)=Θ(k2/log⁡k)R(3,k)=\Theta(k^2/\log k) . arXiv:2609.01782, 2026.arXiv
  17. Z. Hefty, P. Horn, D. King, and F. Pfender. Improving R(3,k)R(3,k) in just two bites. arXiv:2510.19718, 2025.arXiv
  18. A. S. Kechris. Classical Descriptive Set Theory , volume 156 of Graduate Texts in Mathematics . Springer-Verlag, New York, 1995.
  19. J. H. Kim. The Ramsey number R(3,t)R(3,t) has order of magnitude t2/log⁡tt^2/\log t . Random Structures & Algorithms , 7:173--207, 1995.
  20. T. Kelly and L. Postle. Fractional coloring with local demands and applications to degree-sequence bounds on the independence number. Journal of Combinatorial Theory, Series B , 169:298--337, 2024. arXiv:1811.11806.arXiv
  21. A. S. Kechris, S. Solecki, and S. Todorcevic. Borel chromatic numbers. Advances in Mathematics , 141:1--44, 1999.
  22. A. S. Marks. A determinacy approach to Borel combinatorics. Journal of the American Mathematical Society , 29:579--600, 2016.
  23. M. Molloy. The list chromatic number of graphs with small clique number. Journal of Combinatorial Theory, Series B , 134:264--284, 2019. arXiv:1701.09133.arXiv
  24. M. Molloy and B. Reed. Graph Colouring and the Probabilistic Method , volume 23 of Algorithms and Combinatorics . Springer-Verlag, Berlin, 2002.
  25. A. Martinsson and R. Steiner. Random independent sets in triangle-free graphs. Forum of Mathematics, Sigma , 13:e156, 2025.
  26. R. A. Moser and G. Tardos. A constructive proof of the general Lovász Local Lemma . Journal of the ACM , 57:11:1--11:15, 2010. arXiv:0903.0544.arXiv
  27. S. Pettie and H.-H. Su. Distributed coloring algorithms for triangle-free graphs. Information and Computation , 243:263--280, 2015.
  28. V. Rozho ň and M. Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 350--363. ACM, 2020. arXiv:1907.10937.arXiv
  29. M. Rahman and B. Virág. Local algorithms for independent sets are half-optimal. The Annals of Probability , 45:1543--1577, 2017. arXiv:1402.0485.arXiv
  30. J. B. Shearer. A note on the independence number of triangle-free graphs. Discrete Mathematics , 46:83--87, 1983.
  31. F. Weilacher. Borel homomorphisms from forests to Kneser graphs. arXiv:2601.19045, 2026.arXiv

Version history

  1. v1Submitted by Oleg PikhurkoInitial depositCurrentOct 30, 2026