Prodsimplicial Complexes

Definition 2.43. A polyhedral complex whose cells are direct products of sim-plices is called a prodsimplicial complex. 

Just as in the simplicial case, there exists a canonical way to associate a prodsimplicial complex to a graph. 

Definition 9.16. Let G he an arbitrary graph. We define the prodsimplicial complex PF[G) as follows the graph G is taken to be the 1-dimensional skeleton of PF[G), and the higher-dimensional cells are taken to be all those products of simplices whose 1-dimensional skeleton is contained in the graph G. The complex PF G) is called prodsimplicial flag complex ofG. 

The prodsimplicial flag construction allows one to specify a prodsimplicial complex by a relatively compact set of data. The reader should note that while a simplicial complex is always also a prodsimplicial complex, a simplicial flag complex is usually not a prodsimplicial flag complex. An example of that is provided by a hollow square. 

The prodsimplicial complex Bip (G) is our first example of the so-called Hom(-, -)-construction, namely, as a polyhedral complex it is isomorphic to Horn K2, G). 

In this section we would like to prove a property that holds for general morphism complexes, which were described in Definition 9.24. A crucial fact about this family of prodsimplicial complexes is that Horn, —) complexes are fuUy... 

Proposition 18.1 was first formulated and proved by the author in [Ko05a, Proposition 2.2.2], where also the concept of prodsimplicial complexes was introduced. 

Proof. By Proposition 18.12, we know that under the assumptions of the theorem, the prodsimplicial complex Horn (T, H) is a Z2-space for any loop-free graph H. 

For m > 3, the prodsimplicial complexes Horn Km, G) can be thought of as consisting of all complete m-partite subgraphs of G. Even in the case G = K , it seems complicated to understand Hom(iFm,G) up to homeomorphism see Figure 19.1. However, we still obtain a good description of the homotopy type. 

Theorem 19.10. Let us assume that m and n are positive integers and that n > m. The prodsimplicial complex of all n-colorings of a complete graph with m vertices, Horn Km, Kn), is homotopy equivalent to a wedge of n — m)-dimensional spheres. 

On the other hand, the prodsimplicial complex Bip (G) has nontrivial homology already in dimension 1. Indeed, since the vertices vi,...,vt are chosen... 

In recent years, several families of complexes that appeared in combinatorics were not simplicial, but rather prodsimplicial. 

Clearly, these complexes are prodsimplicial. It will be shown in Section 18.1.1 that complexes of morphisms Horn, —) are in fact prodsimplicial flag complexes. 

Proposition 18.1 comes in handy when we need to show that certain prod-simplicial complexes caimot be represented as Horn complexes, since it imposes the rather rigid restriction of being a prodsimplicial flag complex. 

---