极值集合论中的一些经典问题与方法

本书深入且系统地探讨了极值集合论这一专业数学领域的核心问题与方法。 内容上，涵盖多种重要方法，如移位方法、随机游走方法、生成集方法等。此外，书末还列出了一些公开问题，为读者进一步探索提供方向。
本书专业性强，深入剖析多种复杂数学方法和前沿成果，对极值集合论进行深度挖掘。注重方法介绍，每种方法独立成章，且结合具体定理证明和实际问题，实现理论与实践紧密结合。
本书适合数学专业的研究生、科研人员及高校数学教师阅读。对于研究生是深入学习的教材，助力学术研究；科研人员可从中获取最新方法和研究动态；高校教师则可作为教学参考，提升教学质量。

极值集合论是组合数学的重要研究分支之一，主要研究满足给定条件下集族的相关极值问题，在概率论、密码学、离散几何以及理论计算机科学等领域中都有非常广泛的应用。我国著名数学家柯召先生与匈牙利数学家保罗·埃尔德什、英国数学家理查德·拉多合作完成的埃尔德什-柯-拉多定理是极值集合论的奠基性定理，开辟了极值集合论迅速发展的道路。
本书内容涵盖移位方法、随机游走方法、生成集方法、线性代数方法、弗兰克尔-库帕夫斯基集中不等式、超图匹配问题以及移位方法的新应用等，此外第 8 章中还列出了目前极值集合论中一些未证明的猜想和未解决的问题。
本书可以作为高等院校数学专业高年级本科生和研究生、计算机专业和其他专业研究生的组合数学课程辅助教材，也可作为相关研究工作者的参考书。

王健
太原理工大学数学学院副教授，2016年博士毕业于南开大学组合数学中心，导师为陈永川院士。 主要研究方向为极值组合学，主持国家自然科学基金青年项目和面上项目各一项，入选山西省2024年度三晋英才计划科技创新青年拔尖人才。在COMBINATORICA；Journal of Combinatorial Theory, Series A；Journal of Combinatorial Theory, Series B；SIAM Journal on Discrete Mathematics；Combinatorics, Probability & Computing等期刊上发表论文40余篇。

第 1 章 移位方法 .................................................................................................... 1
1.1 埃尔德什-柯-拉多定理 ........................................................................................ 1
1.2 移位方法简介 ........................................................................................................ 3
1.3 埃尔德什-柯-拉多定理的移位方法证明 ............................................................ 5
1.4 非平凡相交集族的希尔顿-米尔纳定理 ..............................................................6
1.5 克鲁斯卡尔-卡托纳定理 ...................................................................................... 9
1.6 希尔顿引理 .......................................................................................................... 13
1.7 皮贝尔定理 .......................................................................................................... 15
1.8 卡托纳相交影子定理 .......................................................................................... 18
1.9 卡托纳并定理 ...................................................................................................... 22
1.10 克莱特曼等径定理与 VC 维定理 ..................................................................... 24
第 2 章 随机游走方法 ........................................................................................... 27
2.1 k 元集合与格路之间的双射 ............................................................................... 27
2.2 t -相交埃尔德什-柯-拉多定理的弗兰克尔证明 ............................................... 30
2.3 随机游走方法在 r -项 t -相交非一致集族上的应用 ......................................... 40
第 3 章 生成集方法 ............................................................................................... 44
3.1 生成集方法简介 .................................................................................................. 44
3.2 t -相交埃尔德什-柯-拉多定理的生成集方法证明 ........................................... 48
3.3 非空交叉 t -相交集族的最大和问题 ................................................................. 53
第 4 章 线性代数方法 ........................................................................................... 58
4.1 霍夫曼定理与埃尔德什-柯-拉多定理的谱方法证明 ...................................... 58
4.2 黄-赵定理 ............................................................................................................ 61
4.3 精确 t -相交埃尔德什-柯-拉多定理的威尔逊证明 .......................................... 66
4.4 埃尔德什-柯-拉多定理的多项式方法证明 ...................................................... 77
第 5 章 弗兰克尔-库帕夫斯基集中不等式 ............................................................. 82
5.1 鞅与弗兰克尔-库帕夫斯基集中不等式 ............................................................ 82
5.2 弗兰克尔-库帕夫斯基集中不等式的推导 ........................................................ 85
5.3 哈密顿(a,b)-圈的存在性问题 ............................................................................. 88
5.4 直积超图上的彩色匹配问题 .............................................................................. 91
第 6 章 超图匹配问题 ......................................................................................... 105
6.1 弗兰克尔匹配定理的证明 ................................................................................ 105
6.2 给定最小正协度的相交集族 ............................................................................ 109
6.3 一致超图的几乎完美匹配 ................................................................................ 116
第 7 章 移位方法的新应用 .................................................................................. 126
7.1 覆盖数为 s 的相交集族 ..................................................................................... 126
7.2 相交集族的多样性和最大度比率问题 ............................................................ 132
7.3 相交集族的最大多样性 .................................................................................... 137
第 8 章 一些未证明的猜想和未解决的问题 ......................................................... 144
8.1 埃尔德什-拉多太阳花猜想 .............................................................................. 144
8.2 弗兰克尔并封闭集族猜想 ................................................................................ 145
8.3 埃尔德什匹配猜想 ............................................................................................ 146
8.4 弗兰克尔 s -项 u -并猜想 ................................................................................. 146
8.5 弗兰克尔 t -相交 u -并猜想 .............................................................................. 148
8.6 埃尔德什-洛瓦斯相交集族问题 ...................................................................... 149
8.7 赖瑟覆盖数猜想 ................................................................................................ 149
参考文献 ............................................................................................................... 151