Iterated chromatic subdivisions are collapsible

Eric Goubault (1) , Samuel Mimram (1) , Christine Tasson (2)

1 DILS (CEA, LIST) - Département Ingénierie Logiciels et Systèmes
2 PPS - Preuves, Programmes et Systèmes

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

Mots clés: simplicial complex; Standard chromatic subdivision; Collapsibility; Iterated subdivision

Domaines: Informatique [cs]; Systèmes et contrôle [cs.SY]

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⟩