Iterated Chromatic Subdivisions are Collapsible - Archive ouverte HAL Access content directly
Journal Articles Applied Categorical Structures Year : 2015

Iterated Chromatic Subdivisions are Collapsible

(1) , (1) , (2)
1
2

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.
Not file

Dates and versions

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

Identifiers

Cite

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⟩
43 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More