We establish a novel connection between the well-known chromatic threshold problem in extremal combinatorics and the celebrated (p, q)-theorem in discrete geometry. In particular, for a graph G with bounded clique number and a natural density condition, we prove a (p, q)-theorem for an abstract convexity space associated with G. Our result strengthens those of Thomassen and Nikiforov on the chromatic threshold of cliques. Our (p, q)-theorem can also be viewed as a χ-boundedness result for (what we call) ultra maximal Kr-free graphs. We further show that the graphs under study are blow-ups of constant size graphs, improving a result of Oberkampf and Schacht on homomorphism threshold of cliques. Our result unravels the cause underpinning such a blow-up phenomenon, differentiating the chromatic and homomorphism threshold problems for cliques. Our result implies that for the homomorphism threshold problem, rather than the minimum degree condition usually considered in the literature, the decisive factor is a clique density condition on co-neighborhoods of vertices. More precisely, we show that if an n-vertex Kr-free graph G satisfies that the common neighborhood of every pair of non-adjacent vertices induces a subgraph with Kr−2-density at least ε > 0, then G must be a blow-up of some Kr-free graph F on at most 2 O(rε log 1ε ) vertices. Furthermore, this single exponential bound is optimal.
Liu et al. (Thu,) studied this question.