數學系里一般不叫離散數學，一般都稱為組合數學（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），因為重合幾何的一個主要研究對象也是多項式或者代數/半代數曲線。

• 編碼理論（Coding theory）與設計（Design）

我對這個幾乎不了解。但是確實也是組合的一大主流分支。20世紀著名的科克曼女生問題就是這個領域的問題。

文章來源：算數學苑

IEEE Spectrum

《科技縱覽》

官方微信公眾平臺