第十三期图论与组合数学读书班

Abstract

本周我们主要介绍随机图 G(n, c/n) 中的相变现象。以该随机图模型中的孤立点个数为例引入强阈函数的概念，并给出经典的一阶矩与二阶矩方法。本次讨论班的主要内容是随机图巨大连通分支尺寸的相变现象，着重分析在次临界态最大连通分支的大小以及具体结构，超临界态下最大连通分支与次大连通分支的大小的渐进估计，临界态下最大连通分支大小的 double jump 现象。

参考书籍：The Probabilistic Method (4th edition)，Graph Theory and Additive Combinatorics，Probabilistic Methods in Combinatorics。

基本信息

• 系列：图论与组合数学讨论班（2025 秋季）
• 时间：2025 年 12 月 14 日（周日）19:00–21:00
• 地点：北衡楼 1216
• 腾讯会议：436-8103-5036
• 研讨主持：付智旋
• 指导教师：宋慧敏

内容概要

本周主要介绍随机图 G(n, c/n) 中的相变现象。以该随机图模型中的孤立点个数为例引入强阈函数的概念，并给出经典的一阶矩与二阶矩方法。主要内容是随机图巨大连通分支尺寸的相变现象，着重分析在次临界态最大连通分支的大小以及具体结构，超临界态下最大连通分支与次大连通分支的大小的渐进估计，临界态下最大连通分支大小的 double jump 现象。

海报