{
  "id": "1110.3758",
  "version": "v2",
  "published": "2011-10-17T18:35:04.000Z",
  "updated": "2012-06-14T03:11:33.000Z",
  "title": "Maximizing H-colorings of a regular graph",
  "authors": [
    "David Galvin"
  ],
  "comment": "21 pages, small revisions from earlier version, this version to appear in Journal of Graph Theory",
  "categories": [
    "math.CO"
  ],
  "abstract": "For graphs $G$ and $H$, a {\\em homomorphism} from $G$ to $H$, or {\\em $H$-coloring} of $G$, is an adjacency preserving map from the vertex set of $G$ to the vertex set of $H$. Writing ${\\rm hom}(G,H)$ for the number of $H$-colorings admitted by $G$, we conjecture that for any simple finite graph $H$ (perhaps with loops) and any simple finite $n$-vertex, $d$-regular, loopless graph $G$ we have $$ {\\rm hom}(G,H) \\leq \\max{{\\rm hom}(K_{d,d},H)^{\\frac{n}{2d}}, {\\rm hom}(K_{d+1},H)^{\\frac{n}{d+1}}} $$ where $K_{d,d}$ is the complete bipartite graph with $d$ vertices in each partition class, and $K_{d+1}$ is the complete graph on $d+1$ vertices. Results of Zhao confirm this conjecture for some choices of $H$ for which the maximum is achieved by ${\\rm hom}(K_{d,d},H)^{n/2d}$. Here we exhibit infinitely many non-trivial triples $(n,d,H)$ for which the conjecture is true and for which the maximum is achieved by ${\\rm hom}(K_{d+1},H)^{n/(d+1)}$. We also give sharp estimates for ${\\rm hom}(K_{d,d},H)$ and ${\\rm hom}(K_{d+1},H)$ in terms of some structural parameters of $H$. This allows us to characterize those $H$ for which ${\\rm hom}(K_{d,d},H)^{1/2d}$ is eventually (for all sufficiently large $d$) larger than ${\\rm hom}(K_{d+1},H)^{1/(d+1)}$ and those for which it is eventually smaller, and to show that this dichotomy covers all non-trivial $H$. Our estimates also allow us to obtain asymptotic evidence for the conjecture in the following form. For fixed $H$, for all $d$-regular $G$ we have $$ {\\rm hom}(G,H)^{\\frac{1}{|V(G)|}} \\leq (1+o(1))\\max{{\\rm hom}(K_{d,d},H)^{\\frac{1}{2d}}, {\\rm hom}(K_{d+1},H)^{\\frac{1}{d+1}}} $$ where $o(1)\\rightarrow 0$ as $d \\rightarrow \\infty$. More precise results are obtained in some special cases.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-06-14T03:11:33.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "regular graph",
      "maximizing h-colorings",
      "vertex set",
      "conjecture",
      "simple finite graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1110.3758G"
    }
  }
}