{
  "id": "2502.09576",
  "version": "v1",
  "published": "2025-02-13T18:34:43.000Z",
  "updated": "2025-02-13T18:34:43.000Z",
  "title": "Interpolating chromatic and homomorphism thresholds",
  "authors": [
    "Xinqi Huang",
    "Hong Liu",
    "Mingyuan Rong",
    "Zixiang Xu"
  ],
  "comment": "29 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "The problem of chromatic thresholds seeks for minimum degree conditions that ensure $H$-free graphs to have a bounded chromatic number, or equivalently a bounded size homomorphic image. The strengthened homomorphism thresholds problem further requires that the homomorphic image itself is $H$-free. The purpose of this paper is two-fold. First, we define a generalized notion of threshold which encapsulates and interpolates chromatic and homomorphism thresholds via the theory of VC-dimension. Our first result shows a smooth transition between these two thresholds when varying the restrictions on homomorphic images. In particular, we proved that for $t \\ge s \\ge 3$ and $\\epsilon>0$, if $G$ is an $n$-vertex $K_s$-free graph with VC-dimension $d$ and $\\delta(G) \\ge (\\frac{(s-3)(t-s+2)+1}{(s-2)(t-s+2)+1} + \\epsilon)n$, then $G$ is homomorphic to a $K_t$-free graph $H$ with $|H| = O(1)$. Moreover, we construct graphs showing that this minimum degree condition is optimal. This extends and unifies the results of Thomassen, {\\L}uczak and Thomass\\'e, and Goddard, Lyle and Nikiforov, and provides a deeper insight into the cause of existences of homomorphic images with various properties. Second, we introduce the blowup threshold $\\delta_B(H)$ as the infimum $\\alpha$ such that every $n$-vertex maximal $H$-free graph $G$ with $\\delta(G)\\ge\\alpha n$ is a blowup of some $F$ with $|F|=O(1)$. This notion strengthens homomorphism threshold. While the homomorphism thresholds for odd cycles remain unknown, we prove that $\\delta_B(C_{2k-1})=1/(2k-1)$ for any integer $k\\ge 2$. This strengthens the result of Ebsen and Schacht and answers a question of Schacht and shows that, in sharp contrast to the chromatic thresholds, 0 is an accumulation point for blowup thresholds. Our proofs mix tools from VC-dimension theory and an iterative refining process, and draw connection to a problem concerning codes on graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2025-02-13T18:34:43.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "free graph",
      "homomorphic image",
      "interpolating chromatic",
      "minimum degree condition",
      "notion strengthens homomorphism threshold"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 29,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}