Geodesic
From descriptive to distributed
Zbornik radova, Tome 22 (2025) no. 30, p. 261

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

DOI

In the past couple of years a rich connection has been found between the fields of \emph{descriptive set theory} and \emph{distributed computing}. Frequently, and less surprisingly, finitary algorithms can be adopted to the infinite setting, resulting in theorems about infinite, definable graphs. In this survey, we take a different perspective and illustrate how results and ideas from descriptive set theory provide new insights and techniques to the theory of distributed computing. We focus on the two classical topics from graph theory, \emph{vertex} and \emph{edge colorings}. After summarizing the up-to-date results from both areas, we discuss the adaptation of Marks' games method to the LOCAL model of distributed computing and the development of the multi-step Vizing's chain technique, which led to the construction of the first non-trivial distributed algorithms for Vizing colorings. We provide a list of related open problems to complement our discussion. Finally, we describe an efficient deterministic distributed algorithm for Brooks coloring on graphs of subexponential growth.
DOI : 10.64191/zr24040410108
Classification : 03E15, 68W15, 28A05, 05C15
Keywords: descriptive, Borel combinatorics, LOCAL model 
Jan Grebík; Zoltán Vidnyánszky. From descriptive to distributed. Zbornik radova, Tome 22 (2025) no. 30, p. 261 . doi: 10.64191/zr24040410108
@article{10_64191_zr24040410108,
     author = {Jan Greb{\'\i}k and Zolt\'an Vidny\'anszky},
     title = {From descriptive to distributed},
     journal = {Zbornik radova},
     pages = {261 },
     year = {2025},
     volume = {22},
     number = {30},
     doi = {10.64191/zr24040410108},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.64191/zr24040410108/}
}
TY  - JOUR
AU  - Jan Grebík
AU  - Zoltán Vidnyánszky
TI  - From descriptive to distributed
JO  - Zbornik radova
PY  - 2025
SP  - 261 
VL  - 22
IS  - 30
UR  - http://geodesic.mathdoc.fr/articles/10.64191/zr24040410108/
DO  - 10.64191/zr24040410108
LA  - en
ID  - 10_64191_zr24040410108
ER  - 
%0 Journal Article
%A Jan Grebík
%A Zoltán Vidnyánszky
%T From descriptive to distributed
%J Zbornik radova
%D 2025
%P 261 
%V 22
%N 30
%U http://geodesic.mathdoc.fr/articles/10.64191/zr24040410108/
%R 10.64191/zr24040410108
%G en
%F 10_64191_zr24040410108

Cité par Sources :