第三届魅丽数学与交叉应用会议（基础篇）
大家好，本人 24 日参加魅丽数学与交叉应用会议的报告，非常荣幸。会上，也学习了很多本人接触过但是没深入研究的部分，现在把一些知识点和笔记作整理。
关于极值图论
1.超图
定义。从文字上讲，肯定比“边”多一些。通超图里，我们抽象出一种新的边：超边（hyperedge）。本人从图示的角度，认为超边其实包含传统意义上的边超过 2 条。
示意图大家从后文找，还是比较直观的。
2.超图与SVM
超边可以做到同时连超过2个点。如果伙伴们研究过 SVM，超边的概念，犹如将软间隔定义成一条边。
3.超图与KNN
超边的建立有许多种方法，我们可以根据研究的问题特性来进行选择，这里我选择了KNN。假设图中每个节点都是一个菌种，每个节点的赋值内容则是一个包含有菌种各种信息的向量。我们通过计算比较各个菌种信息的Euclidean distance来给每一个节点选择个neighbour，并据此构建出一个包含（原节点也包含在内）的超边，然后对每个节点重复上述步骤，最后构建出一张完整的超图。总的来说，超图的建立是基于超边的建立，而超边的建立则是基于我们对节点之间关系的先验条件来实现的。在上面的问题中，我们选择用KNN+Euclidean distance的方式来赋予超边所代表的节点与节点之间的关系。
4.剪切 Normalized Hypergraph Cut
一个点的子集 S，如果其补集是 U。超图的剪切的含义，找到某种方式，将点集分为 S 和 U（S的补集）。如果超边，同时包含，S 和 U 中的点，则为一个剪切（存在性）。通俗地说，“可以在这个点剪切”，如果切开某个“剪切”，原来的超边也能够被分割开来。
参考
超图学习（Learning with hypergraphs）（一）
5.Ablation Study 消融实验
消融 的原意是通过手术切除身体组织。消融研究“Ablation study”一词起源于 20 世纪 60 年代和 70 年代的实验神经心理学领域，通过切除部分动物大脑来研究这对动物行为的影响。
在机器学习领域，尤其是复杂的深度神经网络中，“消融研究”被用来描述切除网络某些部分的过程，以便更好地了解网络的行为。
为了更好地了解该系统，作者进行了一项消融研究，移除系统的不同部分--例如，移除卷积神经网络的一个或两个全连接层，性能损失却出奇地小，这让作者得出以下结论：
Much of the CNN’s representational power comes from its convolutional layers, rather than from the much larger densely connected layers.
可以看出，消融实验的目的在于移除系统中的特定的部分，来控制变量式的研究这个部分对于系统整体的影响。如果去除这一部分后系统的性能没有太大损失，那么说明这一部分对于整个系统而言并不具有太大的重要性；如果去除之后系统性能明显的下降，则说明这一部分的设计是必不可少的。当然，如果出现了第三种情况，也就是去除之后模型的性能不降反升，那么建议找一下bug或者修改设计。
如果我们已经有一个模型，去除因素A，去除因素B，去除因素C，查看哪个因素作用最大。据说，针对深度神经网络，消融实验还是非常有效的。
参考
【论文精读】Lightgcn: Simplifying and powering graph convolution network for recommendation
一文搞懂什么是ablation study (消融实验）
6.LightGCN 图卷积网络
针对 LightGCN，能够进行协同过滤 Neural Graph Collaborative Filtering (NGCF)
NGCF 将 K+1 个特征拼接起来。相比之下，LightGCN 是非线性加权相加。
深圳大学课件
这篇文章还没看
7.拉姆齐数 Ramsey Number
定义A：拉姆齐数是组合数学和图论中的一个重要函数，用于描述在任意大结构中必然出现某种规律子结构的最小顶点数。
定义B：拉姆齐数（Ramsey number）是整个数学领域中最难计算的数。拉姆齐数源于拉姆齐理论（Ramsey Theory），它是数学中的一个分支，主要研究在一定条件下结构中存在的规律性或者秩序。其基本观点是，在足够大的结构中，一定会出现某种特定的子结构。这种理论最早是由英国数学家Frank P. Ramsey于20世纪初提出的，因此得名。
这是知乎的解释，还是比较清晰的。说到，Ramsey Number，R(2)=2, R(3)=6, R(4)=18, ... 因为上界是很难确定的，2023年被证明上界是指数级别的。
Ramsey Number 和【着色实验】息息相关。
8.着色实验
着色实验，是一种算法。算法的目标，就是把一堆无色的点，着色成红色或者蓝色。怎么着色呢？着色的方法是，正是在着色的这个点，连出去的点，红色多于蓝色，把蓝色着色成红色；如果连出去的点，蓝色多于红色，则红色着色成蓝色。
没有无色点的时候，至少有一种颜色有 K 个球，称为 Ramsey Number Upper 是 4^K。这 K 个点称为单色团。
参考
四位数学家发现了“拉姆齐数”的新上限
9.Ramsey Number 相关定理
第一，R(3,3)=6; R(3,4)=9; R(3,5)=16; R(4,4)=18; R(3,6)=18; R(3,7)=23。第二，R(3,t) 复杂度，现在被证明是 t^2/logt。第三，R(s,t) <= R(s-1,t) + R(s,t-1)-1。
目前找到的上限，R(2X)，X 有很大的下限。如果要找到比较确切下限，或者上限，要么算力够，要么非常完整的理论证明。
参考
Ramsey Number
四位数学家发现了“拉姆齐数”的新上限
这篇文章找到拉姆齐数下界
三位年轻中国学者合作的重磅成果在数学四大顶刊的《数学新进展》发表
这是南大的课件，我没怎么看
Ramsey Theory and Classical Graph Ramsey Numbe
10.书籍页面图
一本 5 页的书，可以记为 B(p)，阶数 5+2=7。
定义一个集合G，这个集合满足以下条件，特点是只有一个孤立点。条件我没看懂，主要是 Notation 不懂。
参考
The Turan Number of Book Graphs
11.Turan Number 图兰数
第一，极值图 ex() 表示“边的数目”，extremal graph。
第二，H-Free 不包含同构于集合 H 的子图，这个图称为 H-free。#注解：首先这个超图中存在某个子图，其次这个子图只有一个。
综上，如果一个 n 个顶点的 H-free 的图，称为极值图。ex(n,H) 是记号。更加有意思的是，这样的极值图中，边数的最大值为 Turan Number。
Erdos Gallai Theorem： ex(n,H) <= (n-1)(k-1)/2, 其中 k = min{ H }。我们自己给它一个名字“最小自由度”。这个定理还给出边数目的估计方法，ex(n,H) = (1-1/F)*C(n,2), where C(n,2) = 2!(n-1)!/n!。
Turan numbers of cycles plus a general graph
Regular Tur´an numbers
对于自由度集合 H，不包含 H 同构图。针对这类子集的构造，是有很多讨论的。比如，ex(n, K(r+1) ), ex(n, C(2k+1) ), ex(n, W(2k) )，等等。最近的讨论一直到 2024 年，ex(n, W(s,2k-1) )。
参考
Turan问题及其相关
12.Turan Density 图兰密度
定义，p(H) = ex(n, H) / C(n,2) when n turns to infinite.
NIFORM TURÁN DENSITIES OF k-UNIFORM HYPERGRAPHS
极值图论笔记
13.Erdos Problem 鄂尔多斯问题
这事儿聚焦于埃尔德什问题#339，这是著名数学家保罗・埃尔德什提出或转述的近千道问题之一，收录于erdosproblems.com网站。该网站记录了每道题目的当前状态，其中约三分之一已解决，大部分仍待解。
OpenAI 新闻
14.K-Uniform Hypergraph
超图的概念，超边组成的图，就是超图。
For a fixed integer k (k ≥ 3), let Gk(n,p) be a probability space consisting of k-uniform hypergraphs with n vertices, in which each element of C([n], k) occurring independently as an edge with probability p.
We show that there exists a positive constant K such that with high probability the following is true. If p > K/n, then every maximum Fank free subhypergraph of Gk(n,p) is k-partite for k ≥ 4; and if p > K(logn)γ/n, where γ > 0 is an absolute constant, then every maximum Fan3-free subhy pergraph of G3(n,p) is tripartite.
某些概率空间可能包含 K-均匀超图。K均匀超图含义（K>=3），如果某边以概率 P （P>K/n）出现，至多K个顶点都是独立地出现，和边的出现没有必然的联系。能保证这句话发生的图，称为 K-均匀超图。一定条件下，这种K-均匀超图，会成为这个超图的“自由子图”（H-free）。后面半句连续的情况没看懂，先放着。
参考
On k-uniform random hypergraphs without generalized fans
15.哈密尔顿圈
巡回售货员问题有一个基于图的天然类似问题，它是图论中的一个基本问题，给定一个有向图G(V，E)，如果G中的圈C恰好经过每一个顶点一次，则称圈C是一个哈密顿圈。换句话说，它构成一条经过所有顶点的、没有重复的“路线”。
自己总结：K 个顶点的集合，每个顶点只经过一次并且形成圈，没有一条边走两次。
通过和千问3.6对话，在一个图 G 中找到哈密尔顿圈，原因是哈圈具有非常良好的性质。如果某个哈圈子集 H 是唯一的，这个图 G 还是 H-Free 的。这个极值图的最大边数，即 Turan Number。
关于微分方程
16.分数阶微分方程
关于分数阶的微分方程。分数阶微分方程是涉及非整数阶导数和积分的微分方程，用于描述具有记忆效应和非局部特性的复杂系统。
17.分数阶微分
分数用 α 表示，泰勒展开的部分，不是有限项，而是无限项。这个时候，无限项二项式系数相加，可以写成 Gamma 函数 的形式。
w(j) = (-1)^j * ga(α+1)/[ ga(j+1) * ga(α-j+1) ]
某个分数阶的微分，可以用一个二项式无穷级数表示，而且权重就是 w(j)。
18.Grunwald Letnikov 定义
f(t) 的 α 阶导数
GL = h^(-α) * sum( w(j) * f(t-jh) ) when j is from 0 to [(t-t0)/h] and h->0.
参考
分数阶微积分：定义与计算
沪公安联网 31011502019103