BIMSA > Research seminar in Discrete Mathematics Chromatic threshold via combinatorial convexity, and beyond
Chromatic threshold via combinatorial convexity, and beyond
Organizer
Benjamin Sudakov
Speaker
Jozef Skokan
Time
Tuesday, February 18, 2025 5:05 PM - 6:15 PM
Venue
Online
Online
Zoom 787 662 9899 (BIMSA)
Abstract
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