Simple Σ_r-homotopy types of HOM complexes and box complexes assigned to r-graphs

摘要

For a pair of graphs, Lovász introduced a polytopal complex called the Hom complex in order to estimate topological lower bounds for chromatic numbers of graphs. The definition is generalized to hypergraphs. Given an r-graph H, we compare the Hom complex of the complete r-partite r-graph and H with the box complex of H invented by Alon, Frankl and Lovász. We verify that both complexes which are equipped with right actions of the symmetric group on r letters Σ_r, are of the same simple Σr-homotopy type.