組み合わせ論

列挙的組み合わせ論は、組み合わせ論の中で最も古典的な分野であり、特定の組み合わせオブジェクトの数を数えることに重点を置いています。集合内の要素の数を数えることはかなり広範な数学的問題ですが、応用で生じる問題の多くは、比較的単純な組み合わせ論的記述で表すことができます。フィボナッチ数は、列挙的組み合わせ論における問題の基本的な例です。12分割法は、順列、組み合わせ、分割を数えるための統一的な枠組みを提供します。

解析的組み合わせ論は、複素解析と確率論の手法を用いて組み合わせ構造を列挙する学問である。明示的な組み合わせ式や母関数を用いて結果を記述する列挙的組み合わせ論とは対照的に、解析的組み合わせ論は漸近的な公式を得ることを目的としている。

分割理論は、整数分割に関連するさまざまな列挙問題や漸近問題を研究する分野であり、 q級数、特殊関数、直交多項式と密接に関連しています。元々は数論と解析学の一部でしたが、現在では組み合わせ論の一部​​、あるいは独立した分野とみなされています。全単射アプローチや解析学および解析的数論におけるさまざまなツールを取り入れており、統計力学とも関連があります。分割はヤング図やフェラーズ図を用いて視覚的に表現できます。対称多項式や対称群の研究、そして一般的な群表現論など、数学や物理学の多くの分野に現れます。

グラフは組み合わせ論における基本的な対象です。グラフ理論の考察は、列挙（例： n個の頂点とk個の辺を持つグラフの数）から既存の構造（例：ハミルトン閉路）まで、代数的表現（例：グラフGと2つの数xとyが与えられたとき、Tutte多項式T _G ( x , y )は組み合わせ論的な解釈を持つか？）まで多岐にわたります。グラフ理論と組み合わせ論の間には非常に強い関連性がありますが、これらは別々の分野として考えられることもあります。^{[ 21 ]} 組み合わせ論的手法は多くのグラフ理論の問題に適用できますが、この2つの分野は一般的に異なるタイプの問題の解決策を探すために使用されます。

デザイン理論は、特定の交差特性を持つ部分集合の集合である組み合わせデザインを研究する分野です。ブロックデザインは、特殊なタイプの組み合わせデザインです。この分野は、 1850年にカークマンが提唱した女子生徒問題のように、組み合わせ論の中でも最も古い分野の一つです。この問題の解は、有限単純群の分類において重要な役割を果たすシュタイナー系の特殊なケースです。この分野は、符号理論や幾何学的組み合わせ論とも関連があります。

組み合わせ設計理論は、実験計画の分野に応用できます。組み合わせ設計の基本理論の一部は、統計学者ロナルド・フィッシャーによる生物学的実験の設計に関する研究に由来しています。現代の応用例は、有限幾何学、トーナメントスケジューリング、宝くじ、数理化学、数理生物学、アルゴリズム設計と解析、ネットワーク、グループテスト、暗号など、幅広い分野に見られます。^{[ 22 ]}

有限幾何学とは、有限個の点のみを持つ幾何学的システムを研究する分野です。連続幾何学（ユークリッド平面、実射影空間など）に見られる構造に類似していますが、組み合わせ論的に定義された構造が主な研究対象です。この分野は、設計理論のための豊富な事例を提供します。離散幾何学（組み合わせ幾何学）と混同しないように注意が必要です。

順序理論は、有限および無限の半順序集合を研究する分野です。「これはあれより小さい」や「これはあれより前にある」といった命題を記述するための形式的な枠組みを提供します。半順序の様々な例は、代数学、幾何学、数論、そして組み合わせ論やグラフ理論の至るところに現れます。半順序の代表的なクラスや例としては、束やブール代数などが挙げられます。

マトロイド理論は幾何学の一部を抽象化したものです。これは、線形従属関係における特定の係数に依存しない、ベクトル空間内のベクトルの集合（通常は有限集合）の性質を研究します。構造だけでなく、列挙的な性質もマトロイド理論に含まれます。マトロイド理論はハスラー・ホイットニーによって導入され、順序理論の一部として研究されました。現在では、組み合わせ論の他の分野と多くの関連性を持つ独立した研究分野となっています。

極値組み合わせ論は、有限オブジェクト（数、グラフ、ベクトル、集合など）の集合が、特定の制約を満たす場合に、どれだけ大きく、あるいは小さくなり得るかを研究する学問です。極値組み合わせ論の多くは集合系のクラスに関係しており、これは極値集合論と呼ばれます。例えば、n個の要素からなる集合において、互いに交差するk個の要素からなる部分集合の最大数はいくつでしょうか？また、他のどの部分集合も含まない部分集合の最大数はいくつでしょうか？後者の問いは、極値集合論の多くを生み出したスペルナーの定理によって答えられます。

このケースで扱われる質問の種類は、特定の性質を満たす最大のグラフに関するものです。たとえば、2n 個の頂点を持つ最大の三角形を含まないグラフは、完全二部グラフK _n,nです。多くの場合、極値f ( n ) を正確に見つけることさえ難しく、漸近的な推定値しか与えることができません。

ラムゼー理論は極値組み合わせ論の一分野である。この理論によれば、十分に大きな配置には必ず何らかの秩序が存在する。これは鳩の巣原理の高度な一般化である。

