Interpolating chromatic and homomorphism thresholds

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 $\hat{I}\mu >0$, if $G$ is an $n$-vertex $K_s$-free graph with VC-dimension $d$ and $\hat{I}´(G)\ge (\frac{(s-3)(t-s+2)+1}{(s-2)(t-s+2)+1}+\hat{I}\mu )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, Łuczak and Thomassé, 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 $\hat{I}{´}_B(H)$ as the infimum $\hat{I}\pm$ such that every $n$-vertex maximal $H$-free graph $G$ with $\hat{I}´(G)\ge \hat{I}\pm 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 $\hat{I}{´}_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.

29 pages