數學(xué)系里一般不叫離散數學(xué)，一般都稱(chēng)為組合數學(xué)（Combinatorics）。這里注意一下，組合數學(xué)研究的對象不一定是離散的（比如graph limit theory中會(huì )研究一類(lèi)連續函數的拓撲性質(zhì)），我更愿意把組合數學(xué)稱(chēng)為具體數學(xué)（Concrete Math）。
我個(gè)人覺(jué)得，組合數學(xué)家里幾乎沒(méi)有專(zhuān)門(mén)為算法做理論設計的。算法的理論，一般屬于理論計算機科學(xué)（Theoretical Computer Science），隸屬于計算機系。
那組合數學(xué)家在做什么呢？美國數學(xué)會(huì )給組合數學(xué)分了五類(lèi)：計數組合，編碼與設計理論，圖論，極值組合，代數組合。我個(gè)人認為這個(gè)分類(lèi)已經(jīng)過(guò)時(shí)了二十年了。我這里說(shuō)一下我認為組合數學(xué)里最常見(jiàn)最核心的幾個(gè)領(lǐng)域。因為水平所限，肯定會(huì )有不全或者錯漏。
結構圖論（Structural graph theory）與圖的染色（Graph coloring）
我沒(méi)有把圖論分作一類(lèi)，因為目前圖論領(lǐng)域里明顯有兩類(lèi)風(fēng)格迥異的數學(xué)家。結構圖論顧名思義，主要研究目標是圖的結構，包括graph minor; graph immersion; topological graph theory; perfect graph等等很多分支。圖的染色就是考慮確定圖的染色數，或者用染色數為圖分類(lèi)。我把這兩個(gè)方向放到一起，因為我覺(jué)得大部分做其中一個(gè)方向的數學(xué)家也做另外一個(gè)方向。
極值組合（Extremal combinatorics）與極值圖論（Extremal graph theory）
極值組合研究的是滿(mǎn)足某種條件下的一種結構的極限情況，極值圖論研究的就是圖了。這個(gè)方向也是組合目前最主流也是競爭最激烈的方向之一，包括Turan問(wèn)題，Ramsey問(wèn)題等等臭名昭著(zhù)的難題。
代數組合（Algebraic combinatorics）
這個(gè)方向我了解的不多，因為和我個(gè)人taste不是很相符。有的組合學(xué)家不承認代數組合是組合的分支，因為有些代數組合的問(wèn)題來(lái)源自抽象數學(xué)（Abstract Math），并不是具體數學(xué)。這里分支也有很多，比如組合交換代數，組合表示論等等。
算數組合（Arithmetic combinatorics）
這個(gè)領(lǐng)域比較廣，一般認為包括加性組合（Additive Combinatorics）和乘性組合（Multiplicative Combinatorics）。很多我們耳熟能詳的數學(xué)家比如陶哲軒，Bourgain等，都在這個(gè)領(lǐng)域做了很多貢獻。狹義的說(shuō)加性組合研究阿貝爾群上的組合結構，乘性組合研究一般群的結構。加性組合研究的問(wèn)題比如Freiman type theorem；Pseudorandomness等；乘性組合的問(wèn)題比如Approximate group；growth rate of group等。這個(gè)領(lǐng)域的用到的其他分支的數學(xué)比較多，包括圖論，極值組合，概率，代數，調和分析，代數幾何，離散幾何，邏輯等。
計數組合（Enumeration combinatorics）與解析組合（Analytic combinatorics）
這里顧名思義就是使用代數/復分析等工具來(lái)計數了。注意并不是所有的計數問(wèn)題都在這里，比如數平面圖有多少個(gè)就屬于計數組合問(wèn)題，但是數沒(méi)有三角形的最大的圖的個(gè)數就屬于極值組合。一般其他的數學(xué)分支，比如代數拓撲，常會(huì )用到的組合大多是這個(gè)分支。
離散幾何（Discrete geometry）
這個(gè)領(lǐng)域和算數組合有點(diǎn)像，使用其他分支的工具也很多。比較著(zhù)名的問(wèn)題比如sphere packing；kissing number；equiangular lines等等。其中四維和24維sphere packing問(wèn)題就是用代數幾何解決的。這里還包含一個(gè)子分支重合幾何（incidence geometry），主要研究點(diǎn)線(xiàn)面的關(guān)系的幾何，這里面調和分析與極值組合用的會(huì )多一些，也是一個(gè)很新很熱門(mén)的分支。有的人也會(huì )把重合幾何叫代數組合幾何（Algebraic combinatorial geometry），因為重合幾何的一個(gè)主要研究對象也是多項式或者代數/半代數曲線(xiàn)。
編碼理論（Coding theory）與設計（Design）
我對這個(gè)幾乎不了解。但是確實(shí)也是組合的一大主流分支。20世紀著(zhù)名的科克曼女生問(wèn)題就是這個(gè)領(lǐng)域的問(wèn)題。
▼▼▼更多驚喜點(diǎn)擊
聯(lián)系客服
