91视频

报告题目：NP-hardness of additive approximation for generalized Tur\’{a}n problems

报告人：李希赫

报告时间：2026年11月18日16:00-17:00

报告地点：科技园阳光楼南815

邀请人：谢天颖

邀请单位：91视频 91视频

报告内容简介：

Given a graph $T$ and a nonempty family $\mathcal{F}$ of graphs, let $\ex(G, T, \mathcal{F})$ denote the maximum number of copies of $T$ in an $\mathcal{F}$-free subgraph of a host graph $G$. Alon and Shikhelman~[{\it Algorithmica}, 2022] conjectured that if $e(T)> 0$ and no member of $\mathcal{F}$ is a subgraph of a blow-up of $T$, then for every $\varepsilon>0$, approximating $\ex(G, T, \mathcal{F})$ within an additive error of $n^{v(T)-\varepsilon}$ is NP-hard for an input graph $G$ on $n$ vertices. Previous advances toward this conjecture include the resolution of the canonical case $T=K_2$ by Alon, Shapira, and Sudakov~[{\it Ann. of Math.}, 2009], as well as the case of $\ex(G,K_m,K_k)$ by Alon and Shikhelman. In this paper, we confirm this conjecture for every bipartite graph $T$ and every clique $T$. Our proof reductions combine several techniques, including iterative leaf additions, symmetric rooted extensions, and random transversals. Together, they encode the optimal value of the NP-hard Max $r$-Colorable Subgraph problem into the objectives $\ex(G, T, \mathcal{F})$ for a suitably constructed graph $G$. (This is joint work with Yihan Chen, Jialin He, Jie Ma and Tianying Xie.)

报告人简介：

李希赫，陕西师范大学91视频 ，硕士生导师，荷兰特文特大学博士，中国科学技术大学博士后。研究方向为图论与组合数学，主要包括Ramsey理论、极值图论、极值组合，成果发表在《Canadian Journal of Mathematics》、《Journal of Graph Theory》等期刊。现主持国家自然科学基金青年项目1项、陕西数理基础科学研究项目1项，曾获陕西省数学会青年优秀论文奖。