意大利米兰博科尼大学张继昱学术报告

发布日期:2026-11-19    浏览次数:

报告题目:Rotated Laplacian, and Cheeger-type inequalities for digraphs

报告人:张继昱

报告时间:2026年11月27日14:30-15:30

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

邀请人:周宏

邀请单位:福州大学数学与统计学院、福州大学离散数学研究中心

报告内容简介:

A common theme in spectral graph theory studies the connection between graph structure and the spectrum of the matrices associated with the graph. The Cheeger's Inequality states that the second smallest eigenvalue of the Laplacian matrix measures the connectivity of the graph. Inspired by recent advances in notions of spectral approximation of digraph, we study the spectrum of a rotated Laplacian matrix associated with a digraph. We show that the smallest eigenvalue of the rotated Laplacian measures the periodicity of the digraph, in the sense that we present a Cheeger-type inequality for periodicity. We then generalize this connection to higher eigenvalues and present a higher-order Cheeger-type inequality. This is proved by spectral embedding of the vertices using the eigenvectors of the rotated Laplacian. Our proof is algorithmic and gives a randomized polynomial-time spectral algorithm for partitioning the graph into periodic components.

报告人简介:

张继昱是意大利米兰博科尼大学的博士五年级学生/助理研究员。他的导师是Luca Trevisan,随后由Salil Vadhan和Alon Rosen联合指导。他的研究兴趣包括算法设计与分析、计算复杂性理论,以及它们与数学相关领域的交互。