AbstractExtremal eigenvalues of graphs are of particular interest in theoretical computer science and combinatorics. Specifically, the spectral gap—the gap between the first and second largest eigenvalues—measures the expanding property of the graph. In this talk, I will focus on random $d$-regular graphs, for which the largest eigenvalue is $d$.I'll first explain some conjectures on the extr...
AbstractLet $H$ be a graph with $\chi(H) = r+1$. Simonovits's theorem states that, for every edge-critical graph $H$, the unique largest $H$-free subgraph of $K_n$ is its largest $r$-partite subgraph, provided that $n$ is sufficiently large. We show that the same holds with $K_n$ replaced by $G_{n,p}$ whenever $H$ is also strictly 2-balanced and $p \ge C_H n^{-1/m_2(H)} \log(n)^{1/(e(H)-1)}$ fo...
E-mail：qzsy@tsinghua.edu.cn
Address：Qiuzhen College, Tsinghua University, Haidian District, Beijing
© 2024 Tsinghua University. All Rights Reserved 京ICP备15006448号 京公网安备 110402430053 号
