Iterated chromatic subdivisions are collapsible (Q891921): Difference between revisions

The paper continues the study of questions of algebraic topology related to the theory of distributive computing. An important construction in understanding the topology of the broad class of protocol complexes for \(n+1\) processes is the standard chromatic subdivision \(\chi(\Delta^n)\). Many results are deduced from the contractibility of the standard chromatic subdivision [\textit{D. Kozlov}, Homology Homotopy Appl. 14, No. 2, 197--209 (2012, Zbl 1259.68146)]. \textit{D. Kozlov} proved that \(\chi(\Delta^n)\) is collapsible [ibid. 17, No. 1, 307--319 (2015, Zbl 1227.55011)]. In the paper under review, this result is obtained independently. This result is proved in a purely combinatorial way by the study of the combinatorical constructions in the category of colored simplicial complexes. In particular, this method has led to the proof of collapsibility of the simplicial complex \(\chi^k(\Delta^I)\) obtained by the application the \(k\)-iterated barycentric subdivision functor to the standard \(I\)-simplicial complex, for all \(k\geq 1\) and finite \(I\subset \mathbb{N}\). A \textit{simplicial complex} is a pair \((\underline{K},K)\) consisting of a set \(\underline{K}\) of \textit{vertices}, together with a set \(K\) of finite subsets of \(\underline{K}\) called \textit{simplices}, and satisfying the following conditions: 1) \(K\) is non-empty; 2) for every \(x\in \underline{K}\), we have \(\{x\}\in K\); 3) if \(\sigma\in K\) and \(\tau\subseteq \sigma\), then \(\tau \in K\). In particular, \(\emptyset\in K\). A simplicial complex \((\underline{K},K)\) is shortly denoted by \(K\). A \textit{morphism \(f: K\to K'\) of simplicial complexes} consists of a function \(f: \underline{K}\to \underline{K'}\) such that \(f(\sigma)\in K'\) for every \(\sigma\in K\), and the restriction of \(f\) to \(\sigma\) is injective for every \(\sigma\in K\). The category of simplicial complexes is denoted by \({SC}\). Given a finite set \(I\), the standard \(I\)-simplicial complex \(\Delta^I\) is the complex with \(I\) as the set of vertices and all subsets of \(I\) as simplices. For \(n\in \{-1\}\cup \mathbb{N}\), \(\Delta^{[n]}\) is denoted by \(\Delta^n\). Given a simplicial complex \((\underline{K},K)\) and \(\sigma\subseteq \underline{K}\) with \(\sigma\not= \emptyset\), let \(K\setminus{\sigma}\) be the simplicial complex consisting of vertices \(\underline{K\setminus \sigma}\subseteq \underline{K}\) together with the set of simplices \(K\setminus{\sigma}= K\setminus \{\tau\in K | \sigma\subseteq \tau\}\). Suppose that \(K\) is a simplicial complex of finite dimension and \(\sigma, \tau \in K\) are two simplices. The simplex \(\tau\) is a \textit{free face} of \(\sigma\) when the following two conditions are satisfied: 1. \(\tau\subseteq\sigma\) and \(\tau\not= \sigma\), 2. \(\sigma\) is a maximal simplex of \(K\) and no other maximal simplex of \(K\) contains \(\tau\). For such a pair \((\tau,\sigma)\), the simplicial complex \(K\subseteq{\tau}\) is called a \textit{collapse step} of \(K\). If additionally we have \(\dim\tau= \dim\sigma-1\), then this is called an \textit{elementary} collapse step. A \textit{collapse} is a finite sequence of collapse steps. A simplicial complex that has a finite sequence of collapses to a point is called \textit{collapsible}, where a \textit{point} is a complex isomorphic to \(\Delta^0\). The equivalence relation on simplicial complexes generated by collapses is called \textit{simple homotopy}. In Section 3, the usual definition of the barycentric subdivision is adapted to the colored case. Let \(Graph\) be the category of graphs \(G=(V_G,E_G)\), with \(E_G\subseteq V_G\times V_G\), which are irreflexive in the sense of \((x,y)\in E_G\) implies \(x\not=y\). A morphism \(f: G\to H\) consists of a function \(f: V_G\to H_G\) such that for every \((x,y)\in E_G\), we have \((f(x),f(y))\in E_H\). The \textit{graph of elements} \({El}(K)\) of a simplicial complex \(K\) is the graph whose elements are the non-empty simplices of \(K\) and there is an edge \(\tau\to\sigma\) whenever \(\tau\subseteq\sigma\). This construction extends to a functor \({El}: {{SC}\to Graph}\). The \textit{nerve of a graph} \(G\) is the simplicial complex \(NG\) whose vertices are those of \(G\) and simplices are sets of elements \(\{x_1, \dots, x_n\}\) having an edge \(x_i\to x_j\) for any \(i\prec j\). This construction extends to a functor \(N: Graph \to {{SC}}\). The barycentric subdivision functor is defined as \(\chi= N\circ {El}\). Some important properties of the complex \(\chi(\Delta^I)\) are proved in Theorem 99. Let \(\Lambda\) be a category whose objects are finite non-empty subsets \(I\) of \(\mathbb{N}\) and morphisms are inclusions. Functors \(\Lambda^{op}\to Sets\) are called \textit{chromatic presimplicial sets}. Any simplicial complex \(K\) can be seen as a chromatic presimplicial set via the embedding of Proposition 104. The main result is formulated in Theorem 116: For every a collapsible simplicial complex \(K\), the complex \(\chi(K)\) is also collapsible. In particular, for every \(I\in \Lambda\) and \(n\in \mathbb{N}\), \(\chi^n(\Delta^I)\) is collapsible.