Iterated Chromatic Subdivisions are Collapsible

作者：Goubault Eric; Mimram Samuel^*; Tasson Christine

来源：Applied Categorical Structures, 2015, 23(6): 777-818.

DOI：10.1007/s10485-014-9383-6

• Abstract simplicial complex
• Standard chromatic subdivision
• Collapsibility
• Iterated subdivision

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.

• 出版日期2015-12
• 单位中国地震局