Optimizing the overlap of two independent Erdős-Rényi graphs
报告专家：巩舒阳博士（北京大学）
报告时间：2024年1月15日上午10:00-11:00
报告地点：数学院东409
报告摘要：For two independent Erdős-Rényi graphs G(n,p), we study the maximal overlap, i.e. the maximal number of common edges over all possible vertex correspondenceπ∈S_n. We consider the problem in two parameter regimes of p=n^(-α+o(1)): the sparse regime (1/2<α<1) and the dense regime (0<α<1/2). We prove that in the sparse regime, there exists a polynomial-time algorithm which finds the maximal overlap up to a multiplicative factor which is arbitrarily close to 1. As a by-product, we show that the maximal overlap is asymptotically n/(2α-1) in the sparse regime. For the dense regime, we establish an exact algorithmic phase transition via the branching overlap gap property. This talk is based on joint works with Jian Ding(PKU), Hang Du(MIT) and Rundong Huang(PKU).
专家简介：巩舒阳是北京大学的博士，师从陈大岳教授，研究方向为概率论。
邀请人：常寅山
