Beijing Institute of Mathematical Sciences and Applications

Benjamin Sudakov

Jozef Skokan

Tuesday, February 18, 2025 5:05 PM - 6:15 PM

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

Jozef Skokan is a Professor in Mathematics at the London School of Economics and Political Science. Before moving to London, he studied Applied Mathematics at the Czech Technical University in Prague, received his PhD from Emory University in Atlanta under the supervision of Vojtech Rödl, and spent some years as postdoc at the University of Illinois at Urbana-Champaign and Universidade de São Paulo. His primary research interests are extremal and probabilistic combinatorics, and he also enjoys exploring connections between combinatorics and other parts of mathematics.