Skip to Main content Skip to Navigation
Journal articles

Iterated Chromatic Subdivisions are Collapsible

Abstract : 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.
Document type :
Journal articles
Complete list of metadatas
Contributor : Bruno Savelli <>
Submitted on : Monday, June 25, 2018 - 3:43:49 PM
Last modification on : Friday, March 27, 2020 - 4:04:39 AM



Eric Goubault, Samuel Mimram, Christine Tasson. Iterated Chromatic Subdivisions are Collapsible. Applied Categorical Structures, Springer Verlag (Germany), 2015, 23, pp.777 - 818. ⟨10.1007/s10485-014-9383-6⟩. ⟨cea-01822918⟩



Record views