前回第9回にシェラブルな単体的複体について紹介したのですが、 この第10回はこの続きになる話で、シェラブルかシェラブルでないかの境目は 結構難しい、という話です。
まず、前回に少し、単体的複体がシェラブルだとそのトポロジーはきれいなものに限定される、 というようなことに触れていましたが、 その顕著な、簡単な例としては、2次元曲面の三角形分割を考えると、 2次元球面の三角形分割はすべてシェラブル、球面以外の2次元曲面だとどのように三角形分割しても シェラブルにはなりません。 球面以外の2次元曲面の三角形分割がシェラブルにならないということは、 シェリングに沿ってオイラー標数の変化を見ていくことで、球面以外の曲面のオイラー標数は 実現できないことが分かるという仕組みで示すことができます。 同様に、高次元の多様体の三角形分割の場合も、シェラブルなら球面に限られるということが 簡単に示されます。
ここからが高次元の場合には難しいことになっていて、 2次元の場合は球面の三角形分割は必ずシェラブルになるのですが、3次元以上だと、 球面の三角形分割でもシェラブルにならないことがあるのです。 その代表例が、PLでない球面です。PLというのは区分的線形(Piesewise Linear)という意味で、 PL球面というのは、標準的な単体の境界との間に区分的線形な同相写像を持つように 三角形分割された球面のことです。 実は、シェリングに沿って帰納的に確認していくことで、球面の三角形分割がシェラブルであると、 それは必ずPL球面でなければならないことが分かります。 一方、5次元以上の球面に対してはPLでない三角形分割が存在することが知られています。 このことから、それらはシェラブルでないことということになります。
3次元の球面の場合は、任意の三角形分割がPLであることが知られているのですが、実は3次元球面 でもシェラブルでない三角形分割が存在します。 その代表的な構成法は、結び目を用いる方法です。 三角形分割における辺をつないで作られる結び目は、、 シェリングに沿ってその結び目が構成される様子の観察から、その結び目の複雑さに応じて それ相応の辺数を用いないと作れないことが分かるのです。 例えば非自明な最も単純な結び目である三葉結び目の場合は、4辺必要です。 つまり、3辺からなる非自明な結び目が三角形分割に含まれていたら、その三角形分割はシェラブルでない ということになるわけです。 そして、そのような三角形分割は比較的簡単に構成することができ、 これによって、3次元球面の三角形分割でシェラブルでないものが作れることになります。
シェラブルなものとシェラブルでないものの境目の難しさは2次元の場合も、曲面以外の場合にはあります。 曲面の場合、球面とそれ以外の三角形分割のシェラビリティーを分けていたのはオイラー標数だったのですが、 曲面以外だとこのように単純な議論では判別できないケースが出てきます。 その代表的な例が、下図のダンスハットと呼ばれる例です。
これは右図のような三角形を用意し、まずこのABとACの辺を張り合わせて真ん中の図のような三角帽子を作り、 さらにABの線分を三角帽子のふちになっている円周の周りにBからCまでぴったり張り合わせたものです。 慣れていないと形状を想像することがちょっと難しいかもしれませんが、3次元空間中に実現可能な物体になります。 これは実はオイラー標数が1点と同じく１（簡約オイラー標数は０）で、 トポロジー的には可縮という非常に単純なものになっています。 右端はこれを三角形分割して単体的複体にした例です。（この8頂点での三角形分割が最小です。）
このオイラー標数はシェラブルな単体的複体として許容されるものなのですが、しかし、このダンスハットは どのように三角形分割してもシェラブルではありません。
もともと、このダンスハットは古くからよく知られている構造で、カラップシング(collapsing)という、 可縮性の組合せ的アナロジーと本来の可縮性のギャップを示す例として有名なものです。 （可縮ではあるもののカラップシブルではない例。）
ダンスハットはどのような三角形分割をしてもシェラブルでない例なのですが、もう少し微妙な例もあり、 下の図の例は、左側はシェラブルではない例、右側は左側のものを少し細分したものですが、こちらはシェラブルになります。 （4-14と8-13の二重線で書いてある辺のところが細分されています。）
この例はカラップシングに関しては、カラップシブルな例になっています。 実は、2次元の場合に限っては、「シェラブルな細分を持つか」という問題がカラップリビリティーとかなり密接な関連を持っていて、 2次元の単体的複体がシェラブルな細分を持つか否かは、いくつかの2次元ファセットを取り除いてカラップシブルにできることと＋ 各頂点の周りの局所的な構造に問題がないこと、という形で特徴づけることができたりします。 2次元の単体的複体のシェラブル/シェラブルでないの問題にカラップリビリティーの関係する具体例が絡んでくることは この意味から自然なことでもあるのです。
このような感じで、シェラブルなものとシェラブルでないものの境目を探っていくと、なかなか難しいところが多く、 感覚的には、この境目をはっきりさせる（シェラブル／シェラブルでない、の特徴付けをする）ことは かなり難しそうです。 この感覚は、与えられた単体的複体がシェラブルかどうかを判定する問題はNP-完全なのではないか？ と予想することに つながります。実際、これは1970年代から予想されていた未解決問題でした。
このシェラビリティーのNP-完全性の問題は、ほとんど何も進展がないまま長い時間が経ったのですが、 2019年に突如、Gaoac, Paták, Patáková, Tancer, Wagner,という人たちが解決しました。 ようやく、シェラビリティー判定問題はNP-完全だということが示され、この問題が決着したのでした。 彼らの証明は、シェラビリティーとカラップシングとの関連を経由して、カラップシビリティーの言葉を用いて行われました。 （その後、Santamaria-GalvisとWoodroofeにより、シェリングの言葉のみでこれを記述することができるという証明も 与えられました。）
この連載では、第9～11回のシェラビリティーに関する紹介をするという部分は最初の構想時点で決めていて、 ここの説明に登場する基礎知識がそれ以前のいろいろな回の中に登場するように散りばめていたのですが、 幾何学・トポロジー的なトピックに関連がなさそうだった第4回の計算量の話の部分も、実はこの回のこの シェラビリティーのNP-完全性の問題が解決されたという話を紹介するための布石になっていたのでした。
（この回の3次元球面における結び目との関係、2次元の場合とカラップシングとの関係などのあたりは、 私自身の成果が入っています。）
八森正泰