Academy of Mathematics and Systems Science, CAS Colloquia & Seminars
Speaker:
王光辉教授,山东大学数学学院
Inviter:
交叉中心
Title:
Applications of sublinear expanders
Language:
Chinese
Time & Venue:
2023.02.18 10:30-11:30 N219
Abstract:
We will introduce the sublinear expander and cover some applications of sublinear expander. 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 cd^{1/2} vertices. It also confirms a conjecture from Verstra?te: every graph of average degree cd^2, for some absolute constant c>0, contains a pair of disjoint isomorphic subdivisions of the complete graph Kd.