Beyond chromatic threshold via $(p,q)$-theorem, and sharp blow-up
phenomenon
Beyond chromatic threshold via $(p,q)$-theorem, and sharp blow-up
phenomenon
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 …