Dissections, Hom-complexes and the Cayley trick

We show that certain canonical realizations of the complexes Hom ( G , H ) and Hom + ( G , H ) of (partial) graph homomorphisms studied by Babson and Kozlov are, in fact, instances of the polyhedral Cayley trick. For G a complete graph, we then characterize when a canonical projection of these complexes is itself again a complex, and exhibit several well-known objects that arise as cells or subcomplexes of such projected Hom -complexes: the dissections of a convex polygon into k-gons, Postnikovʹs generalized permutohedra, staircase triangulations, the complex dual to the lower faces of a cyclic polytope, and the graph of weak compositions of an integer into a fixed number of summands.