Homology, Homotopy and Applications

Volume 17 (2015)

Number 1

Topology of the view complex

Pages: 307 – 319

DOI: https://dx.doi.org/10.4310/HHA.2015.v17.n1.a15

Author

Dmitry N. Kozlov (Department of Mathematics, University of Bremen, Germany)

Abstract

In this paper we consider a family of simplicial complexes, which we call the view complexes. Our choice of objects of study is motivated by theoretical distributed computing, since the view complex is a key simplicial construction used for protocol complexes in the snapshot computational model. We show that the view complex $\textrm{View}^n$ can be collapsed to the well-known complex $\chi(\Delta^n)$, called standard chromatic subdivision of a simplex, and that $\chi(\Delta^n)$ is itself collapsible. Furthermore, we show that the collapses can be performed simultaneously in entire orbits of the natural symmetric group action. Our results yield a purely combinatorial and constructive understanding of the topology of view complexes, at the same time as they enhance our knowledge about the standard chromatic subdivision of a simplex.

Keywords

collapses, distributed computing, combinatorial algebraic topology, immediate snapshot, read-write protocols

2010 Mathematics Subject Classification

57Q05, 68Q85

Published 18 May 2015