Interpolating chromatic and homomorphism thresholds

Abstract

The problem of chromatic thresholds seeks minimum degree conditions that ensure that dense H -free graphs 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 s -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 t -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 existence 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 2 k − 1 ) = 1 2 k − 1 for any integer k ≥ 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 to find the desired homomorphic images, and draw a connection to a problem concerning codes on graphs.