組合せ論における独立理論

『組合せ論における独立理論：グラフと横断への応用に関する入門書』は、マトロイド理論に関する学部レベルの数学教科書です。Victor Bryant とHazel Perfectによって執筆され、1980 年に Chapman & Hall から出版されました。

組合せ論における独立性理論の主なテーマは抽象の統一性、特にマトロイド理論が数学のさまざまな分野に由来する独立性の概念を統一する方法です。^[1] 5つの章から成り、最初の章ではグラフ理論、組合せ論、線型代数の基本的な定義を提供し、2番目の章ではマトロイドを定義して紹介します。この本では「独立空間」と呼ばれています。^{[2]名前が示すように、これらは主に独立集合を通じて定義されますが、回路、}マトロイドランク、サブモジュラー集合関数を使用した定義との同値性も示され、マトロイドの和、マイナー、切り捨て、デュアルも示されています。^[3]

第3章では、グラフィックマトロイド、グラフ内の全域木のマトロイド^[2]、および最小全域木の貪欲アルゴリズム^[3]について説明します。第4章には、二部グラフのマッチングの観点から説明できる横断マトロイドに関する資料が含まれており、マッチング理論と、ホールの結婚定理、メンガーの定理（グラフ内の最小カットと最大セットの分離パスの同値性）、ラテン方陣、ガモイド[ ^2]などの関連トピックに関する追加資料が含まれています。^[3]最後の章では、ベクトル空間での線形独立性を使用したマトロイド表現^[2]について説明します。これは付録としてラベル付けされ、証明は少なくなっています。^{[1] [3] [4]}

さまざまな難易度の練習問題がヒントと解答付きで多数含まれています。^{[1] [2] [3]}

テキストのレベルは、上級学部生や修士課程の学生向けのコースに適しており^[1]、基本的な線形代数のみを前提としており^{[2] 、 [4] [5]}、マトロイド理論に関する他のテキストよりもアクセスしやすく一般的なレベルで内容をカバーしています。^{[3] [4] [6]}本書が幾何学的格子という関連トピックを省略した選択には同意しませんが、レビュアーのドミニク・ウェルシュは、これを「組合せ理論の学部コースに最適なテキスト」と呼んでいます。^[2]マイケル・J・ガンリーも同様に、これを「非常に難しい主題への非常に良い入門書」と呼んでいます。^[4]

しかし、査読者の W. Dörfler は、この本は実用的な応用を十分にカバーしておらず、適切な参考文献も欠けていると不満を述べています。^[3] Bernhard Korteによる別の不満は、本のタイトルが誤解を招くものであることです。「独立空間」は、抽象的な単体複合体をより一般的に指すことが多いのに対し、この本はマトロイドに特化しています。Korte はまた、組み合わせ最適化への応用と格子理論とのつながりがカバーされていないという他の査読者の不満に同意しています。 ^[5]