Name
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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.jcta.2006.07.001 | J. Comb. Theory, Ser. A |
Keywords | Field | DocType |
graph homomorphism,complete graph,polytopal complex,certain canonical realization,polygon dissection,clique number,canonical projection,convex polygon,fixed number,complexes hom,cyclic polytope,polyhedral cayley trick,lower face,cayley trick,composition,staircase triangulation.,generalized permutohedra,. cayley trick,staircase triangulation | Geometric graph theory,Discrete mathematics,Combinatorics,Vertex-transitive graph,Cayley graph,Polyhedral graph,Null graph,Petersen graph,Mathematics,Voltage graph,Complement graph | Journal |
Volume | Issue | ISSN |
114 | 3 | Journal of Combinatorial Theory, Series A |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Julian Pfeifle | 1 | 31 | 6.56 |