組合せ数学セミナー
発表内容の概要
隣接する頂点では異なるように，グラフの各頂点に色を与えることをグラフの
彩色という．与えられたグラフの彩色に必要最小限の色の個数を彩色数という．
グラフの彩色問題にトポロジーを応用することは， Lovasz の Kneser 予想の
解決に端を発する． Lovasz はグラフに対して近傍複体という単体複体を対応さ
せ，その位相的不変量とグラフの彩色数とを関連付け， Kneser グラフの彩色数
を決定した．箱複体はグラフに対して定義される Z_2-作用が与えられた半順序
集合であり，近傍複体と関係が深い．そのZ_2-ホモトピー不変量も彩色数と関連
が深いことが知られている．
それでは箱複体や近傍複体のトポロジーがどの程度，彩色数と関連があるのか
という問題が生じる．本講演では以下の結果について述べる．ここでGとHは孤立
点を持たないグラフであり，B(G)はGの箱複体，N(G)はGの近傍複体を表す．
・B(G)とB(H)がZ_2-半順序集合として同型であることと，GとHが同型であること
は同値である．したがってそれらの彩色数は等しい．しかしB(G)とB(H)が半順序
集合として同型であってもGとHの彩色数が異なることがある．
・B(G)とB(H)がZ_2-ホモトピー同値であってもGとHの彩色数が異なるものが存在
する．
・N(G)とN(H)が単体複体として同型であっても，GとHの彩色数が異なるものが存
在する．
マトロイド複体においては、頂点集合の任意の順序が誘導するファセットの辞書式
順序がshellingを与え、また、この性質はマトロイド複体の特徴付けにもなること
が古典的によく知られている。本発表では、この事実を復習しつつ、さらに、この
事実がposet matroidへ拡張できることを見る。
本発表は、筑波大学の佐野良夫氏との共同研究に基づく。
有限グラフは、中心が高さcの長方形に存在する単位円たちによる
単位円交差グラフとして実現できるときにc-stripとよばれる。
特に任意の正の数εに対してε-stripグラフであるグラフを
thin strip graphと呼ぶ。このグラフクラスは定義よりunit
interval graphとunit disc graphの間に存在することが分かるが、
さらにunfettered unit interval graphとmixed unit interval graphと
よばれる2種類のunit interval graphの拡張クラスの間に存在することを示す。
この講演は群馬大学の山崎浩一氏、林貴史氏、東京大学の河村彰星氏、
北陸科学技術大学院大学の大舘陽太氏との共同研究に基づく。
Kを位数pの（有限）素体とするとき、K上の任意のn変数（対称）関数は
各変数の次数がp未満であるn変数（対称）多項式を用いて表せることは
よく知られている。本発表では、p進法の足し算と掛け算における
繰り上がり関数についてその具体的な多項式表示について論じるとともに、
それらと暗号理論との関連性について述べる。（なお、本発表は
鍛冶静雄氏（山口大）、前野俊昭氏（名城大）、沼田泰英氏（信州大）との
共同研究に基づくものである。）
連結グラフGにおいて，その頂点部分集合Sが安全集合であるとは，Sによって誘導される部分
グラフの連結成分CとG-Sにおける連結成分DでCとDがGにおいて隣接しているとき|C|≧|D|が
つねに成り立つことを示す．連結グラフGには全域木が存在するので，その全域木から頂点数
がGの半分以上からなる部分木に対応する頂点部分集合をとれば安全集合となるので，任意の
連結グラフは安全集合を含んでいる．本講演では，与えられたグラフが含む安全集合の最小
位数について議論し，得られている研究成果を紹介する．本研究はUniversity of Victoria
のGary MacGillivray氏と山形大学の佐久間雅氏との共同研究に基づく．
アイゼンシュタイン級数の有限世界での類似物の一つの候補が，
アイゼンシュタイン多項式であり，アイゼンシュタイン級数の持つ
良い性質を多く受け継いでいることが，大浦学氏（金沢大）によって
確認されている．
一方，ゼータ多項式とは，代数曲線のゼータ関数をアイデアとして，
斉次多項式に対して定義され，その零点配置に関する
リーマン仮説類似の成立・不成立が非常に大きな問題である．
しかし現在まで，リーマン仮説類似の成立が確認された例は，それほど
多くない．
本講演では，アイゼンシュタイン多項式とゼータ多項式の，
新たな関係を指摘する．
半順序集合 P の順序複体の幾何学的実現は、
P の分類空間とも呼ばれ、
そのホモトピー型と P の離散的な性質との関係が
Quillen などにより調べられている。
フロベニウス複体は、Laudal と Sletsjoe により
環の代数的構造を調べるために導入された概念で、
アファインモノイドの開区間の順序複体として定義される。
最近では、Peeva-Reiner-Sturmfels や Clark-Ehrenborg に
よってそのホモトピー型の研究がなされている。
本講演では、Clark-Ehrenborg の結果を拡張した
自身の結果について発表する。
平面に辺の交差なく埋め込まれたグラフで全ての面が三角形であるものを平面の三角形分割と呼
ぶ。また、頂点数が2m+2以上のグラフGにおいて、m辺からなるマッチングMをGからどのように選
んでもMを含むような完全マッチングが存在する時、Gはm-extendableであると言う。
平面的グラフのmatching extendabilityについて、Plummerはどの平面的グラフも3-extendable
でないことを示した。一方で、5-連結平面的グラフは2-extendableであることが得られている
(Plummer, 1992)。このような研究の中で、指定するマッチングを任意のものではなく「どの2辺も
距離が離れているようなマッチング」とすることで、extendできるマッチングの本数を増やすこ
とができることが知られている。ここで、2辺の距離をその2辺を結ぶ最短のパスの長さで定義し、
頂点数が2m+2以上のグラフGにおいて「m本からなる辺の集合Mで、どの2辺も距離がd以上離れて
いるようなもの」をどのように選んでもMを含むような完全マッチングが存在する時、
Gはdistance d m-extendableであると言う。
本講演では、どのような(d,m)に対して平面の5-連結三角形分割がdistance d m-extendableとな
るかについて、既存の結果と最新の研究成果を紹介する。本研究は慶應義塾大学の太田克弘氏と
の共同研究である。
トップに戻る