組合せ数学セミナー
発表内容の概要
単体的複体Δが性質Pを持たず，Δの頂点集合の真部分集合への制限が
すべて性質Pを持つとき，Δを性質Pのobstructionという．単体的複体
の性質としてshellability, partitionability, sequential Cohen-Macaulayness
を取り上げ，2次元の場合のobstructionを特定する結果の紹介および，
その他の議論を進めたい．
n 変数上の論理式を例題とするあるＰＳＰＡＣＥ完全問題を（厳密に）解く，
O(2-\epsilon)^n 時間アルゴリズムを提案する．ＮＰ完全問題である 3-SAT
問題と SAT 問題において，前者には (2-c)^n 時間アルゴリズムが存在する
（for some c>0）のに対して，後者には (2-\epsilon)^n（\epsilon>0）時間
アルゴリズムの存在が知られていない．このように，ＮＰ困難な問題を厳密に
解くことを考えた場合，明らかな上界 2^n よりも（真に）よい上界を見つけ
ること，及び，そのような上界が存在するかどうかを議論することが，１つの
研究分野になっている．本研究では，あるＰＳＰＡＣＥ完全な問題が，
O(2-\epsilon)^n 時間アルゴリズム（for some \epsilon>0）を持つことを示す．
また，（多項式時間階層の）\Sigma_2 完全問題が O(2-\epsilon)^n 時間アル
ゴリズムを持つこと，及び，\Pi_2 完全問題に O(2-\epsilon)^n 時間アルゴ
リズムが存在するかどうかについて議論する．
1968年J. E. Cohen は、生態学の問題と関連して、競争グラフの概念を導入した。
有向グラフ $D$ に対して、その競争グラフ $C(D)$ とは、$D$ と同じ頂点集合を
持ち、異なる２頂点 $x$ と $y$ の間に辺 $xy$ を持つのは、$(x,v)$ と $(y,v)$
が $D$ の有向辺であるようなある頂点 $v$ が存在するときとして、定義される
(無向)グラフのことである。
F. S. Roberts は、「どんなグラフ $G$ についても十分多くの孤立点を付け加える
ことで、 $G$ はある非巡回有向グラフの競争グラフとなる」ということに着目した。
そのような孤立点の最小の数を、グラフ $G$ の競争数と呼び、$k(G)$ で表す。
一般のグラフに対して、この競争数を求めるのは難しい問題である。
R. J. Opsut はグラフの競争数を求める計算問題はＮＰ困難問題であることを示した。
本発表では、グラフの競争数に関する基本的な定理等をいくつか紹介した後、最近
になって発表者が得た、完全多部グラフの競争数に関する結果について述べたいと
思う。さらに時間があれば、競争数に関する他の話題にもふれたいと思う。
近年の研究で、カオス的性質を持つロジスティック写像を応用した
擬似乱数生成アルゴリズムが提案されている。しかしその一方式には、
不適切なパラメータを選択すると出力が定常的になってしまう危険性が
あるという欠点の存在が指摘されている。話者の最近の研究では、
0と1からなる無限列におけるあるパターンの漸近的出現率に関する
組合せ論的解析を通して、ある組合せ数論的予想の成立を仮定した上での
この不適切なパラメータの割合の下界を与えた。
本発表ではこの研究結果について紹介する。
単体的複体がshellableであるとは、単体を1つづつうまい具合に足していって
構成することができるかというようなことである。今回の研究では、
任意の deletion が shellable となる単体的複体について議論する。2 次元の
単体的複体で、任意の deletion が shellable なものは、extendably shellable
であることを示した。 また、２次元の純な単体的複体で、任意の deletionが
shellableであるにも関わらずvertex decomposableでない例を見つけた。
さらに、matroid複体との関係についても議論し、予想を紹介する。
この研究は筑波大の八森正泰氏との共同研究に基づいています。
クイックソートは，期待計算量が Θ(n log n) であるが，入力によっては
最悪で Θ(n^2) の計算量を必要とする．とくに，整列済みの順列を入力した
場合に計算量が大きくなると言われている．
本研究では入力の整列度合いの指標として反転数を用いて，反転数と計算量に
ついての関連性を詳細に解析した．最悪計算量，最良計算量，期待計算量に
関して理論的な結果を得た．
本研究は岡本吉央氏 (東工大), 白幡和也氏 (豊橋技科大) との共同研究
である．
本発表は上別府陽氏（筑波大学大学院数理物質科学研究科後期課程）との
共同研究に基づいています。
有限単純グラフGの組み合わせ構造を,Gに付随して定義される単体的複体K(G)の
トポロジーを通して調べる研究がいくつか行われています。ここで考えるbox complex
B(G)もそのような複体の一つであり,Gの彩色数との関係が調べられています (Matousek-Ziegler)。
一方でB(G)のトポロジーを知ることは一般に難しく, 上の結果にせよ彩色数の評価と
して”良い”ものかどうか, 明らかではありません。そこで「一般にB(G)の
ホモトピー型、あるいはホモロジー群は, Gのどのような性質を反映しているのか？」
という問題が生じます。
今回の結果はchordal graph Gのbox complex B(G)について、そのホモロジー群をGの
組み合わせ的データから決めることを目標としています。
（１）まずchordal graph Gに対して, B(G)のホモロジー群はtorsion-free
であることが示せます。Csorba, Zivaljevicらによって、どんな自由Z_2作用を持つ
単体的複体も, 適当なグラフのbox complexと同じホモトピー型をもつことが示されてい
ます。上の結果はchordal graphのbox complexとして実現される単体的複体に対する一つ
の制限を与えるものです。
（２）chordal graphは常に極大完全部分グラフによる樹状分解を持ちます。この分解を
用いて、box complexのオイラー標数を記述することができます。この計算を行う過程に
おいて,「Gの完全部分グラフがB(G)の非自明なホモロジー類を表すのはいつか？」という
問いにある程度答えることができます。
トップに戻る