極值集合論中的一些經典問題與方法
王健
- 出版商: 人民郵電
- 出版日期: 2025-10-01
- 售價: $474
- 語言: 簡體中文
- 頁數: 158
- ISBN: 7115674159
- ISBN-13: 9787115674159
-
相關分類:
離散數學 Discrete-mathematics
尚未上市，歡迎預購
商品描述
極值集合論是組合數學的重要研究分支之一，主要研究滿足給定條件下集族的相關極值問題，在概率論、密碼學、離散幾何以及理論計算機科學等領域中都有非常廣泛的應用。我國著名數學家柯召先生與匈牙利數學家保羅·埃爾德什、英國數學家理查德·拉多合作完成的埃爾德什-柯-拉多定理是極值集合論的奠基性定理，開辟了極值集合論迅速發展的道路。
本書內容涵蓋移位方法、隨機遊走方法、生成集方法、線性代數方法、弗蘭克爾-庫帕夫斯基集中不等式、超圖匹配問題以及移位方法的新應用等，此外第 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
