7931のあたまんなか

数学/読書メモ/自分の考え方/水曜どうでしょう/交通関係(道路・航空)など、頭の中にあることを書き出しています。

連載「組合せ数学の雑記帳」~『数学セミナー』読書メモ

数学セミナー』では2019年4月から、連載「組合せ数学の雑記帳」(八森正泰)が始まりました。

この記事では、連載の内容のメモを毎号追記していきます。

私は学生時代に組合せ論に興味を持った時期があり、この連載はとても楽しみです。 *1

【第1回 - 2019年4月号】超平面の切り分ける領域の個数はいくつ?

d 次元空間を n 枚の超平面で切り分けるときにできる領域の個数  f_d(n) を考えるのが今回のテーマです。

d=3 の場合が、2019年度の東京工業大学の入試問題で扱われています。

amathnojaku.livedoor.blog

いくつかの専門用語が出てきますが、高校生でも十分理解できる内容だと思います。

頭の中で超平面を少しずつ動かすイメージができて楽しい記事です。

キーワード

  • 空間上のいくつかの点が一般の位置にある/縮退している
  • 超平面:d-1 次元のアフィン部分空間
  • 直線配置/平面配置/超平面配置(それぞれ d=2 / d=3 / 一般の d の場合)
  • シュレフリの式:  f_d(n) を d と n で書いた式

【第2回 - 2019年5月号】包除原理,半順序集合,そして再び超平面配置

高校数学でベン図とともに出てくる  |A \cup B| = |A| + |B| - |A \cap B| を一般化した公式(包除原理)からスタートします。

包除原理を部分集合どうしの包含関係(半順序関係の一例)を使って見直し、メビウスの反転公式を導きます。

最後に、前回の超平面配置について再考します。超平面( d-1 次元アフィン部分空間)とその交わりがなす頂点などのアフィン部分空間を、半順序集合の元と見ることになります。

キーワード

  • 包除原理(包含排除の原理とも呼ばれる)
  • 集合 E のべき集合  2^E : E の部分集合すべてからなる集合
  • 順序関係と半順序集合(poset)
  • ハッセ図:順序関係を図式化したもの
  • ランク n のブール束  B_n : n 元集合のべき集合のなす半順序集合
  • 階層的な半順序集合に定められるランク関数:集合の位数  | \cdot | の拡張に見える。
  • メビウス関数とメビウスの反転公式
  • ザスラフスキーの定理:超平面配置がなす領域数を与える公式
    • 超平面配置から半順序集合が得られ、アフィン空間の次元を加味すると得られる。

【第3回 - 2019年6月号】マトロイドと有向マトロイド

マトロイドとは、有限集合上の集合族で、ある3つの条件を満たすものを言います。

この条件を読むと、「集合に1点を加える(または除く)」という操作がポイントのようです。

マトロイドの2つの集合が連続変形できるとか、順序関係で極大な要素は基底と呼ばれるとか、双対を持つとか、集合・位相・線形代数でよく出てくる用語が記事の中に登場します。

実際、マトロイドはベクトル空間の一次独立性の抽象化と説明されることが多いようです。
記事を慎重に読み進めていくと、この説明は納得できました。

そして、マトロイドの構造に符号の情報を追加したものが有向マトロイドと呼ばれ、この連載の第1~2回で出てきた超平面配置につながっていると説明されています。

【第4回 - 2019年7月号】グラフのON/OFFゲームと計算量の話

グラフ *2 上の頂点をランプに見立てて、「一定のルールに従ってON/OFFすることでランプをすべて消す」というON/OFFゲームが扱われています。

与えられたグラフに対して、「どのような開始状態でも、最終的にランプをすべて消すことができるか?」が今回の主要な問題です。

この問題に対する答えの導き方が記事の前半で説明されています。この説明は難しい数学を使うことなく、ある意味で数学パズルのように理解できます。


そこから考察を進めると、2元体  \mathbb{F}_2 上の線形代数に帰着されることが後半に書かれています。

これは『数学ガールの秘密ノート/行列が描くもの』の研究問題に出てくる隣接行列に関係するようです。 *3 この関係については、個人的に興味があるので、手を動かして計算してみたいテーマです。

記事の中盤では、ON/OFF問題を例とした計算量とP≠NP問題について書かれています。PとNPの対になるcoNPという概念もあるようです。

最後には、前回記事のマトロイドとの関係が言及されています。


今回までで、超平面配置/マトロイド/ON/OFF問題が深いところでそれぞれが関係しあっていることが示唆されています。今後が楽しみです!

【第5回 - 2019年8月号】曲がったものをまっすぐにすること

第3回で出てきた超平面配置から考えを進めるところから始まります。

手書きで図を書いてみました。

https://lh3.googleusercontent.com/wvsRZ3lEz4-uPCRC2Noc7GNbYzQweuB-tcEigNZbQTrWu-t8Vib3UPEJikt2NIXIm060nqZT8-YSespDmUzEDjRiRs_fvxlCPVY83cbfaLYxfrXKdPwj4djErtFUKgVmmMKOo5xVbVcQYVGymLeDEUKfQp6lQzq98jH5klPwF91slv5Z49WtEqC0fPnYts67KxdYkgu6cY8__cXEUbUZhvPEmsxZ_Zx8smScJIefdlCW5XAMHV4_cnfF4X4sdRoPNEXVvyt-nNDYyvw6Fwb_jZhn_IFBSiBeAOHXaD0m9eCpX_vygGJBsAHJu9bFolhXVo-mpsPBiTyu9O4BTkpPZ_BpXGD7S6dCkxWrmKPlqvja6xycd1-hM16RM3LDKW7ko0ze0xxcKaO-AtQK7Cl73-BQwhm-a8dlx4A2VSFTtHEzKxe2z280neBy0UJRe9zEP21JTSKV-eiRvZNIoYlq36GG2yHd2waUY71GVkQ3PbPn_49fk35UWlqM4zV5TOysARpR4eZCA7zzYP5xWsC1p2A19a2skRDRa9uRO7LSjjznJcrqLRr3ihajK6PSHcmpB9hlfzDWpG4mAW88-43EqYCKPuh1z71agk9SCvn8JEdGG1Wrz2L4RRItyZ3CAhJl8r-Q2EN9_scDVpMdrwwQbXIO5uOL61wu=w889-h625-no

この図にある伸張可能性問題の計算量を考えるのが今回の主題です。

使う道具は3SATと呼ばれるNP完全問題

…私には難しくて、中盤以降は読み解けませんでした。残念。

*1:専門にしていた表現論関係のセミナーや講演で、ヤング図形と組合せ論の関係がテーマのものが多く、興味を持ちました。あのテトリスのようなヤング図形が、単純に馴染み深く思えたのかもしれません。

*2:頂点と辺がなす集合

*3:細かく言うと、隣接行列+単位行列になる?