数学系离散数学的几大核心领域

2019 年 5 月 17 日 算法与数学之美

数学系里一般不叫离散数学，一般都称为组合数学（Combinatorics）。这里注意一下，组合数学研究的对象不一定是离散的（比如graph limit theory中会研究一类连续函数的拓扑性质），我更愿意把组合数学称为具体数学（Concrete Math）。

我个人觉得，组合数学家里几乎没有专门为算法做理论设计的。算法的理论，一般属于理论计算机科学（Theoretical Computer Science），隶属于计算机系。

那组合数学家在做什么呢？美国数学会给组合数学分了五类：计数组合，编码与设计理论，图论，极值组合，代数组合。我个人认为这个分类已经过时了二十年了。我这里说一下我认为组合数学里最常见最核心的几个领域。因为水平所限，肯定会有不全或者错漏。

结构图论（Structural graph theory）与图的染色（Graph coloring）

我没有把图论分作一类，因为目前图论领域里明显有两类风格迥异的数学家。结构图论顾名思义，主要研究目标是图的结构，包括graph minor; graph immersion; topological graph theory; perfect graph等等很多分支。图的染色就是考虑确定图的染色数，或者用染色数为图分类。我把这两个方向放到一起，因为我觉得大部分做其中一个方向的数学家也做另外一个方向。

极值组合（Extremal combinatorics）与极值图论（Extremal graph theory）

极值组合研究的是满足某种条件下的一种结构的极限情况，极值图论研究的就是图了。这个方向也是组合目前最主流也是竞争最激烈的方向之一，包括Turan问题，Ramsey问题等等臭名昭著的难题。

代数组合（Algebraic combinatorics）

这个方向我了解的不多，因为和我个人taste不是很相符。有的组合学家不承认代数组合是组合的分支，因为有些代数组合的问题来源自抽象数学（Abstract Math），并不是具体数学。这里分支也有很多，比如组合交换代数，组合表示论等等。

算数组合（Arithmetic combinatorics）

这个领域比较广，一般认为包括加性组合（Additive Combinatorics）和乘性组合（Multiplicative Combinatorics）。很多我们耳熟能详的数学家比如陶哲轩，Bourgain等，都在这个领域做了很多贡献。狭义的说加性组合研究阿贝尔群上的组合结构，乘性组合研究一般群的结构。加性组合研究的问题比如Freiman type theorem；Pseudorandomness等；乘性组合的问题比如Approximate group；growth rate of group等。这个领域的用到的其他分支的数学比较多，包括图论，极值组合，概率，代数，调和分析，代数几何，离散几何，逻辑等。

计数组合（Enumeration combinatorics）与解析组合（Analytic combinatorics）

这里顾名思义就是使用代数/复分析等工具来计数了。注意并不是所有的计数问题都在这里，比如数平面图有多少个就属于计数组合问题，但是数没有三角形的最大的图的个数就属于极值组合。一般其他的数学分支，比如代数拓扑，常会用到的组合大多是这个分支。

离散几何（Discrete geometry）

这个领域和算数组合有点像，使用其他分支的工具也很多。比较著名的问题比如sphere packing；kissing number；equiangular lines等等。其中四维和24维sphere packing问题就是用代数几何解决的。这里还包含一个子分支重合几何（incidence geometry），主要研究点线面的关系的几何，这里面调和分析与极值组合用的会多一些，也是一个很新很热门的分支。有的人也会把重合几何叫代数组合几何（Algebraic combinatorial geometry），因为重合几何的一个主要研究对象也是多项式或者代数/半代数曲线。