Borel versions of the Local Lemma and LOCAL algorithms for graphs of finite asymptotic separation index
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929746400509952 |
|---|---|
| author | Bernshteyn, Anton Weilacher, Felix |
| author_facet | Bernshteyn, Anton Weilacher, Felix |
| contents | Asymptotic separation index is a parameter that measures how easily a Borel graph can be approximated by its subgraphs with finite components. In contrast to the more classical notion of hyperfiniteness, asymptotic separation index is well-suited for combinatorial applications in the Borel setting. The main result of this paper is a Borel version of the Lovász Local Lemma -- a powerful general-purpose tool in probabilistic combinatorics -- under a finite asymptotic separation index assumption. As a consequence, we show that locally checkable labeling problems that are solvable by efficient randomized distributed algorithms admit Borel solutions on bounded degree Borel graphs with finite asymptotic separation index. From this we derive a number of corollaries, for example a Borel version of Brooks's theorem for graphs with finite asymptotic separation index. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_14941 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Borel versions of the Local Lemma and LOCAL algorithms for graphs of finite asymptotic separation index Bernshteyn, Anton Weilacher, Felix Logic Distributed, Parallel, and Cluster Computing Combinatorics Asymptotic separation index is a parameter that measures how easily a Borel graph can be approximated by its subgraphs with finite components. In contrast to the more classical notion of hyperfiniteness, asymptotic separation index is well-suited for combinatorial applications in the Borel setting. The main result of this paper is a Borel version of the Lovász Local Lemma -- a powerful general-purpose tool in probabilistic combinatorics -- under a finite asymptotic separation index assumption. As a consequence, we show that locally checkable labeling problems that are solvable by efficient randomized distributed algorithms admit Borel solutions on bounded degree Borel graphs with finite asymptotic separation index. From this we derive a number of corollaries, for example a Borel version of Brooks's theorem for graphs with finite asymptotic separation index. |
| title | Borel versions of the Local Lemma and LOCAL algorithms for graphs of finite asymptotic separation index |
| topic | Logic Distributed, Parallel, and Cluster Computing Combinatorics |
| url | https://arxiv.org/abs/2308.14941 |