Dissections, Hom-complexes and the Cayley trick (Q878954)

A homomorphism from a graph \(G\) to a graph \(H\) is a map from the vertex set of \(G\) to that of \(H\) which preserves edges. From the set of all homomorphisms from \(G\) to \(H\), the simplicial complexes Hom\((G,H)\) and Hom\(_+(G,H)\) may be constructed (see the article for details). These complexes have proven useful in the field of topological combinatorics. The article under review explores certain geometric properties of these complexes. First, it is shown that some canonical realisations of Hom\((G,H)\) and Hom\(_+(G,H)\) are related by a geometrical construction known as the polyhedral Cayley trick. Secondly, the shapes of the cells of certain canonical projections of Hom\((G,H)\) are derived, and found to be generalised permutohedra. The article then focuses on the case where \(G\) is a complete graph, and characterises when the projections of Hom\((G,H)\) will be polytopal or simplicial complexes. The results are then applied to dissection complexes (see the article for a definition), which provided the initial motivation to the article's authors.