Dissections, Hom-complexes and the Cayley trick

2005/12/22 by Julián Pfeifle, Julian Pfeifle, Pfeifle, Julian
Mathematics · #52B11 (Primary) 05C99 #52B70 (Secondary) #Advanced Combinatorial Mathematics #Algebraic structures and combinatorial models #Combinatorics (math.CO) #FOS: Mathematics #Homotopy and Cohomology in Algebraic Topology #Metric Geometry (math.MG) #math.CO #math.MG #msc:05C99 #msc:52B11 #msc:52B70

paper · pdf · doi:10.48550/arxiv.math/0512529

23 pages, 5 figures; improved exposition; accepted for publication in JCTA

openalex publication_date 2005/12/22 · arxiv created 2006/06/27 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Related

• Homotopy types of Hom complexes of graph homomorphisms whose codomains are cycles
• Affine hom-complexes
• Hom complexes and homotopy theory in the category of graphs
• Homotopy types of Hom complexes of graph homomorphisms whose codomains are square-free
• Simple S_r-homotopy types of Hom complexes and box complexes associated to r-graphs