-

Chromatic threshold via combinatorial convexity, and beyond

组织者

本杰明·苏达科夫

演讲者

Jozef Skokan

时间

2025年02月18日 17:05 至 18:15

地点

Online

线上

Zoom 787 662 9899 (BIMSA)

摘要

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 Hong Liu, Chong S