报告学者：刘鸿教授

报告者单位：韩国基础科学研究院

报告时间：2024年4月18日（周四）16:00-17:00

报告地点：学活十层1005会议室

报告摘要：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 strengthens those of Thomassen and Nikiforov on the chromatic threshold of cliques. Our $(p,q)$-theorem can also be viewed as a $\chi$-boundedness result for (what we call) ultra maximal $K_r$-free graphs. 

We further show that the graphs under study are blow-ups of constant size graphs, improving a result of Oberkampf and Schacht on homomorphism threshold of cliques. Our result unravels the cause underpinning such a blow-up phenomenon, differentiating the chromatic and homomorphism threshold problems for cliques. Our result implies that for the homomorphism threshold problem, rather than the minimum degree condition usually considered in the literature, the decisive factor is a clique density condition on co-neighborhoods of vertices.

报告人简介： 刘鸿教授2015年在伊利诺伊大学厄巴纳-香槟分校(UIUC)取得博士学位，师从József Balogh教授。2019年在华威大学(Warwick U)取得终身教职，并摘获英国科研创新（UKRI）未来领袖奖。2022年加入韩国基础科学研究院(IBS)任首席科学家，现是其极值及概率组合研究组(ECOPRO)的领头人。2023年起，担任图论组合领域顶级期刊Siam Journal on Discrete Mathematics副主编。研究领域包括极值与概率组合、图论、离散几何、Ramsey理论、组合数论。在Journal of the American Mathematical Society等期刊上发表论文50余篇。