確率的組み合わせ論では、次のような問題が問われます。ランダムな離散オブジェクト（例えばランダムグラフ）の特定の性質の確率はどれくらいか？例えば、ランダムグラフにおける三角形の平均数はどれくらいか？確率的手法は、特定の規定された性質を持つ組み合わせオブジェクトの存在を判定するためにも使用されます（明示的な例を見つけるのが難しい場合もあります）。これは、それらの性質を持つオブジェクトをランダムに選択する確率が 0 より大きいことを観察することによって行われます。このアプローチ（しばしば確率的手法と呼ばれます）は、極値組み合わせ論やグラフ理論への応用において非常に効果的であることが証明されています。密接に関連する分野は、有限マルコフ連鎖の研究、特に組み合わせオブジェクトに関する研究です。ここでも、混合時間を推定するために確率的手法が使用されます。

確率的組み合わせ論は、この分野の先駆者であるポール・エルデシュと関連付けられることが多いが、従来は組み合わせ論の他の分野における問題を研究するためのツール群として捉えられていた。しかし近年、この分野は独立した組み合わせ論の分野へと発展した。

代数的組み合わせ論は、抽象代数学の手法、特に群論と表現論を様々な組み合わせ論的文脈で用い、逆に、組み合わせ論的手法を代数学の問題に応用する数学の分野である。代数的組み合わせ論は、組み合わせ論的手法と代数的手法の相互作用が特に強く重要な数学の分野として、より広義に捉えられるようになってきている。したがって、組み合わせ論的トピックは列挙的な性質を持つ場合もあれば、マトロイド、多面体、半順序集合、有限幾何学を含む場合もある。代数的側面では、群論と表現論に加えて、束論と可換代数が一般的である。

語の組み合わせ論は形式言語を扱う分野である。数論、群論、確率論など、数学のいくつかの分野で独立して発展してきた。列挙組み合わせ論、フラクタル解析、理論計算機科学、オートマトン理論、言語学などに応用されている。多くの応用例は新しいものだが、形式文法のクラスに関する古典的なチョムスキー＝シュッツェンベルガー階層は、おそらくこの分野で最もよく知られた成果であろう。

幾何学的組み合わせ論は、凸幾何学および離散幾何学と関連しています。例えば、凸多面体が各次元にいくつの面を持つことができる か、といった問題を扱います。多面体の計量特性も重要な役割を果たしており、例えば、凸多面体の剛性に関するコーシーの定理などが挙げられます。また、順列多面体、結合多面体、バーコフ多面体といった特殊な多面体も考察対象となります。組み合わせ幾何学は、離散幾何学の歴史的な名称です。

幾何学的組み合わせ論には、多面体組み合わせ論（凸多面体の面の研究）、凸幾何学（凸集合の研究、特にそれらの交差の組み合わせ論）、離散幾何学など、多くの下位分野が含まれます。離散幾何学は、計算幾何学に多くの応用があります。正多面体、アルキメデス立体、キス数などの研究も、幾何学的組み合わせ論の一部​​です。また、順列多面体、結合多面体、バーコフ多面体などの特殊な多面体も考慮されます。

グラフ彩色、公平分割、分割、半順序集合、決定木、ネックレス問題、離散モース理論などの研究には、トポロジーにおける概念や手法の組み合わせ論的類似物が用いられる。これは、代数トポロジーの古い名称である組み合わせトポロジーと混同してはならない。

算術組み合わせ論は、数論、組み合わせ論、エルゴード理論、調和解析の相互作用から生まれた。これは、算術演算（加算、減算、乗算、除算）に関連する組み合わせ的推定に関するものである。加法数論（加法組み合わせ論とも呼ばれる）は、加算と減算の演算のみが関係する特殊な場合を指す。算術組み合わせ論における重要な手法の一つは、力学系のエルゴード理論である。

無限組み合わせ論、または組み合わせ集合論は、組み合わせ論の概念を無限集合に拡張したものです。これは数理論理学の一分野である集合論の一部ですが、集合論と極値組み合わせ論の両方のツールと概念を使用します。研究対象には、連続グラフと木、ラムゼーの定理の拡張、マーティンの公理などがあります。最近の発展は、連続体の組み合わせ論^{[ 23 ]}と特異基数の後継者の組み合わせ論^{[ 24 ]}に関するものです。

ジャン＝カルロ・ロータは、数えることと測度の間に多くの類似点があることから、幾何学的確率を説明するために連続組み合わせ論^{[ 25 ]}という名前を使用しました。

組み合わせ最適化とは、離散的かつ組み合わせ的な対象に対する最適化を研究する分野である。当初は組み合わせ論とグラフ理論の一部として始まったが、現在では応用数学およびコンピュータ科学の一分野とみなされており、オペレーションズリサーチ、アルゴリズム理論、計算複雑性理論と関連している。

符号理論は、初期の組み合わせ論的手法による誤り訂正符号の構築から始まった設計理論の一部です。この分野の主な目的は、効率的かつ信頼性の高いデータ伝送方法を設計することです。現在では、情報理論の一部である広範な研究分野となっています。

離散幾何学（組合せ幾何学とも呼ばれる）もまた、凸多面体やキス数に関する初期の成果から、組合せ論の一部​​として始まった。離散幾何学が計算幾何学に応用されるようになると、これら二つの分野は部分的に融合し、独立した研究分野となった。幾何学的組合せ論や位相的組合せ論との関連性は依然として多く、これらの分野自体も初期の離散幾何学の発展形と見なすことができる。

力学系の組み合わせ論的側面は、新たな研究分野として注目されています。ここでは、力学系は組み合わせ論的な対象に基づいて定義されます。例えば、 グラフ力学系を参照してください。

組み合わせ論と物理学、特に統計物理学との相互作用はますます強まっている。例としては、イジングモデルの厳密解や、ポッツモデルと彩色多項式およびタット多項式との関連性などが挙げられる。