組合せ数学セミナー
発表内容の概要
Segre-Veronese 型配置に付随するトーリックイデアルは
変数の添字のソーティングに対応する単項式順序に関して
スクエアフリーな2次のグレブナー基底を持つ。
この配置は，Veronese型配置，Segre配置の自然な拡張であり，
H. Ohsugi and T. Hibi,
Compressed polytopes, initial ideals and complete multipartite graphs,
Illinois Journal of Mathematics 44 (2000), 391-406.
において定義されたが，
最近，共同研究（Aoki-Hibi-Ohsugi-Takemura）
の中でさらに拡張されたので，これについて紹介したい。
グラフの全ての頂点を通る閉路をハミルトン閉路と呼ぶ．「与えられたグラフ
にハミルトン閉路が存在するかどうかを判定する」という問題は非常に重要で
あるが同時に難しい問題であることも知られている．この難しい問題に対する
アプローチの一つの方法として，グラフがハミルトン閉路を持たないときに，
そのグラフが ``どのくらいハミルトン閉路を持ちにくいか''という点に関して
の数量的な評価を考慮する，というものが挙げられる．本講演ではグラフ理論
におけるこの数量的な評価に関わる歴史と，特にその中でも最近考案されたグ
ラフの ``Relative Length'' という不変量による評価の方法を紹介する．
LorentzのX線問題とは, 平面内の均一な物体を2方向への射影のみから復元するという問題で,
均一な物体や材料の非破壊検査, グラフ理論, 暗号理論等への応用が検討されている問題である.
本公演では, この問題の歴史やCTスキャンとの関連についての紹介から始め,
2方向への射影のみからできること, できないこと, 今後解決されるべき問題について紹介したい.
graph から決まる abstract simplicial complex の１つに、
J. Matousek と G. M. Ziegler によって定義された box complex がある。
box complex に関する興味深い事実の１つとして、box complex の
Z_2-index で (graph の彩色数-2) の下界が与えられることが挙げられる。
一方、(graph の彩色数-2) と box complex の Z_2-index との差が生じる
ような、4-cycles を含まない graph が存在することもわかっている。
本講演では、box complex の幾何学的構造を調べることを目標にし、
4-cycles を含まない graph 及び 細分された graph の組合せ論的構造が
box complex の幾何学的構造に対して、どのように反映するかを紹介する。
結晶学になじみのない方向けに、粉末結晶回折パターンの未知構造解析問題およびその
一部である指数づけ問題について、背景から紹介する。
この問題は、一種の逆問題であり、Kacの太鼓の問題・2次形式・パッキング問題など、
さまざまな分野と関連があることが分かっている。そういった関連について述べながら
、この分野の全体的な様子をお伝えしたい。
今回紹介したい新しい成果としては、以下がある。
1．粉末回折パターンから得られる情報は、3次元空間に原子を周期的に配置したときの
average theta seriesから得られる情報に等しいことを示した。
2．新しい指数づけアルゴリズムを開発した。
特に、2．についてであるが、粉末回折パターンの指数づけ問題は、具体的には、以下の
ように定式化される。
"3次元格子の格子ベクトルの長さの情報が(部分的に)分かっているときに、その格子の
形（単位格子の辺の長さ、角度）を決定する。ただし、一般に、長さの情報には誤差が
含まれており、適当な確率で(不純物や雑音による)間違いも発生する。"
従来の指数づけアルゴリズムに存在する問題点を解決するために、既存の方法とは全く
異なる新しい指数づけの方法を考案した。
この方法を用いれば、晶系に関わらず、手計算でも指数づけを行うことが現実的に可能
である。(もちろん手計算の場合は、それなりに時間はかかる。)
組合せ最適化問題の標準的な手法に凸多面体的手法がある。グラフの最大カット問題に
対応する凸多面体であるカット多面体は、定義は単純なのに複雑な構造を持ち、長年研
究されている。一方、物理学の世界では量子力学が古典的な直観に反する非局所性とい
う性質を持つことが知られており、その証明に使われるBell不等式という道具は「古典
的な直観」に対応する凸多面体の不等式表現に相当する。この古典世界に対応する凸多
面体は、じつは完全二部グラフのカット多面体になっていることがわかる。
本発表では、カット多面体と量子力学の非局所性の関係について述べる。カット多面体
が古典の世界に対応するように、カット多面体の半定値緩和であるelliptopeや線形緩和
の一つである根付き擬距離多面体がある意味で量子の世界に対応することが示せる。古
典に対応する凸多面体、それを含む量子に対応する凸図形の差異が、量子力学の非局所
性の大きさを表すと捉えることができる。これにより、カット多面体の性質を使って量
子力学で得られる非局所性の定量的な評価を得ることができる。
本研究は、 David Avis 氏、今井浩氏、佐々木勇也氏との共同研究である。
与えられた語Aに対してsubword order が定義され、そのメビウス関数はnormal
embedding という組合せ論的な言葉で記述されます。
一方基になる語をposet Pとしたとき同様にgeneralized subword orderを
定義することができます。 とくにPがrooted forestのときにはsubword orderと
似たような形でメビウス関数を表示することができます。
今回PがΛの形をしたposetのとき〔non rooted posetでもっとも簡単な場合〕に
generalized subword orderのメビウス関数がどうなるかをお話します。
chordal graphの重要な性質の一つに、perfect elimination orderと
呼ばれる頂点集合への特別な番号付けの存在がある。特に、グラフが
chordalなこととperfect elimination orderの存在が同値であることは
グラフ理論における周知の事実である。今回の発表では、話者の最近の
研究のうち、辺が2色で色分けされたグラフ（edge-bicolored graph）への
perfect elimination orderの拡張と、そのような番号付けが存在するための
edge-bicolored graphに関する必要充分条件について述べる。更に、
本研究の動機となった（多重）超平面配置に関する最近の研究に関しても、
研究背景や本研究を応用して得られる結果などについて紹介する。
なお、本研究は阿部拓郎氏および沼田泰英氏（ともに北海道大学）との
共同研究である。
トップに戻る