报告题目：Balance subdivisions of graphs

报告人：王光辉教授，山东大学

报告时间：2022年5月6日下午14：30-15：30

报告地点：腾讯会议（会议号：442793458）

主持人：何伟骅

报告摘要：Given a graph H, a balanced subdivision of H is a graph obtained from H by subdividing every edge the same number of times. In 1984, Thomason conjectured that for each integer k≥1, high average degree is sufficient to guarantee a balanced subdivision of Kk. Recently, Liu and Montgomery resolved this conjecture. We give an optimal estimate up to an absolute constant factor by showing that there exists c>0 such that for sufficiently large d, every graph with average degree at least d contains a balanced subdivision of a clique with at least cd1/2 vertices. It also confirms a conjecture from Verstra{ë}te: every graph of average degree cd2, for some absolute constant c>0, contains a pair of disjoint isomorphic subdivisions of the complete graph Kd. We also prove that there exists some absolute c>0 such that for sufficiently large d, every C4-free graph with average degree at least d contains a balanced subdivision of the complete graph Kcd, which extends a result of Balogh, Liu and Sharifzadeh.

专家简介：王光辉，山东大学数学学院教授、党委书记，主要从事组合数学基础理论及其在数据科学等领域的应用研究，在Journal of London Mathematical Society、ACM-SIAM Symposium on Discrete Algorithms(SODA)、Journal of Graph Theory、European Journal of Combinatorics、Combinatorics Probability & Computation等期刊会议发表论文40余篇。主持负责国家自然科学基金四项，并承担国家自然科学基金重点项目子课题，获得了2017年山东省青年科技奖和2018年中国运筹学会青年科技奖。