ON HOMOMORPHISM GRAPHS

Sebastian Brandt ; Yi-Jun Chang ; Jan Grebík ; Christoph Grunau ; Václav Rozhoň ; Zoltán Vidnyánszky

Forum of Mathematics, Pi, Tome 12 (2024)

Résumé

We introduce new types of examples of bounded degree acyclic Borel graphs and study their combinatorial properties in the context of descriptive combinatorics, using a generalization of the determinacy method of Marks [Mar16]. The motivation for the construction comes from the adaptation of this method to the $\mathsf {LOCAL}$ model of distributed computing [BCG+21]. Our approach unifies the previous results in the area, as well as produces new ones. In particular, strengthening the main result of [TV21], we show that for $\Delta>2$, it is impossible to give a simple characterization of acyclic $\Delta $-regular Borel graphs with Borel chromatic number at most $\Delta $: such graphs form a $\mathbf {\Sigma }^1_2$-complete set. This implies a strong failure of Brooks-like theorems in the Borel context.

Détail

DOI : 10.1017/fmp.2024.8

Bibliographie

[BBE+20] Balliu, A., Brandt, S., Efron, Y., Hirvonen, J., Maus, Y., Olivetti, D. and Suomela, J., ‘Classification of distributed binary labeling problems’, in 34th International Symposium on Distributed Computing, DISC 2020 (Virtual Conference, 2020), 1–17.Google Scholar | DOI

[BCG+21] Brandt, S., Chang, Y.-J., Grebík, J., Grunau, C., Rozhoň, V. and Vidnyánszky, Z., ‘Local problems on trees from the perspectives of distributed algorithms, finitary factors, and descriptive combinatorics’, Preprint, 2021, . A short version of the paper was presented at the 13th Innovations in Theoretical Computer Science conference (ITCS 2022).Google Scholar | arXiv

[Ber21] Bernshteyn, A., ‘Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms’, Preprint, 2021, .Google Scholar | arXiv

[Ber23] Bernshteyn, A., ‘Distributed algorithms, the Lovász Local Lemma, and descriptive combinatorics’, Invent. Math. 233 (2023), 495–542.Google Scholar | DOI

[BFH+16] Brandt, S., Fischer, O., Hirvonen, J., Keller, B., Lempiäinen, T., Rybicki, J., Suomela, J. and Uitto, J., ‘A lower bound for the distributed Lovász local lemma’, in Proc. 48th ACM Symp. on Theory of Computing (STOC) (Cambridge, MA, 2016), 479–488.Google Scholar

[Bol81] Bollobás, B., ‘The independence ratio of regular graphs’, Proc. Amer. Math. Soc. 83(2) (1981), 433–436.Google Scholar | DOI

[CGA+16] Csóka, E., Grabowski, Ł., András, M., Pikhurko, O. and Tyros, K., ‘Borel version of the local lemma’, Preprint, 2016, .Google Scholar | arXiv

[CJM+20] Conley, C. T., Jackson, S., Marks, A. S., Seward, B. and Tucker-Drob, R., ‘Hyperfiniteness and Borel combinatorics’, J. Eur. Math. Soc. (JEMS) 22(3) (2020), 877–892.Google Scholar | DOI

[CK11] Caicedo, A. E. and Ketchersid, R., ‘A trichotomy theorem in natural models of ’, in Set Theory and Its Applications, Contemporary Mathematics volume 533 (American Mathematical Society, Providence, RI, 2011), 227–258.Google Scholar

[CMSV21] Carroy, R., Miller, B. D., Schrittesser, D. and Vidnyánszky, Z., ‘Minimal definable graphs of definable chromatic number at least three’, Forum Math. Sigma 9 (2021), e7.Google Scholar | DOI

[CMTD16] Conley, C. T., Marks, A. S. and Tucker-Drob, R. D., ‘Brooks’ theorem for measurable colorings’, Forum Math. Sigma 4 (2016),16–23.Google Scholar | DOI

[DPT15] Di Prisco, C. A. and Todorčević, S., ‘Basis problems for Borel graphs’, Zb. Rad. (Beogr.), Selected Topics in Combinatorial Analysis 17(25) (2015), 33–51.Google Scholar

[Ele18] Elek, G., ‘Qualitative graph limit theory. Cantor dynamical systems and constant-time distributed algorithms’, Preprint, 2018, .Google Scholar | arXiv

[EL75] Erdős, P. and Lovász, L.. ‘Problems and results on 3-chromatic hypergraphs and some related questions‘, in Infinite and Finite Sets (To Paul Erdős on His 60th Birthday) vol. II (A. Hajnal, R. Rado, V. T. Sós, eds, North-Holland Pub. Co., Amsterdam, 1975), 609–627.Google Scholar

[FMW92] Feng, Q., Magidor, M. and Woodin, H., ‘Universally Baire sets of reals’, in Set Theory of the Continuum, Mathematical Sciences Research Institute Publications (Springer Nature, Switzerland, 1992), 203–242.Google Scholar

