Simple homotopy type

The converse of Proposition 6.14 is not true there are abstract simplicial complexes that are contractible, yet not collapsible. The situation is somewhat clarified by the following result. 

Theorem 6.16. A generalized simplicial complex A is contractible if and only if there exists a sequence of collapses and expansions (operation inverse to the collapse, also called an anticollapse) leading from A to a vertex. 

More generally, one benefits from the following definition. 

Definition 6.17. Two generalized simplicial complexes are said to have the same simple homotopy type if there exists a sequence of elementary collapses and expansions leading from one to the other. Such a sequence is called a formal deformation. 

Theorem 6.16 is a special case of the fundamental theorem that in particular says that two simply connected generalized simplicial complexes are homotopy equivalent if and only if they have the same simple homotopy type. 

---

It is known that a subdivision of any generalized simplicial complex X has the same simple homotopy type as X. Let us show a special case of that. 

Under the conditions of Theorem 13.22(b), the simplicial complex A P) collapses onto the simplicial complex A(Q). This implies Theorem 13.12 as a special case. In particular, the complexes A(P) and A(Q) have the same simple homotopy type. 

Recall from Section 6.4 that the analogous equivalence relation, where ne and yoE are replaced by and y, is called the simple homotopy type, and that the celebrated Whitehead theorem implies that the simplicial complexes with the simple homotopy type of a point are precisely those that are contractible see Theorem 6.16. Therefore, the class of simplicial complexes that are NE-equivalent to a point relates to nonevasiveness in the same way as con-tractibility relates to collapsibility. Clearly, this means that this class should constitute an interesting object of study. 

We conjecture that NE-equivalence is much coarser than Whitehead s simple homotopy type. 

Conjecture 13.25. There exists an infinite family of finite simplicial complexes all of which have the same simple homotopy type such that Xi Xj, for all i j. 

It will be shown in Theorem 18.3 that the complexes Af G) and Bip (G) have the same simple homotopy type. This fact leads one to consider the family of Horn complexes as a natural context in which to look for further obstructions to the existence of graph homomorphisms. 

The discussion in Section 6.5 implies now that the polyhedral complex of all bipartite subgraphs of G, Bip(G), and the neighborhood complex Af G), have the same simple homotopy type, and yields an explicit formal deformation between these two complexes. ... 

We have seen in Theorem 18.3 that the complex Bip (G) has the same simple homotopy type as the neighborhood complex of G. In particular, the complex Bip (Kn) is homotopy equivalent to the sphere S . The following proposition summarizes more complete information. 

Ko06c] D.N. Kozlov, Simple homotopy types of Horn-complexes, neighborhood complexes, Lovdsz complexes, and atom crosscut complexes. Topology and its Appl. 153 (2006), no. 14, 2445-2454. 

Cs07] P. Csorba, On simple Z2-homotopy type of graph complexes, and their simple Z2-universality, preprint 2007, to appear in Canad. Math. Bull. 

It is useful to generalize the model development procedure just described, adopting the idea of homotopy methods that have become important in the design of algorithms to solve various types of optimization problems. The basic idea is the construction of a continuous path connecting a difficult problem that we wish to solve with a simpler problem that we can solve easily. By following the path in sufficiently small steps from the simple problem, we ultimately obtain an approximate solution to the more complicated problem of interest. More specifically, two continuous functions f X Y and g X Y, axe said to be homotopic if there exists a continuous function 77 X x [0,1] "K such that 77(2 , 0) = f x) and 77(a , 1) = g x) [18, ch. 11]. The idea behind homotopy methods in minimization, for example, is to find a homotopy function 77(i, A) such that H x, 0) = f x) defines an easy minimization problem and H x,l) = g x) defines the minimization problem we would like to solve. This approach is useful in cases where we can construct a sequence of intermediate values satisfying... 

---