Iterated Chromatic Subdivisions are Collapsible - CEA - Commissariat à l’énergie atomique et aux énergies alternatives Access content directly
Journal Articles Applied Categorical Structures Year : 2015

Iterated Chromatic Subdivisions are Collapsible


The standard chromatic subdivision of the standard simplex is a combinatorial algebraic construction, which was introduced in theoretical distributed computing, motivated by the study of the view complex of layered immediate snapshot protocols. A most important property of this construction is the fact that the iterated subdivision of the standard simplex is contractible, implying impossibility results in fault-tolerant distributed computing. Here, we prove this result in a purely combinatorial way, by showing that it is collapsible, studying along the way fundamental combinatorial structures present in the category of colored simplicial complexes.
Not file

Dates and versions

cea-01822918 , version 1 (25-06-2018)



Eric Goubault, Samuel Mimram, Christine Tasson. Iterated Chromatic Subdivisions are Collapsible. Applied Categorical Structures, 2015, 23, pp.777 - 818. ⟨10.1007/s10485-014-9383-6⟩. ⟨cea-01822918⟩
48 View
0 Download



Gmail Facebook Twitter LinkedIn More