No | 114914 | |
著者(漢字) | 八森,正泰 | |
著者(英字) | Hachimori,Masahiro | |
著者(カナ) | ハチモリ,マサヒロ | |
標題(和) | 構成可能複体の組合せ論 | |
標題(洋) | Combinatorics of Constructible Complexes | |
報告番号 | 114914 | |
報告番号 | 甲14914 | |
学位授与日 | 2000.03.29 | |
学位種別 | 課程博士 | |
学位種類 | 博士(学術) | |
学位記番号 | 博総合第256号 | |
研究科 | 総合文化研究科 | |
専攻 | ||
論文審査委員 | ||
内容要旨 | 本論文は単体的複体および多面体的複体の組合せ的研究であり、主としてその組合せ分割について詳細に研究するものである。 単体的複体とはあるユークリッド空間中の単体の有限集合で、(i)ある単体が集合に含まれていたらその面もすべてその集合に含まれている、(ii)二つの単体が集合に含まれていたらその共通部分は両方の単体の面になっている、という二つの条件を満たすものであり、例えば多様体の三角形分割などはその例である。定義の中で単体を多面体で置き換えると多面体的複体となる。 この単体的複体という概念はトポロジーではホモロジーの計算などにおける基礎概念であり、その考察はトポロジーと切り離すことのできない、密接な関連のある概念であるが、一方、組合せ論でもこの単体的複体が随所に現れる。例えば、多面体というのは組合せ論の基礎的な道具であり研究対象でもあるが、その境界は多面体的複体であり、単体的多面体の境界は単体的複体である。また、半順序集合を考察する上でそれに含まれる鎖の全体を考えるとそれは自然に単体的複体になり、また、グラフの単調プロパティーという概念があり、ある単調プロパティーを持つグラフの全体を考えると自然に単体的複体となる、ということも知られている。この他にも、グラフのクリークの全体やマトロイドの独立集合の全体なども単体的複体として扱われ、単体的複体という概念は組合せ論における研究の中で欠かすことの出来ない重要な概念となっている。本論文はこの単体的複体そのものを研究対象とし、その性質を議論する基礎研究と位置付けられる。 本論文で取り上げるのは単体的複体を再帰的に組合せ的な条件を満たして分割するという「組合せ分割」という概念である。このような概念は多数知られているが、代表的なところを取り上げると次のような4つがあり、それらの概念を強い順に並べると、 頂点分解能⇒シェラブル⇒構成可能⇒コーエン・マコーレ というような関係になっている。本論文ではこれらのすべてを対象とするが、中でも中心的に取り扱うのが構成可能性である。これは、(i)単体は構成可能(ii)二つのd次元の構成可能な単体的複体が(d-1)次元の構成可能な単体的複体を共有している場合それらの和集合は構成可能、というようにサイズおよび次元によって二重に再帰的に定義される概念である。その他の概念では、シェラブルおよびコーエン・マコーレーという概念は非常によく知られていてかつ重要であり、多面体の面の数に関する上限定理の証明に使われたり、その他の多面体の不変量の計算に用いられ、多くの研究がなされている。また、頂点分解可能性も多面体の直径に関する予想との関連からある程度の研究がなされている。しかし、構成可能という概念はこれまでほとんど研究対象として取り上げられず、多くの性質が未解決のまま残されてきていた。本論文はこの構成可能という概念を本格的に研究する初めてのものであり、これまで未解決であった問題を解決すると共に、その考察がシェラブルや頂点分解可能という他の組合せ分割についても新しい結果を多く導くことが出来ることを示す。特に、シェラブルという概念はこれまで非常によく研究されてきていたのであるが、本研究における構成可能性の議論を通して初めて示された事実が存在するということはこの構成可能性という概念の重要さを主張するものである。 本論文における研究で重要なのは、手法として組合せ論的な再帰性に基づく議論に加え、PLトポロジーの議論を道具として用いている点である。上記のように近年の組合せ論においては随所に単体的複体の存在が考慮され、そのトポロジーに基づいた議論が組合せ論における新しい事実を示すことが多々あり、そのような議論は「トポロジー的組合せ論」や「組合せ論のトポロジー的手法」などといわれているが、本研究もその流れの一つに入る。本論文ではPL球体とPL球面についての基本的な定理をもとにして組合せ分割における再帰的な分割の各段階で現れる物体のトポロジーの情報を特定し、その情報を組合せ的議論の中に取り入れることによって純粋に組合せ的に議論する場合以上に細かい議論をすることを可能にしている。また、結び目の性質を議論することによって組合せ分割に関して特殊な性質を持つ例を構成するということも行なっている。 論文では初めの二つの章で概要および初歩的な定義、定理が述べられた後に主な結果が三つの章に渡って述べられる。三章では結び目と組合せ分割の関連に焦点が当てられる。この章で議論される問題は球体や球面の三角形分割(単体的複体の特殊ケース)で組合せ分割の出来ないものを作ることは可能か?という問題である。これはシェラビリティーおよび頂点分解可能性についてはそのようなものが作れることが知られていたが、構成可能性については未解決であった。この章ではこの未解決問題の解決を次のような形で与える。 三章の主定理1.三次元球体および球面の三角形分割が3辺からなる結び目を持っていたら構成可能ではない。また、5辺以下からなる結び目を持っていたら頂点分解可能ではない。 三章の主定理2.三次元球体および球面の三角形分割がe(K)辺からなる結び目Kを持ち、その橋指数がb(K)であるとき、b(K)>e(K)である場合は構成可能ではない、また、2b(K)-2>e(K)である場合は頂点分解可能ではない。 これによって、三次元の球面および球体の三角形分割で構成可能でないものが作れることが示されるだけでなく、三次元以上のすべての次元でそのような構成可能でない三角形分割の存在を示すことが可能である。また、頂点分解可能性に関する上の定理もこの研究で新しく示されたものである。さらに、この構成可能性に関する結果は以前に知られていたFurchやLickorishによるシェラブルでない球体や球面の三角形分割の構成法に関する結果を拡張するものである。特に、Lickorishが1991年にシェラブルでない球面の分割を示した時には、上の定理と似た形で「3辺からなる十分に複雑な結び目を含んでいたらシェラブルではない」ということを示していたのであるが、今回の我々の結果ではシェラブルではないというだけでなく構成可能ではないというように強い形で示したのみではなく、「十分に複雑な」という条件を取り除いたという意味でより強い結果になっている。この他にも、球面の分割のシェラビリティーに関するHetyeiの予想の解決も結果の一つとして示されている。 この章の諸結果はGunter M.Ziegler氏とRichard Ehrenborg氏との共同研究を含んでいる。 四章では与えられた単体的複体に対して組合せ分割が可能であるか否かを効率よく判定する方法があるかどうか、という判定問題を扱う。特にシェラブルの場合については多くの研究者が重要な問題とかが得ているにも関わらず、これまで二次元の擬多様体の場合以外の結果が得られていず、他の組合せ分割に関しても同様に、得られている結果が皆無に等しいという難しい問題である。一般的にはほとんどの場合にNP完全であると予想されている。この章では三次元球体の三角形分割の特殊な場合について、次の結果を具体的なアルゴリズムと共に与える。 四章の主定理.三次元球体の三角形分割で内部の頂点が高々2点である場合、その構成可能性を四面体の数の線形オーダーの時間で判定することが可能である。 これは三次元以上の場合についての組合せ分割の判定問題に関する初めての結果であり、このケースについて多項式時間の判定可能性を示したのみでなく、今までシェラブルでない球体の分割として知られていた例の構成可能性を判定するという結果も示し、それらの中に構成可能ではあるものと構成可能でもないものが混在していたという事実を明らかにしている。 最後の五章では、二次元の単体的複体の組合せ分割について議論する。いままで二次元の単体的複体についてはあまり論じられて来ず、二次元の擬多様体が極めて簡単な構造を持っているため、「二次元=単純」と思われ勝ちであった。ここでは二次元の単体的複体でも擬多様体に制限しない場合にはかなり複雑な構造があることを論じる。これまでに知られていたのはStanleyによるシェラブルではないがコーエン・マコーレーではある例、および、Bjornerによる拡張的にはシェラブルではないがシェラブルではある例くらいであったが、この章では新たに、シェラブルでないが構成可能ではある例、構成可能ではないがコーエン・マコーレーではある例、頂点分解可能ではないがシェラブルではある例を示す。特に、構成可能ではないががコーエン・マコーレーではある例としてはダンス・ハットが構成可能でないことを示し、これは以前にStanleyによって示されていたダンス・ハットがシェラブルでないという事実を強い形に拡張する結果となっている。これらの結果は二次元においても三次元以上の場合に知られていた各階層間のギャップがすでに存在していることを示していて、二次元ですでに複雑な様相が現れていることを明らかにするものである。また、シェラブルではないが細分するとシェラブルになる例などが二次元で作れることも示されている。 | |
審査要旨 | 本論文では、位相幾何学で主要な研究対象である単体的複体、多面体的複体の性質、特に構成可能性(constructibility)、シェラビリティ(shellability)といったその組合せ的分割の性質についての研究が展開されている。その中で、単体的複体の構成可能性については、シェラビリティ頂点分解可能性といった概念に比べてこれまで研究成果が乏しかったが、論文提出者は構成可能性が成立するあるいは成立しないための条件をあらたにいくつか明らかにし、そこから球体及び球面の三角形分割で構成可能でないものを構成する一般的な方法を示した。さらに、適当な条件の下で、構成可能性が単体の数の線形オーダーの手間のアルゴリズムで判定できることを具体的なアルゴリズムによって示した。 本論文は全体で5章からなる。第1章、第2章は、導入部と数学的準備にあてられている。第3章においては、球体や球面の三角形分割で構成可能でない例を見つけるという未解決の問題を取り上げ、それを次のふたつの定理を示すことで解決した。 [定理]三次元球体および球面の三角形分割が、3辺からなる結び目を持っているときは構成可能でない。また、5辺からなる結び目を持っているときは頂点分解可能でない。 [定理]三次元球面および三次元球体の三角形分割がe(K)辺からなる結び目Kを持ち、その橋指数がb(K)であるとき、b(K)>e(K)であれば構成可能でない。また、2b(K)-2>e(K)である場合は頂点分解可能でない。 これらは、球面や球体の三角形分割でシェラブルでない例を示したFurchやLickorishの結果を構成可能性にまで拡張した結果になっている。また、球面の三角形分割でシェラブルにならずかつその立方重心細分が再びシェラブルでないものが存在するだろうというHetyeiの予想がこれにより肯定的に解決された。 第4章では、与えられた単体的複体が組合せ分割可能であるかどうかを判定するアルゴリズムが扱われている。ここで論文提出者は、三次元球体の三角形分割で内部の頂点の数が高々2点である場合は、含まれる単体の数の線形のオーダーでその構成可能性が判定できるということを示した。このような判定アルゴリズムの問題については、これまでほとんどめぼしい結果が得られておらず、本章の結果はこの分野で貴重な第一歩を記すものである。 最後の第5章では、これまであまり注目されなかった二次元の単体的複体の組合せ分割を取り上げ、詳細に議論している。論文提出者は、ここで、二次元の単体的複体でも擬多様体に制限しなければ、かなり複雑な構造を持ちうることを述べ、シェラブルでないが構成可能である例、構成可能でないがコーエン・マコーレイである例、頂点分解可能ではないがシェラブルである例を示している。特に、Stanleyがコーエン・マコーレイであるがシェラブルでないことを示したダンス・ハットと呼ばれる単体的複体について、これがさらに強く構成可能でないことを示し、Stanleyの結果を拡張している。 以上要するに、論文提出者は、位相幾何学において重要な概念である単体的複体の構成可能性、シェラビリティなどの組合せ分割について、新しい判定条件を提示し、及びそれに基づいて球面あるいは球体の三角形分割で構成可能でないものの例をあらたに示し、これまでに知られていた結果を大幅に拡張してみせた。かつこれにより未解決の予想を解決することができた。また、適当な条件のもとでは、三次元球体の構成可能性を判定する効率的なアルゴリズムが存在することを示した。この一連の研究成果は、単体的複体の組合せ分割の研究において新しい方向を開くものとして高く評価されるものである。また、論文提出者のこれらの研究活動は、ベルリン工科大学のZiegler氏などの海外の研究者からも早くから関心を持たれ、それを糸口としてZiegler氏ほかの研究者との共同研究が始まって現在に至っている。そして、本論文にもその共同研究の成果が含まれている。また、第3章、第4章の主要な結果は、二編の学術論文として学術雑誌にすでに掲載予定になっている。 よって本論文は、博士(学術)の学位論文として合格と認められる。 | |
UTokyo Repositoryリンク | http://hdl.handle.net/2261/54753 |