Speaker
Hong Liu, Institute for Basic Science
Abstract
Chromatic threshold via combinatorial convexity, and beyond 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 graphs with bounded clique number and certain natural density condition, we prove a $(p,q)$-theorem for the dual of its maximal independent sets hypergraph. Our result strengthens those of Thomassen and Nikiforov on the chromatic threshold of cliques. We further show that the graphs under study in fact have `bounded complexity’ in the sense that they are blow-ups of constant size graphs with the same clique number, strengthening the results of Luczak and Goddard-Lyle on homomorphism threshold of cliques and improving the best known quantitative result of Oberkampf and Schacht. Our result unravels the cause underpinning such blow-up phenomenon, showing that rather than the minimum degree condition usually considered in the literature, the decisive factor is a density condition on co-neighbourhoods. Joint work with Chong Shangguan, Jozef Skokan, Zixiang Xu.