連載「組合せ数学の雑記帳」～『数学セミナー』読書メモ
『数学セミナー』では2019年4月から、連載「組合せ数学の雑記帳」（八森正泰）が始まりました。
![数学セミナー 2019年 04 月号 [雑誌]](https://images-fe.ssl-images-amazon.com/images/I/41koKRDZ5oL._SL160_.jpg "数学セミナー 2019年 04 月号 [雑誌]")
- 作者:
- 出版社/メーカー: 日本評論社
- 発売日: 2019/03/12
- メディア: 雑誌
この記事では、連載の内容のメモを毎号追記していきます。
私は学生時代に組合せ論に興味を持った時期があり、この連載はとても楽しみです。 *1
【第1回 - 2019年4月号】超平面の切り分ける領域の個数はいくつ？
d 次元空間を n 枚の超平面で切り分けるときにできる領域の個数 を考えるのが今回のテーマです。
d=3 の場合が、2019年度の東京工業大学の入試問題で扱われています。
いくつかの専門用語が出てきますが、高校生でも十分理解できる内容だと思います。
頭の中で超平面を少しずつ動かすイメージができて楽しい記事です。
キーワード
- 空間上のいくつかの点が一般の位置にある／縮退している
- 超平面：d-1 次元のアフィン部分空間
- 直線配置／平面配置／超平面配置（それぞれ d=2 ／ d=3 ／ 一般の d の場合）
- シュレフリの式：
を d と n で書いた式
【第2回 - 2019年5月号】包除原理，半順序集合，そして再び超平面配置
高校数学でベン図とともに出てくる を一般化した公式（包除原理）からスタートします。
包除原理を部分集合どうしの包含関係（半順序関係の一例）を使って見直し、メビウスの反転公式を導きます。
最後に、前回の超平面配置について再考します。超平面（ d-1 次元アフィン部分空間）とその交わりがなす頂点などのアフィン部分空間を、半順序集合の元と見ることになります。
【第3回 - 2019年6月号】マトロイドと有向マトロイド
マトロイドとは、有限集合上の集合族で、ある3つの条件を満たすものを言います。
この条件を読むと、「集合に1点を加える(または除く)」という操作がポイントのようです。
マトロイドの2つの集合が連続変形できるとか、順序関係で極大な要素は基底と呼ばれるとか、双対を持つとか、集合・位相・線形代数でよく出てくる用語が記事の中に登場します。
実際、マトロイドはベクトル空間の一次独立性の抽象化と説明されることが多いようです。
記事を慎重に読み進めていくと、この説明は納得できました。
そして、マトロイドの構造に符号の情報を追加したものが有向マトロイドと呼ばれ、この連載の第1～2回で出てきた超平面配置につながっていると説明されています。
【第4回 - 2019年7月号】グラフのON/OFFゲームと計算量の話
グラフ *2 上の頂点をランプに見立てて、「一定のルールに従ってON/OFFすることでランプをすべて消す」というON/OFFゲームが扱われています。
与えられたグラフに対して、「どのような開始状態でも、最終的にランプをすべて消すことができるか？」が今回の主要な問題です。
この問題に対する答えの導き方が記事の前半で説明されています。この説明は難しい数学を使うことなく、ある意味で数学パズルのように理解できます。
そこから考察を進めると、2元体 上の線形代数に帰着されることが後半に書かれています。
これは『数学ガールの秘密ノート／行列が描くもの』の研究問題に出てくる隣接行列に関係するようです。 *3 この関係については、個人的に興味があるので、手を動かして計算してみたいテーマです。
記事の中盤では、ON/OFF問題を例とした計算量とP≠NP問題について書かれています。PとNPの対になるcoNPという概念もあるようです。
最後には、前回記事のマトロイドとの関係が言及されています。
今回までで、超平面配置／マトロイド／ON/OFF問題が深いところでそれぞれが関係しあっていることが示唆されています。今後が楽しみです！
【第5回 - 2019年8月号】曲がったものをまっすぐにすること
第3回で出てきた超平面配置から考えを進めるところから始まります。
手書きで図を書いてみました。
この図にある伸張可能性問題の計算量を考えるのが今回の主題です。
使う道具は3SATと呼ばれるNP完全問題。
…私には難しくて、中盤以降は読み解けませんでした。残念。
