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 f...

Full description

Saved in:
Bibliographic Details
Published in:Applied categorical structures 2015-12, Vol.23 (6), p.777-818
Main Authors: Goubault, Éric, Mimram, Samuel, Tasson, Christine
Format: Article
Language:English
Subjects:
Computer Science
Convex and Discrete Geometry
Geometry
Mathematical Logic and Foundations
Mathematics
Mathematics and Statistics
Systems and Control
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0927-2852
1572-9095
DOI:10.1007/s10485-014-9383-6