{
  "id": "2412.19039",
  "version": "v1",
  "published": "2024-12-26T03:16:46.000Z",
  "updated": "2024-12-26T03:16:46.000Z",
  "title": "Homotopy types of Hom complexes of graph homomorphisms whose codomains are square-free",
  "authors": [
    "Soichiro Fujii",
    "Kei Kimura",
    "Yuta Nozaki"
  ],
  "comment": "29 pages, no figures",
  "categories": [
    "math.CO",
    "math.AT"
  ],
  "abstract": "Given finite simple graphs $G$ and $H$, the Hom complex $\\mathrm{Hom}(G,H)$ is a polyhedral complex having the graph homomorphisms $G\\to H$ as the vertices. We determine the homotopy type of each connected component of $\\mathrm{Hom}(G,H)$ when $H$ is square-free, meaning that it does not contain the $4$-cycle graph $C_4$ as a subgraph. Specifically, for a connected $G$ and a square-free $H$, we show that each connected component of $\\mathrm{Hom}(G,H)$ is homotopy equivalent to a wedge sum of circles. We further show that, given any graph homomorphism $f\\colon G\\to H$ to a square-free $H$, one can determine the homotopy type of the connected component of $\\mathrm{Hom}(G,H)$ containing $f$ algorithmically.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-12-26T03:16:46.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "55U05",
      "05C15",
      "55P15",
      "06A15"
    ],
    "keywords": [
      "homotopy type",
      "graph homomorphism",
      "hom complex",
      "square-free",
      "connected component"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 29,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}