Interpolating chromatic and homomorphism thresholds

The problem of chromatic thresholds seeks for minimum degree conditions that ensure dense 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 main result shows a smooth transition between these two thresholds when varying the restrictions on homomorphic images. In particular, we proved that for t ≥ s ≥ 3 and ε > 0, if G is an n-vertex Kₛ-free graph with VC-dimension d and δ(G) ≥ [( (s−3)(t−s+2)+1 )/( (s−2)(t−s+2)+1 ) + ε] n, then G is homomorphic to a Kₜ-free graph H with |H| = O_{s,t,d,ε}(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 δ_B(H) as the infimum α such that every n-vertex maximal H-free graph G with δ(G) ≥ αn is a blowup of some F with |F| = O_{α,H}(1). This notion strengthens homomorphism thresholds. While the homomorphism thresholds for odd cycles remain unknown, we prove that δ_B(C_{2k−1}) = 1/(2k−1) for any integer k ≥ 2. This strengthens the result of Ebsen and Schacht and answers a question of Schacht, showing 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 to find the desired homomorphic images, and draw connection to a problem concerning codes on graphs.