[GP73] Galvin, F. and Prikry, K., ‘Borel sets and Ramsey’s theorem’, J. Symb. Log. 38(2) (1973), 193–198.Google Scholar | DOI

[GR21a] Grebík, J. and Rozhoň, V., ‘Classification of local problems on paths from the perspective of descriptive combinatorics’, Preprint, 2021, .Google Scholar | arXiv | DOI

[GR21b] Grebík, J. and Rozhoň, V., ‘Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics’, Preprint, 2021, .Google Scholar | arXiv

[HLS14] Hatami, H., Lovász, L. and Szegedy, B., ‘Limits of locally-globally convergent graph sequences’, Geom. Funct. Anal. 24(1) (2014), 269–296.Google Scholar | DOI

[HSW17] Holroyd, A. E., Schramm, O. and Wilson, D. B., ‘Finitary coloring’, Ann. Probab. 45(5) (2017), 2867–2898.Google Scholar | DOI

[JKL02] Jackson, S., Kechris, A. S. and Louveau, A., ‘Countable Borel equivalence relations’, J. Math. Logic 2(1) (2002), 1–80.Google Scholar | DOI

[Kec78] Kechris, A. S., ‘Forcing in analysis’, in Higher Set Theory, Lecture Notes in Mathematics (Springer, Berlin, 1978), 277–302.Google Scholar

[Kec95] Kechris, A. S., ‘Classical descriptive set theory’, in Graduate Texts in Mathematics volume 156 (Springer-Verlag, New York, 1995), i–404.Google Scholar

[Kho12] Khomskii, Y. D., ‘Regularity properties and definability in the real number continuum: Idealized forcing, polarized partitions, Hausdorff gaps and mad families in the projective hierarchy’, ILLC (2012).Google Scholar

[KM04] Kechris, A. S. and Miller, B. D., ‘Topics in orbit equivalence’, in Lecture Notes in Mathematics volume 1852 (Springer-Verlag, Berlin, 2004), N2–135.Google Scholar

[KM20] Kechris, A. S. and Marks, A. S., ‘Descriptive graph combinatorics’, https://www.math.ucla.edu/~marks/papers/combinatorics16.pdf, 2020.Google Scholar

[KST99] Kechris, A. S., Solecki, S. and Todorčević, S., ‘Borel chromatic numbers’, Adv. Math. 141(1) (1999), 1–44.Google Scholar | DOI

[Mar] Marks, A. S., ‘A short proof that an acyclic -regular Borel graph may have Borel chromatic number ’, https://www.math.ucla.edu/~marks/notes/003-short_coloring.pdf, (2013).Google Scholar

[Mar75] Martin, D. A., ‘Borel determinacy’, Ann. of Math. (2) 102(2) (1975), 363–371.Google Scholar | DOI

[Mar16] Marks, A. S., ‘A determinacy approach to Borel combinatorics’, J. Amer. Math. Soc. 29(2) (2016), 579–600.Google Scholar | DOI

[Mos09] Moschovakis, Y. N., ‘Descriptive set theory’, in Mathematical Surveys and Monographs volume 155, second edn (American Mathematical Society, Providence, RI, 2009), 1–502.Google Scholar

[Pik21] Pikhurko, O., ‘Borel combinatorics of locally finite graphs’, Preprint, 2021, .Google Scholar | arXiv | DOI

[Sab12] Sabok, M., ‘Complexity of Ramsey null sets’, Adv. Math. 230(3) (2012), 1184–1195.Google Scholar | DOI

[Shi19] Shitov, Y., ‘Counterexamples to Hedetniemi’s conjecture’, Ann. of Math. (2) 190(2) (2019), 663–667.Google Scholar | DOI

[STD16] Seward, B. and Tucker-Drob, R. D., ‘Borel structurability on the 2-shift of a countable group’, Ann. Pure Appl. Log. 167(1) (2016), 1–21.Google Scholar | DOI

[Tod10] Todorcevic, S., ‘Introduction to Ramsey spaces’, in Annals of Mathematics Studies volume 174 (Princeton University Press, Princeton, NJ, 2010), v–287.Google Scholar

[TV21] Todorčević, S. and Vidnyánszky, Z., ‘A complexity problem for Borel graphs’, Invent. Math. 226 (2021), 225–249.Google Scholar | DOI

[TZ19] Tardif, C. and Zhu, X., ‘A note on Hedetniemi’s conjecture, Stahl’s conjecture and the Poljak-Rödl function’, Preprint, 2019, .Google Scholar | arXiv | DOI

[Zhu21] Zhu, X., ‘Note on Hedetniemi’s conjecture and the Poljak-Rödl function’, in 2019-20 MATRIX Annals, MATRIX Book Series vol. 4 (Springer, Cham, 2021), 499–511.Google Scholar