当前位置: 首页  科学研究  学术交流  学术报告

数学学科离散数学研究所学术报告(侯新民 中国科技大学;吕长虹 华东师范大学)

发布者:付慧娟   发布时间:2020-11-08  浏览次数:99

图与组合系列前沿讲座:

报告题目: The Turan number for the edge blow-up of trees

报告人:侯新民  中国科技大学 教授

报告时间:2020年11月9日 15:00

报告地点:腾讯会议ID:247 612 211 

摘要:The edge blow-up of a graph $F$ is the graph obtained from  replacing each edge in $F$ by a clique of the same size where the new vertices of the cliques are all different.In this article, we concern about the Tur\'an problem for the edge blow-up of trees. Erd\H{o}s et al. (1995) and Chen et al. (2003) solved the problem for stars. The problem for paths was resolved by Glebov (2011).Liu (2013) extended the above results to cycles and a special family of trees with the minimum degree at most two in the smaller color class  (paths and  proper subdivisions of stars were included in the family).In this talk, we extend Liu's result to all the trees with the minimum degree at least two in the smaller color class. Combining with Liu's result, except one particular case, the Tur\'an problem for the edge blow-up of trees is completely resolved.  Moreover, we determine the maximum number of edges in the family of $\{K_{1,k}, kK_2, 2K_{1,k-1}\}$-free graphs and the extremal graphs, which is an extension of a result given by Abbott et al. (1972).

报告人简介: 2002年毕业于大连理工大学,获理学博士学位。2002至2004 中国科学技术大学数学系博士后,同年8月留校。主要研究方向为组合与图论。 在Journal of Graph Theory, SIAM Journal on Discrete Mathematics, European Journal of Combinatorics 等国际组合图论权威刊物上发表论文多篇, 先后主持多项国家自然科学基金项目. 




报告题目: A bridge between the double resolving problem of graphs and the coin-weighing problem 

报告人: 吕长虹  华东师范大学 教授

报告时间:2020年11月9日 16:00

报告地点:腾讯会议ID:247 612 211

摘要:图G的顶点子集S称为图G的2-分辨集(Double resolving set), 如果G中任意两个顶点u, v都能在S中找到两个顶点x, y满足:x到u的距离与x到v的距离之差不等于y到u的距离与y到v的距离之差。2-分辨集的概念最初仅仅是Caceres 等人为了研究分辨集问题(resolving set problem)作为研究工具提出的一个新概念。2014年,陈旭瑾等人发现了带权值图的最小2-分辨集问题等价于复杂网络的扩散源定位问题(Locating the source of a diffusion in complex networks)。硬币称重问题(Coin-weighing problems)是个古老的组合优化问题,其中一个经典形式为:给定n个硬币,假定真硬币的重量和假硬币的重量均已知,用弹簧称对硬币进行称重,用最少的称重次数将所有的假币找出来。硬币称重问题已经得到很多学者广泛地研究。最近,我们证明了超方体的2-分辨集问题与硬币称重问题的等价关系,利用硬币称重问题上著名的Lindström方法给出超方体2-分辨集问题的一些新结果,包括解决公开问题;超方体的2-分辨集问题的图论结果反过来也提供了硬币称重问题的一些新进展。另外,我们也将介绍块图、仙人掌图、k-边树以及树的线图上2-分辨集问题的一些算法和理论结果。

报告人简介:吕长虹,华东师范大学数学科学学院教授,博士生导师,主要从事图论和组合算法方面理论和应用研究。吕长虹教授在图的距离标号问题、控制集问题等,得到了许多重要的理论和算法结果。近五年来,他和合作者解决了23年之久的(t,n)-family计数问题的猜想和2-边染色一致完全超图线性路划分的猜想。吕长虹教授2012年入选教育部新世纪优秀人才计划,2020年获得第二届萧树铁应用数学奖。目前担任中国数学会常务理事、上海市运筹学会副理事长、上海市工业与应用数学学会副理事长等职务。 

邀请人:金泽民