Descriptive combinatorics and distributed algorithms
| Title: | Descriptive combinatorics and distributed algorithms |
| Author(s): | Särkijärvi, Joona |
| Contributor: | University of Helsinki, Faculty of Science |
| Degree program: | Master 's Programme in Mathematics and Statistics |
| Specialisation: | Mathematics and applied mathematics |
| Language: | English |
| Acceptance year: | 2023 |
| Abstract: |
Sekä deskriptiivisessä kombinatoriikassa että hajautetussa laskennassa tutkitaan verkko-ongelmia, joissa esiintyy paikallisia rajoituksia. Kuten Anton Bernshteyn osoitti uraauurtavassa artikkelissaan vuonna 2020, tämä yhteys ei ole pelkästään pinnallinen. Tämä työ esittelee Bernshteynin tuloksia, joissa hän kehitti alojen välisiä yhteyksiä, sekä yhtenäisti ongelmien paikallisuuden teoriaa. Nämä tulokset yhtyvät jatkuvien dynaamisten järjestelmien teoriaan. Työssä osoitetaan, että tietynlaiset väritysongelmat ovat jatkuvasti ratkaistavissa avaruuden 2^Γ vapaassa osassa, jos ja vain jos on olemassa nopea LOCAL-algoritmi joka ratkaisee kyseenomaisen ongelman Γ:n Cayley-verkossa.
Lisäksi työssä esitellään Bernshteynin versio Lovászin lokaalista lemmasta. Kyseistä lemmaa käytetään jatkuvasti kombinatoriikan ja hajautetun laskennan tutkimuksessa, missä se tuottaa eksistenssituloksia. Tämä uusi LLL:n versio takaa näiden tulosten jatkuvuuden, mikäli tietyt topologiset ehdot täyttyvät.
Both descriptive combinatorics and distributed algorithms are interested in solving graph problems with certain local constraints. This connection is not just superficial, as Bernshteyn showed in his seminal 2020 paper. This thesis focuses on that connection by restating the results of Bernshteyn. This work shows that a common theory of locality connects these fields. We also restate the results that connect these findings to continuous dynamics, where they found that solving a colouring problem on the free part of the subshift 2^Γ is equivalent to there being a fast LOCAL algorithm solving this problem on finite sections of the Cayley graph of Γ.
We also restate the result on the continuous version of Lovász Local Lemma by Bernshteyn. The LLL is a powerful probabilistic tool used throughout combinatorics and distributed computing. They proved a version of the lemma that, under certain topological constraints, produces continuous solutions.
|
| Keyword(s): | Descriptive combinatorics Distributed computing LOCAL model Lovász Local Lemma |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
| Masters thesis final.pdf | 659.0Kb |
This item appears in the following Collection(s)
-
Faculty of Science [3866]