A Course in Combinatorics（組合せ論講義）

引用

van Lint, J. H., & Wilson, R. M. (2001). A Course in Combinatorics (2nd ed.). Cambridge University Press.

章の要約

第2版は短い38の章からなり、両版の序文が前に置かれ、文献一覧と索引が後に続く。印刷版は約600ページである。ケンブリッジ大学出版局は、本書を、物をどう並べ分配するかの方法についての本で、幾何・代数・解析の考え方が関わり、グラフ理論、極値問題、デザイン、彩色、符号を統一的に扱い、上級学部生または大学院初年次の授業に向くと説明している。各章は主題で題が付けられており、以下の分類は目次の順に従う。

第1–4章：グラフ；木；グラフの彩色とラムゼーの定理；トゥランの定理と極値グラフ

本書は基本的なグラフ理論と木から始まり、すぐに彩色、ラムゼーの定理、トゥランの定理に代表される極値問題へ進む。

第5–9章：相異代表系；ディルワースの定理と極値集合論；ネットワークのフロー；ド・ブラウン列；二つの(0, 1, ⋆)問題：グラフのアドレス付けとハッシュ符号化方式

これらの章は、相異代表系、ディルワースの定理と極値集合論、ネットワークのフロー、ド・ブラウン列、そしてグラフのアドレス付けとハッシュ符号化方式をめぐる一対の問題を扱う。

第10–12章：包除原理と反転公式；パーマネント；ファン・デル・ヴェルデン予想

数え上げの流れは包除原理から始まり、次にパーマネントと、それに関するファン・デル・ヴェルデン予想へ進む。

第13–15章：基本的な数え上げとスターリング数；漸化式と母関数；分割

数え上げの技法は、スターリング数、漸化式、母関数、分割へと続く。

第16–18章：(0, 1)行列；ラテン方陣；アダマール行列とリード–マラー符号

次のまとまりは、0と1からなる行列、ラテン方陣、アダマール行列を扱い、リード–マラー符号で終わる。

第19–23章：デザイン；符号とデザイン；強正則グラフと部分幾何；直交ラテン方陣；射影幾何と組合せ幾何

ここで本書は中心となる構造を集める。デザインと符号の関係、強正則グラフと部分幾何、直交ラテン方陣、射影幾何と組合せ幾何である。

第24–26章：ガウス数とq類似；束とメビウス反転；組合せデザインと射影幾何

このまとまりは、q類似、束とメビウス反転、そして組合せデザインと射影幾何への再訪を扱う。

第27–31章：差集合と自己同型；差集合と群環；符号と対称デザイン；アソシエーションスキーム；グラフ理論における（さらなる）代数的手法

代数的なまとまりは、差集合、群環、対称デザインと符号、アソシエーションスキーム、そしてグラフ理論におけるさらなる代数的方法を扱う。

第32–36章：グラフの連結性；平面性と彩色；ホイットニーの双対性；曲面へのグラフの埋め込み；電気回路網と正方形分割

最後のグラフ理論のまとまりは、連結性、平面性と彩色、双対性、曲面への埋め込み、そして電気回路網と正方形の正方形分割の問題を扱う。

第37–38章：ポリアの数え上げ理論；バラニャイの定理

本書はポリアの数え上げ理論とバラニャイの定理で終わる。

主要概念

第1–18章：グラフ、極値問題、数え上げ

• ラムゼー理論と極値グラフ：ラムゼーの定理とトゥランの定理（第3–4章）。
• 包除原理とパーマネント：第10–12章。
• 母関数と分割：第13–15章。
• ラテン方陣とアダマール行列：第17–18章。

第19–38章：デザイン、符号、幾何、さらなるグラフ理論

• デザイン、符号、アソシエーションスキーム：第19–20章、第29章、第30章。
• 強正則グラフ、差集合、群環：第21、27、28章。
• 平面性、双対性、グラフの埋め込み：第33–35章。
• ポリアの数え上げとバラニャイの定理：第37–38章。

批判的分析

長所

• 短い章で示される幅広さ。 38のコンパクトな章が、この分野の広い地図を与える。ケンブリッジはこれをグラフ理論、極値問題、デザイン、彩色、符号の統一的な扱いとして紹介している。ディーター・ユングニッケルはZentralblatt MATHの書評で、組合せ論の教科書の標準的な選択肢になるだろうと見込んだ。
• 優雅な証明と良い問題。 『Mathematical Gazette』は、優雅な証明と心をそそる例の源だと評する。ケンブリッジが引用する別の書評は、興味深い問題、具体的な例、有用な注と参考文献が豊富だと述べる。
• 二つのレベルで役立つ。 ケンブリッジが引用するEMS名義の書評は、組合せ論を学ぶどの学生にも薦められ、その広さゆえに研究者にも新しいことを多く教えてくれると述べる。
• 代数と幾何の考え方が並ぶ。 目次では、符号、デザイン、有限幾何、群環、アソシエーションスキームが一冊に収まり、学生は同じ構造を複数の側面から見ることができる。

短所

• 要求が高い。 『Mathematical Gazette』の書評は、この本を易しいと感じる人はいないだろうと述べ、臆面もなく、しかも印象的に数学的だと評している。著者が想定する読者は上級学部生か大学院の初学者である。
• 単一の筋ではない。 章は連続した議論ではなく主題ごとに並ぶので、第1章から第38章まで一本の筋はない。読者は自分でルートを選ぶ必要がある。
• 前提知識が一様でない。 初めの章は離散数学の授業以外ほとんど要らないが、代数的な章（群環、アソシエーションスキーム）は、読者がすでにもっている抽象代数を前提とする。

コースにおける位置づけ

他は入門課程が中心の書目のなかで、本書は高度な組合せ論の一冊である。Susanna Epp の『Discrete Mathematics with Applications』、Kenneth Rosen の『Discrete Mathematics and Its Applications』、Oscar Levin のオープン教科書は、初めてこの種の数学に触れる読者に、論理、証明、数え上げ、グラフを教える。Lovász、Pelikán、Vesztergombi の『Discrete Mathematics: Elementary and Beyond』は、問題を軸にした短い入門書で、本書の前に読むのが自然である。Graham、Knuth、Patashnik の『Concrete Mathematics』は母関数と漸化式で重なるが、アルゴリズムの解析を志向する。これに対して van Lint と Wilson は、デザイン、符号、有限幾何に傾く。

本書の使い方

離散数学の授業と線形代数の最初の授業を終えた上級学部生や大学院生に向く。後半の章では抽象代数の知識が役立つ。

• 中核ルート： グラフと極値問題の第1–4章、数え上げの第10–15章、デザインと符号の第19・20章で、自己完結した最初の授業になる。
• 代数ルート： 強正則グラフ、幾何、差集合、アソシエーションスキームを扱う第21・23・27–30章は、抽象代数を知る読者に報いる。
• グラフ理論ルート： 第32–36章は、連結性、平面性、曲面についての二つ目のグラフ理論の授業になる。
• 演習： 章が短く独立性が高いので、週に一章ずつ読むことも、順不同で読むこともできる。問題に取り組み、評者が称賛する注と参考文献をたどるとよい。