Document Open Access Logo

Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics

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

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.29.pdf
  • Filesize: 1.27 MB
  • 26 pages

Document Identifiers

Author Details

Sebastian Brandt
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Yi-Jun Chang
  • National University of Singapore, Singapore
Jan Grebík
  • University of Warwick, Coventry, UK
Christoph Grunau
  • ETH Zürich, Switzerland
Václav Rozhoň
  • ETH Zürich, Switzerland
Zoltán Vidnyánszky
  • California Institute of Technology, Pasadena, CA, USA

Funding

  • Chang, Yi-Jun: Supported by Dr. Max Rössler, by the Walter Haefner Foundation, and by the ETH Zürich Foundation.
  • Grebík, Jan: Supported by Leverhulme Research Project Grant RPG-2018-424.
  • Grunau, Christoph: Supported by the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No. 853109).
  • Rozhoň, Václav: Supported by the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No. 853109).
  • Vidnyánszky, Zoltán: Partially supported by the National Research, Development and Innovation Office - NKFIH, grants no. 113047, no. 129211 and FWF Grant M2779.

Acknowledgements

We would like to thank Anton Bernshteyn, Endre Csóka, Mohsen Ghaffari, Jan Hladký, Steve Jackson, Alexander Kechris, Edward Krohne, Oleg Pikhurko, Brandon Seward, Jukka Suomela, and Yufan Zheng for insightful discussions. Yi-Jun Chang would like to thank Yufan Zheng for a discussion about homomorphism LCL problems, in particular for suggesting potentially hard instances.

Cite As Get BibTex

Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhoň, and Zoltán Vidnyánszky. Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 29:1-29:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.29

Abstract

