EUVIMEDEUVIMED entdecken
Crossref

Structure theory of flip graphs with applications to Weak Symmetry Breaking

Dmitry N. Kozlov

Journal of Applied and Computational Topology · 2017

DOI: 10.1007/s41468-017-0001-1 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Applied and Computational Topology, 2017. Verfasst von Dmitry N. Kozlov. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 21 Literaturangaben. Gefördert von: Deutsche Forschungsgemeinschaft.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

This paper is devoted to advancing the theoretical understanding of the iterated immediate snapshot (IIS) complexity of the Weak Symmetry Breaking task (WSB). Our rather unexpected main theorem states that there exist infinitely many values of n, such that WSB for n processes is solvable by a certain explicitly constructed 3-round IIS protocol. In particular, the minimal number of rounds, which an IIS protocol needs in order to solve the WSB task, does not go to infinity, when the number of processes goes to infinity. Our methods can also be used to generate such values of n. We phrase our proofs in combinatorial language, while avoiding using topology. To this end, we study a certain class of graphs, which we call flip graphs. These graphs encode adjacency structure in certain subcomplexes of iterated standard chromatic subdivisions of a simplex. While keeping the geometric background in mind for an additional intuition, we develop the structure theory of matchings in flip graphs in a purely combinatorial way. Our bound for the IIS complexity is then a corollary of this general theory. As an afterthought of our result, we suggest to change the overall paradigm. Specifically, we think, that the bounds on the IIS complexity of solving WSB for n processes should be formulated in terms of the size of the solutions of the associated Diophantine equation, rather than in terms of the value n itself.

Förderung

  • Deutsche Forschungsgemeinschaft

Zitieren

APA

Kozlov, D. N. (2017). Structure theory of flip graphs with applications to Weak Symmetry Breaking. Journal of Applied and Computational Topology. https://doi.org/10.1007/s41468-017-0001-1

Vancouver

Kozlov DN. Structure theory of flip graphs with applications to Weak Symmetry Breaking. Journal of Applied and Computational Topology. 2017. doi:10.1007/s41468-017-0001-1

BibTeX
@article{Kozlov2017,
  author = {Kozlov, Dmitry N.},
  title = {Structure theory of flip graphs with applications to Weak Symmetry Breaking},
  journal = {Journal of Applied and Computational Topology},
  year = {2017},
  doi = {10.1007/s41468-017-0001-1}
}
Kostenlos starten →