24秋正式选课，组合学进阶课的知识，我其实起码学三遍了。但作为现代组合学中依旧常用的技术，多学几遍我非常乐意，事实上可能下学期我还要再去找Tuan Tran老师和Jack Koolen老师再学一遍。

今年相比去年，删减了一些Szemerédi正则引理的扩展知识，添加了Lovász局部引理的内容，还是不错的。

马杰老师愿意从北京来回赶给我们上课，真的挺负责的。

期末出卷，貌似相比于去年全部显然会不那么显然一些，但总归还是一个背书大赛。助教改卷可以说是放海水，只要提到大概意思的答案貌似都给的非常多分。而马老师的给分可以说是非常厚道，助教说优秀率65%，比他们改出来的结果还松，看来只要没有优秀率限制，马老师是愿意调分的（可能反倒是张老师不太会非线性的调分方式）。

一份略显啰嗦的笔记：组合学进阶.pdf

期末回忆卷：

一、设一图 $G=(V,E)$ 的 Laplace 矩阵的特征值分别为 $0={\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_n$，$S$ 为 $G$ 的一个独立集，而 $d_{ave}(S)={\displaystyle \frac{1}{|S|}}\sum _{v\in S}{d}_G(v)$ 定义为 $S$ 中点的平均度数，证明：$|S|\le n(1-{\displaystyle \frac{d_{ave}(S)}{{\lambda }_n}})$，并且说明这一结论可以导出 Hoffman's Bound。

二、对于任何 $s\ge 3$ 和充分大的 $t$，证明 $R(s,t)\ge c_s{\left({\displaystyle \frac{t}{\ln t}}\right)}^{\frac{s+1}{2}}$，其中 $c_s$ 为一只依赖于 $s$ 的正常数。

三、设 $H$ 是一张图，其点集为 $[h]$。设 $V_1,\dots ,V_h$ 构成一 $h$ 部图，并且只要 $ij\in E(H)$，就有 $(V_i,V_j)$ 是 $\epsilon -$regular 的。设 $T=\{(v_1,\dots ,v_h)\in V_1\times \cdots \times V_h:ij\in E(H)\Rightarrow v_i{v}_j\in E(G)\}$，尝试对 $H$ 的点数 $h$ 归纳证明：$|T|=(\prod _{ij\in E(H)}d(V_i,V_j)\pm Ch\epsilon )\prod _{i=1}^h|V_i|$，其中 $C$ 是一和 $H,\epsilon$ 都无关的普适常数。

四、设 $G$ 是一二部图，其所有点的度数都是偶数。对于 $G$ 的每一个顶点 $v$，都有一个不好的集合 $B_v\subseteq \{0,1,\dots ,d_G(v)\}$，并且满足 $|B_v|\le d_G(v)/2$，证明可以取出 $G$ 的一些边构成一个支撑子图，使得对于所有点，其在这一支撑子图中的度数都不属于对应的不好的集合。

从一开始云旁听到最后不得不到线下听课的人来说一句（其实我也没有都去，到了期末周确实好忙/(ㄒoㄒ)/~~）。

如果说组合学课程教的是经典组合，那么组合学进阶则迈入了modern Combinatoics的大门，算是一点点前沿内容了。

张先得老师讲得是算术组合和基础的谱图论部分。算术组合部分上来先证明了大名鼎鼎的组合零点定理，然后讲了其经典的几个应用，其中最有代表性的是加性组合（数论）中的Cauchy-Davenport定理。之后的谱图论因为我个人比较熟了所以甚至回放都没看，但大致上就是图特征值和各种参数的关系，度数、Moore Bound、Diameter等等。

马杰老师主要讲极值图论部分，上来花了一节课半证明了Szemerédi正则引理，之后一步步导出了Erdos-Stone-Simonovits定理。今年马杰老师相比2022年的讲义又加了不少东西（也可能是整理2022年note的人懒了后面的没整理），主要是(6,3)-Problem、Induced Matching Problem与One Edge One Triangle之间的关系，还有就是Stability Method。马老师讲课主要参考了这本书：

Extremal Graph Theory, Asaf Shapira.pdf

值得一提的是马杰老师的作业布置方式，与组合学本篇不同，进阶部分马老师的作业都是证明中各种gap的补全。马老师自己的研究生课极值组合中，布置作业的方式也是这样的。

虽然有点对不起张先得老师，但我确实更喜欢马杰老师的讲课风格🥺。我发邮件问马老师下学期还有无开极值组合课，得到了一个模糊的回答。感觉马老师可能在科大呆不久了，要去THU了，他的课且听且珍惜吧。

这门课在大部分时候和组合学一样平淡, 但今天 (2024.1.4) 上课时马杰老师讲 3-progression 时发生一件很有意思的事情:

对于集合 [n] 的子集 A, 考虑其中是否出现长为 3 的非平凡的 (即不能三项全相等) 等差数列. 很自然地想到, A 在 [n] 中占的密度越大, 越难以彻底规避这样的 3-progression. 此前 Bloom 和 Sisask 证明了: 如果 A 不含有这样的 3-progression, 则必须要满足 |A|

讲到这里的时候马杰老师特意提了一句: Kelley 与 Meka 两人都不是纯粹的数学家, 而是理论计算机出身. 这个结果最初也是发在计算机科学的刊物上, 但是做组合的数学家看了后纷纷认可. 当时马杰老师大概是看快下课了, 也讲不完下一个知识点, 便和我们分享了些自己对当今做数学, 尤其是做组合的所想. 什么要拓宽视野, 要主动搜罗新信息和新方法, 不要因别人的学科出身抱有成见云云. 原话虽是些老生常谈, 却格外使我有感触.

复习到快要昏死过去, 不知道当初开学为什么要光看名字选这门算不了学分的课.

我的评价是期末考千万只出套皮水题, 指望我能在不到一个月内学会 "自如运用" 这三章的东西未免有点看得起我.

讲义也是作用没有, 小错不断. 上网找了不知哪里来的学习笔记, 步骤比起君の "easy exercise" 至少要详细一些, 可供参考:

组合零点定理: 

https://yuliaalexandr.github.io/alexandr_yulia_2019_ba.pdf

谱图论的部分本质是比较简单的线性代数, 讲义还算能看.

Szemeredi均衡引理:

https://upcommons.upc.edu/bitstream/handle/2117/393365/TFG_Mariona_S%C3%A1nchez_Alc%C3%A1zar.pdf?sequence=2&isAllowed=y

https://iuuk.mff.cuni.cz/~rakdver/kgiii/lesson14-9.pdf

1.15出分后

期末考只有4道大题 (30+30+40+附加20) , 前两题是谱图论和零点定理的水题, 第三题是默写Graph Counting Lemma并由此证明Graph Removing Lemma, 第四题是默写Graph Embedding Lemma并证明一个关于广义Ramsey问题的结论. 题不算难, 认真复习基本就能写出来. 可惜自己只留了一天复习, Szemeredi均衡引理的部分觉得太难了感觉完全没看, 只拿了65分. 不过毕竟是1学分课, 能过就算胜利, 何况考完后作业还给了两天时间补交 (有助教答案) .

经历完折磨的期末复习后, 回头再来看这门课, 我的总结是有不可替代的收获, 能体验到当今最前沿的组合研究在做什么, 怎么做. 正如 ＠starrysheep 的评论所说, 学习者能够快速接触并理解最前沿的结果, 这是组合方向的独特之处. 但没必要选, 毕竟真爱的话自己旁听也会认真学, 注定不爱的来了也是坐牢, 还给自己的期末周添堵. 对我自己而言, 如果说上完组合学我的感受是不精, "以后要用还得再温习一遍" , 那进阶课就是几乎啥也没记住, 以后不走这个方向的用不上, 需要用上的恐怕必然要从头学起. 比起这种潦草的one glance, 我或许更倾向于腾出时间自己踏踏实实地看概率方法或代数图论的书.

最后一节课的最后20分钟, 马杰老师没有接着讲证明, 而是和我们随便聊了聊自己关于组合课学习, 以及走组合方向做研究的一些看法. 里面最令我印象深刻的一些话: "到了研究的深度, 组合和其它数学分支是一样的, 不存在一种学了后就能应对一切问题的高屋建瓴的观点 (否则数学家早就遍地都是了) , 琐碎的方法与技巧的积累是必需的. " 从老师的表情和声音也能感受得到, 他对今年学生在组合课上置身事外般的听课态度很有些失望 (毕竟老师每节课提的问题从来没有人回答) , 或许是原本预期能看到更多对组合感兴趣的人. 个人猜测马杰老师其实心知肚明学生对组合课的反对态度, 但仍然希望通过必修的方式往这个方向里拉到人. 我对此不予置评.

课本身没什么问题，期末出题改卷给分鉴定为寄，不知道怎么有脸说自己改卷很松的，要说我水平差我也无法反驳，真没想到进阶课喜提专业课最低分，只能说选课要谨慎，别教务给你置了你就傻兮兮来上。

P.S：不考虑分数的话，内容还是很有意思的。

不多说了，上讲义：

Comb.pdf

不得不说，今年因为把L-intersecting和1-distance两个问题放进了组合学（3学分）中讲掉了，于是组合学进阶部分有课时补充了很多精彩的内容，主要是在22年较为简略的Szemeredi的regularity lemma和Graph counting lemma这里增加了相对完整的，从正则引理到Triangle Removal Lemma以及Counting Lemma，到这部分理论在（6，3）-Problem，Induced Matching Problem，One-edge-one-triangle Problem（OEOT）的应用；最后在思考如何从Triangle推广到Graph，讲了Graph Counting Lemma，Graph Removal Lemma以及Graph Embedding Lemma。而且结论非常新，2023发表的相关成果都加入了课堂中介绍，可见马杰老师挑选课程内容时的用心。

只有期末考试，考察内容非常正统，好好复习就完全不用担心（然鹅...唉唉），且不说调不调分，只能说从卷子到助教都尽力在捞了。今年的两位助教都很负责，作业答案都写得很清晰整洁，也是好评。

总体来说非常推荐，比起22年（从讲义上看）课程体系要协调的多，相当漂亮的展示了正则引理后面的结论，层层递进，知识逻辑非常漂亮。马老师讲课很有启发性，会带动同学去思考，提出问题，相比之下张老师就是抄写大赛，但至少抄的流畅，现在发现这也不容易（？

相比组合的内容，个人觉得进阶课更值得认真感受和理解。组合这门学科，相比于其他板块更加追求灵机一动的感觉，某种意义上，数学的很多重大突破都会基于组合的技巧，来绕开一些理论上的难点或理论体系的缺失（这个宗老师给我讲了一点小故事，还是挺有感触的），还是希望能有更多同学来体验这门课的。

这门课很好的一点就是，当别的课还在讲19、20世纪的结论时，组合学已经讲到了许多21世纪的结论。mj老师讲的很大一部分都是现代组合学研究中的非常重要的一个定理，并且给出了这个定理的许多应用。但是不好的一点就是讲课过程中会留下许多的exercise，某些定理会给一个sketch，但是detailed的证明不会给出。上课的时候暗示了会出detailed的证明，但是对于1.5结课1.6就有两门考试的我来说在考试周完全没有时间准备。

在网上找资料的时候看到了mj老师20年的Extremal and Probabilistic Graph Theory的讲义与视频，在讲Graph Counting Lemma和Graph Removal Lemma的时候与今年差不多（可以感受一下留作exercise是多么让人摸不到头脑。考试的时候就考了Graph Removal Lemma的证明，不出意外的寄掉了。但是mj老师讲课讲的还是很好的，感觉就是他在带着你进行探索。

感觉组合这个学科最大的特点就是，真正被完全解决的问题很少，很多问题都是给出了一个到目前为止的一个“最好”的结果。也可以说组合学目前是一个很有潜力的学科

总之这门课还是学到了很多！大赞mj