We study connections between three different fields: distributed local algorithms, finitary factors of iid processes, and descriptive combinatorics. We focus on two central questions: Can we apply techniques from one of the areas to obtain results in another? Can we show that complexity classes coming from different areas contain precisely the same problems? We give an affirmative answer to both questions in the context of local problems on regular trees:  
1) We extend the Borel determinacy technique of Marks [Marks - J. Am. Math. Soc. 2016] coming from descriptive combinatorics and adapt it to the area of distributed computing, thereby obtaining a more generally applicable lower bound technique in descriptive combinatorics and an entirely new lower bound technique for distributed algorithms. Using our new technique, we prove deterministic distributed Ω(log n)-round lower bounds for problems from a natural class of homomorphism problems. Interestingly, these lower bounds seem beyond the current reach of the powerful round elimination technique [Brandt - PODC 2019] responsible for all substantial locality lower bounds of the last years. Our key technical ingredient is a novel ID graph technique that we expect to be of independent interest; in fact, it has already played an important role in a new lower bound for the Lovász local lemma in the Local Computation Algorithms model from sequential computing [Brandt, Grunau, Rozhoň - PODC 2021]. 
2) We prove that a local problem admits a Baire measurable coloring if and only if it admits a local algorithm with local complexity O(log n), extending the classification of Baire measurable colorings of Bernshteyn [Bernshteyn - personal communication]. A key ingredient of the proof is a new and simple characterization of local problems that can be solved in O(log n) rounds. We complement this result by showing separations between complexity classes from distributed computing, finitary factors, and descriptive combinatorics. Most notably, the class of problems that allow a distributed algorithm with sublogarithmic randomized local complexity is incomparable with the class of problems with a Borel solution.  We hope that our treatment will help to view all three perspectives as part of a common theory of locality, in which we follow the insightful paper of [Bernshteyn - arXiv 2004.04905].

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Distributed Algorithms
  • Descriptive Combinatorics

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Omer Angel, Itai Benjamini, Ori Gurel-Gurevich, Tom Meyerovitch, and Ron Peled. Stationary map coloring. Ann. Inst. Henri Poincaré Probab. Stat., 48(2):327-342, 2012. Google Scholar
  2. Ágnes Backhausz, Balázs Gerencsér, and Viktor Harangi. Entropy inequalities for factors of IID. Groups Geom. Dyn., 13(2):389-414, 2019. URL: https://doi.org/10.4171/GGD/492.
  3. Ágnes Backhausz and Balázs Szegedy. On large girth regular graphs and random processes on trees. Random Structures Algorithms, 53(3):389-416, 2018. Google Scholar
  4. Ágnes Backhausz, Balázs Szegedy, and Bálint Virág. Ramanujan graphings and correlation decay in local algorithms. Random Structures Algorithms, 47(3):424-435, 2015. URL: https://doi.org/10.1002/rsa.20562.
  5. Ágnes Backhausz and Bálint Virag. Spectral measures of factor of i.i.d. processes on vertex-transitive graphs. Ann. Inst. Henri Poincaré Probab. Stat., 53(4):2260-2278, 2017. Google Scholar
  6. Ágnes Backhausz, Balázs Gerencsér, Viktor Harangi, and Máté Vizer. Correlation bounds for distant parts of factor of iid processes. Combin. Probab. Comput., 27(1):1-20, 2018. Google Scholar
  7. K. Ball. Poisson thinning by monotone factors. Electron. Comm. Probab., 10:60-69, 2005. Google Scholar
  8. Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Classification of distributed binary labeling problems. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing (DISC), volume 179 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1-17:17, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.DISC.2020.17.
  9. Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. Lower bounds for maximal matchings and maximal independent sets. In Proceedings of the IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 481-497, 2019. URL: https://doi.org/10.1109/FOCS.2019.00037.
  10. Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. Improved distributed lower bounds for mis and bounded (out-)degree dominating sets in trees. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC), 2021. Google Scholar
  11. Alkida Balliu, Sebastian Brandt, and Dennis Olivetti. Distributed lower bounds for ruling sets. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 365-376, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00042.
  12. Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela, and Aleksandr Tereshchenko. Locally checkable problems in rooted trees. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, 2021. Google Scholar
  13. Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. Almost global problems in the local model. Distributed Computing, pages 1-23, 2020. Google Scholar
  14. Alkida Balliu, Juho Hirvonen, Janne H Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela. New classes of distributed time complexity. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1307-1318, 2018. Google Scholar
  15. Alkida Balliu, Juho Hirvonen, Dennis Olivetti, and Jukka Suomela. Hardness of minimal symmetry breaking in distributed computing. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 369-378, 2019. Google Scholar
  16. Ferenc Bencs, Aranka Hrušková, and László Márton Tóth. Factor of iid schreier decoration of transitive graphs. arXiv:2101.12577, 2021. Google Scholar
  17. Itai Benjamini and Oded Schramm. Recurrence of distributional limits of finite planar graphs. In Selected Works of Oded Schramm, pages 533-545. Springer, 2011. Google Scholar
  18. Anton Bernshteyn. Work in progress. Google Scholar
  19. Anton Bernshteyn. Distributed algorithms, the Lovász Local Lemma, and descriptive combinatorics. arXiv preprint arXiv:2004.04905, 2020. Google Scholar
  20. Anton Bernshteyn. A fast distributed algorithm for (Δ+1)-edge-coloring. preprint, 2020. Google Scholar
  21. Béla Bollobás. The independence ratio of regular graphs. Proc. Amer. Math. Soc., 83(2):433-436, 1981. URL: https://doi.org/10.2307/2043545.
  22. Lewis Bowen. The ergodic theory of free group actions: entropy and the f -invariant. Groups Geom. Dyn., 4(3):419-432, 2010. Google Scholar
  23. Lewis Bowen. A measure-conjugacy invariant for free group actions. Ann. of Math., 171(2):1387-1400, 2010. Google Scholar
  24. Sebastian Brandt. An automatic speedup theorem for distributed problems. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 379-388, 2019. URL: https://doi.org/10.1145/3293611.3331611.
  25. Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Vaclav Rozhoň, and Zoltán Vidnyánszky. Local problems on trees from the perspectives of distributed algorithms, finitary factors, and descriptive combinatorics. arXiv preprint arXiv:2106.02066, 2021. A short version will be presented at the 13th Innovations in Theoretical Computer Science conference (ITCS 2022). URL: http://arxiv.org/abs/2106.02066.
  26. Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhoň, and Zoltán Vidnyánszky. On homomorphism graphs, 2021. URL: http://arxiv.org/abs/2111.03683.
  27. Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto. A lower bound for the distributed Lovász local lemma. In Proc. 48th ACM Symp. on Theory of Computing (STOC), pages 479-488, 2016. Google Scholar
  28. Sebastian Brandt, Christoph Grunau, and Václav Rozhoň. Randomized local computation complexity of the Lovasz local lemma. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, 2021. Google Scholar
  29. Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R.J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, and Przemysław Uznański. LCL problems on grids. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 101-110, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3087801.3087833.
  30. Sebastian Brandt and Dennis Olivetti. Truly tight-in-Δ bounds for bipartite maximal matching and variants. In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC '20, pages 69-78, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3382734.3405745.
  31. Yi-Jun Chang. The Complexity Landscape of Distributed Locally Checkable Problems on Trees. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing (DISC 2020), volume 179 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1-18:17, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.DISC.2020.18.
  32. Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto. Distributed edge coloring and a special case of the constructive Lovász local lemma. ACM Trans. Algorithms, 16(1):8:1-8:51, 2020. URL: https://doi.org/10.1145/3365004.
  33. Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the local model. SIAM Journal on Computing, 48(1):122-143, 2019. Google Scholar
  34. Yi-Jun Chang and Seth Pettie. A time hierarchy theorem for the local model. SIAM Journal on Computing, 48(1):33-69, 2019. Google Scholar
  35. Yi-Jun Chang, Jan Studený, and Jukka Suomela. Distributed graph problems through an automata-theoretic lens. arXiv:2002.07659, 2020. Google Scholar
  36. Sourav Chatterjee, Ron Peled, Yuval Peres, and Dan Romik. Gravitational allocation to poisson points. Ann. of Math., 172(1):617-671, 2010. Google Scholar
  37. Clinton T. Conley, Steve Jackson, Andrew S. Marks, Brandon Seward, and Robin Tucker-Drob. Borel asymptotic dimension and hyperfinite equivalence relations. arXiv:2009.06721, 2020. Google Scholar
  38. Clinton T. Conley, Andrew S. Marks, and Robin D. Tucker-Drob. Brooks' theorem for measurable colorings. Forum Math. Sigma, e16(4):23pp, 2016. Google Scholar
  39. Clinton T. Conley, Andrew S. Marks, and Spencer T. Unger. Measurable realizations of abstract systems of congruences. In Forum of Mathematics, Sigma, volume 8. Cambridge University Press, 2020. Google Scholar
  40. Clinton T. Conley and Benjamin D. Miller. A bound on measurable chromatic numbers of locally finite Borel graphs. Math. Res. Lett., 23(6):1633-1644, 2016. URL: https://doi.org/10.4310/MRL.2016.v23.n6.a3.
  41. Clinton T. Conley and Benjamin D. Miller. Measure reducibility of countable Borel equivalence relations. Ann. of Math. (2), 185(2):347-402, 2017. URL: https://doi.org/10.4007/annals.2017.185.2.1.
  42. Endre Csóka, Balázs Gerencsér, Viktor Harangi, and Bálint Virág. Invariant gaussian processes and independent sets on regular graphs of large girth. Random Structures & Algorithms, 47(2):284-303, 2015. Google Scholar
  43. Endre Csóka, Łukasz Grabowski, András Máthé, Oleg Pikhurko, and Konstantinos Tyros. Borel version of the Local Lemma. arXiv:1605.04877, 2017. Google Scholar
  44. Randall Dougherty and Matthew Foreman. Banach-Tarski paradox using pieces with the property of Baire. Proc. Nat. Acad. Sci. U.S.A., 89(22):10726-10728, 1992. URL: https://doi.org/10.1073/pnas.89.22.10726.
  45. Randall Dougherty, Steve Jackson, and Alexander S. Kechris. The structure of hyperfinite Borel equivalence relations. Trans. Amer. Math. Soc., 341(1):193-225, 1994. URL: https://doi.org/10.2307/2154620.
  46. Gábor Elek and Gábor Lippner. Borel oracles. An analytical approach to constant-time algorithms. Proc. Amer. Math. Soc., 138(8):2939-2947, 2010. URL: https://doi.org/10.1090/S0002-9939-10-10291-3.
  47. Klaus-Tycho Foerster, Janne H. Korhonen, Ami Paz, Joel Rybicki, Stefan Schmid, and Jukka Suomela. Work in progress. Google Scholar
  48. Damien Gaboriau. Coût des relations d'équivalence et des groupes. Invent. Math., 139(1):41-98, 2000. URL: https://doi.org/10.1007/s002229900019.
  49. Damien Gaboriau and Russell Lyons. A measurable-group-theoretic solution to von neumann’s problem. Invent. Math., 177(3):533-540, 2009. Google Scholar
  50. David Gamarnik and Madhu Sudan. Limits of local algorithms over sparse random graphs. Proceedings of the 5-th Innovations in Theoretical Computer Science conference, ACM Special Interest Group on Algorithms and Computation Theory, 2014. Google Scholar
  51. Su Gao and Steve Jackson. Countable abelian group actions and hyperfinite equivalence relations. Inventiones Math., 201(1):309-383, 2015. Google Scholar
  52. Su Gao, Steve Jackson, Edward Krohne, and Brandon Seward. Forcing constructions and countable borel equivalence relations. arXiv:1503.07822, 2015. Google Scholar
  53. Mika Göös, Juho Hirvonen, and Jukka Suomela. Linear-in-Δ lower bounds in the LOCAL model. In Proc. 33rd ACM Symp. on Principles of Distributed Computing (PODC), pages 86-95, 2014. Google Scholar
  54. Łukasz Grabowski, András Máthé, and Oleg Pikhurko. Measurable circle squaring. Ann. of Math. (2), 185(2):671-710, 2017. URL: https://doi.org/10.4007/annals.2017.185.2.6.
  55. Jan Grebík and Václav Rozhoň. Classification of local problems on paths from the perspective of descriptive combinatorics. arXiv preprint arXiv:2103.14112, 2021. URL: http://arxiv.org/abs/2103.14112.
  56. Jan Grebík and Václav Rozhoň. Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics. arXiv preprint arXiv:2103.08394, 2021. URL: http://arxiv.org/abs/2103.08394.
  57. Ori Gurel-Gurevich and Ron Peled. Poisson thickening. Israel J. Math., 196(1):215-234, 2013. Google Scholar
  58. Viktor. Harangi and Bálint Virág. Independence ratio and random eigenvectors in transitive graphs. Ann. Probab., 43(5):2810-2840, 2015. Google Scholar
  59. Hamed Hatami, László Lovász, and Balázs Szegedy. Limits of locally-globally convergent graph sequences. Geom. Funct. Anal., 24(1):269-296, 2014. URL: https://doi.org/10.1007/s00039-014-0258-7.
  60. Greg Hjorth and Alexander S. Kechris. Borel equivalence relations and classifications of countable models. Annals of pure and applied logic, 82(3):221-272, 1996. Google Scholar
  61. Alexander E. Holroyd. Geometric properties of poisson matchings. Probab. Theory Related Fields, 150(3-4):511-527, 2011. Google Scholar
  62. Alexander E. Holroyd. One-dependent coloring by finitary factors. Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, 53(2):753-765, 2017. URL: https://doi.org/10.1214/15-AIHP735.
  63. Alexander E. Holroyd, Russel Lyons, and Terry Soo. Poisson splitting by factors. Ann. Probab., 39(5):1938-1982, 2011. Google Scholar
  64. Alexander E. Holroyd, Robin Pemantle, Y. Peres, and Oded Schramm. Poisson matching. Ann. Inst. Henri Poincaré Probab. Stat., 45(1):266-287, 2009. Google Scholar
  65. Alexander E. Holroyd and Yuval Peres. Trees and matchings from point processes. Electron. Comm. Probab., 8:17-27, 2003. Google Scholar
  66. Alexander E. Holroyd, Oded Schramm, and David B. Wilson. Finitary coloring. Ann. Probab., 45(5):2867-2898, 2017. Google Scholar
  67. Carlos Hoppen and Nicholas Wormald. Local algorithms, regular graphs of large girth, and random regular graphs. Combinatorica, 38(3):619-664, 2018. Google Scholar
  68. Steve Jackson, Alexander S. Kechris, and Alain Louveau. Countable Borel equivalence relations. J. Math. Logic, 2(01):1-80, 2002. Google Scholar
  69. Alexander S. Kechris. Classical descriptive set theory, volume 156 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995. URL: https://doi.org/10.1007/978-1-4612-4190-4.
  70. Alexander S. Kechris and Andrew S. Marks. Descriptive graph combinatorics. http://www.math.caltech.edu/~kechris/papers/combinatorics20book.pdf, 2020.
  71. Alexander S. Kechris, Sławomir Solecki, and Stevo Todorčević. Borel chromatic numbers. Adv. Math., 141(1):1-44, 1999. Google Scholar
  72. Amos Korman, Jean-Sébastien Sereni, and Laurent Viennot. Toward more localized local algorithms: removing assumptions concerning global knowledge. Distributed Computing, 26(5-6):289-308, September 2012. URL: https://doi.org/10.1007/s00446-012-0174-8.
  73. Gábor Kun. Expanders have a spanning lipschitz subgraph with large girth. preprint, 2013. Google Scholar
  74. Miklós Laczkovich. Equidecomposability and discrepancy; a solution of Tarski’s circle-squaring problem. J. Reine Angew. Math., 404:77-117, 1990. URL: https://doi.org/10.1515/crll.1990.404.77.
  75. Nati Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. Google Scholar
  76. Russell Lyons. Factors of iid on trees. Combin. Probab. Comput., 26(2):285-300, 2017. Google Scholar
  77. Russell Lyons and Fedor Nazarov. Perfect matchings as iid factors on non-amenable groups. European Journal of Combinatorics, 32(7):1115-1125, 2011. Google Scholar
  78. Andrew Marks and Spencer Unger. Baire measurable paradoxical decompositions via matchings. Advances in Mathematics, 289:397-410, 2016. Google Scholar
  79. Andrew S. Marks. A short proof that an acyclic n-regular Borel graph may have borel chromatic number n+1. Google Scholar
  80. Andrew S. Marks. A determinacy approach to Borel combinatorics. J. Amer. Math. Soc., 29(2):579-600, 2016. Google Scholar
  81. Andrew S. Marks and Spencer T. Unger. Borel circle squaring. Ann. of Math. (2), 186(2):581-605, 2017. URL: https://doi.org/10.4007/annals.2017.186.2.4.
  82. Donald A. Martin. Borel determinacy. Ann. of Math. (2), 102(2):363-371, 1975. URL: https://doi.org/10.2307/1971035.
  83. Péter Mester. A factor of i.i.d with uniform marginals and infinite clusters spanned by equal labels. preprint, 2011. Google Scholar
  84. Gary L. Miller and John H. Reif. Parallel tree contraction-Part I: fundamentals. Advances in Computing Research, 5:47-72, 1989. Google Scholar
  85. Moni Naor and Larry Stockmeyer. What can be computed locally? SIAM Journal on Computing, 24(6):1259-1277, 1995. Google Scholar
  86. Huy N. Nguyen and Krzysztof Onak. Constant-time approximation algorithms via local improvements. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 327-336, 2008. URL: https://doi.org/10.1109/FOCS.2008.81.
  87. Oleg Pikhurko. Borel combinatorics of locally finite graphs. arXiv preprint arXiv:2009.09113, 2021. URL: http://arxiv.org/abs/2009.09113.
  88. Mustazee Rahman. Factor of iid percolation on trees. SIAM J. Discrete Math., 30(4):2217-2242, 2016. Google Scholar
  89. Mustazee Rahman and Bálint Virág. Local algorithms for independent sets are half-optimal. Ann. Probab., 45(3):1543-1577, 2017. Google Scholar
  90. Christian Schmidt, Nils-Eric Guenther, and Lenka Zdeborová. Circular coloring of random graphs: statistical physics investigation. Journal of Statistical Mechanics: Theory and Experiment, 2016(8):083303, 2016. Google Scholar
  91. Yinon Spinka. Finitely dependent processes are finitary. Ann. Probab., 48(4):2088-2117, 2020. Google Scholar
  92. Ádám Timár. Tree and grid factors for general point processes. Electron. Comm. Probab., 9(53-59), 2004. Google Scholar
  93. Ádám Timár. Invariant colorings of random planar maps. Ergodic Theory Dynam. Systems, 31(2):549-562, 2011. Google Scholar
  94. Stevo Todorčević and Zoltán Vidnyánszky. A complexity problem for Borel graphs. Invent. Math., 226:225-249, 2021. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact