組合せ数学セミナー
発表内容の概要
chordal graphは全ての長さ４以上のサイクルが弦を持つという
定義であるが、clique treeと呼ばれるlabeled treeの集合を
持つという特徴がある。clique treeはしばしば自然科学において
データ構造として現れるため、あるchordal graphのclique tree
全体となりうるlabeled treeの集合は重要な意味を持つ。
本発表ではこの２つの集合の一致の条件を構造及び集合の濃度から
いくつか列挙する。また、clique treeの自然科学への応用についても
解説したい。
By analogy with the conjecture of Hirsch, we conjecture that the
order of the largest total curvature of the central path associated
to a polytope is the number of inequalities defining the polytope.
By analogy with a result of Dedieu, Malajovich and Shub, we
conjecture that the average diameter of a bounded cell of an
arrangement is less than the dimension. We prove continuous
analogues of two results of Holt-Klee and Klee-Walkup: we construct
a family of polytopes which attain the conjectured order of the
largest total curvature, and we prove that the special case where
the number of inequalities is twice the dimension is equivalent to
the general case. We substantiate these conjectures in low
dimensions and highlight additional links.
joint-work with Tamas Terlaky and Yuriy Zinchenko
$2n$個のチームがあって、$2n-1$日間の日程で総当たりの対戦の日程表を組む
ような状況を考える。すなわち、1日に$n$試合を平行に行い、$2n-1$日間かけ
て全部で$n(2n-1)$試合するような対戦表を考えたい。ただし、対戦スケジュー
ルを組むにあたって制約がひとつある。それは、どのチームがどの日に自分た
ちのホームグラウンドを使用して試合をするかホームグラウンド以外で試合、
すなわちアウェゲームかという$2n\times (2n-1)$の表が事前に与えられていて、
ホームとアウェのチーム間でしか戦えないという制約を満たすように対戦スケ
ジュールを作らないといけないとする。すなわち、その日にホームとホームで
あるようなチーム同士や、アウェとアウェのチーム同士は戦えないということ
である。与えられたホームアウェ表によっては、制約を満たす対戦日程が存在
しない場合もあり得る。そのホームアウェ表がどのような条件を満たせば実際
の総当たり対戦が存在するかなどの問題を考える。
総当たり対戦スケジュールが存在するかどうかという問題に関して、
R. Miyashiro, H. Iwasaki, and T. Matsui(2003) の論文で議論されている。
彼等の論文では、ここでも後に議論する総当たり対戦スケジュールが存在する
必要条件が与えられている。
最近，D. Briskorn(2007)によって，総当たり対戦が存在するための新たな必
要条件と，その条件が十分条件にもなっているのではないかという予想が提出
された．対戦が存在する条件を線形不等式系を用いて記述し，非整数の対戦が
存在すれば，整数の対戦も存在するのではないかという予想である．この研究
では，その予想を，完全マッチングを中心とした記述に書き換える． Hilbert
basisを使って考えることにより，自然に総当たりでない対戦まで問題が一般化
される．総当たり対戦が完全グラフに対応するとすると，正則グラフに一般化
することになる．また，正則グラフの場合では，非整数対戦が存在しても整数
対戦が存在しない例があることを指摘する．どういう正則グラフならば，予想
の性質が成り立ち，どういう場合は成り立たないかを議論する．
マッチングを用いて生成されるコーンのHilbert basisを計算することにより，
その性質を持つかどうかがわかることを説明する．
有向マトロイドとは、線形部分空間を組合せ的に抽象化したモデルであり、
ランクがrの有向マトロイドは(r-1)-次元空間中の点配置と関連付けて考える
ことができる。
2次元平面上の興味深い点配置については平面幾何の立場から盛んに研究が
なされてきたが、一方で高次元の場合にはそのような配置を見つけるための
手法は知られていなかった。
今回は、有向マトロイドの実現可能性を解析するための道具である
極小reduced systemおよび一般化mutationグラフを用い、ランクが4の
有向マトロイドから3次元の点配置の興味深い例を与える。
この研究は、森山園子（東京大学）・福田公明（ETHZ）との共同研究である。
ｘ軸，ｙ軸方向への投影データから一般図形を再構成する様々なアルゴリズムがある．本研究では
，それらのアルゴリズムを分析・比較し，予め既知の禁止領域の存在を仮定し，一般図形を再構成す
るアルゴリズムの開発を行う．
また，解に一意性がない場合について，解に構造を与え，その関係を明らかにし，より良い解を求
める手がかりとする．
トップに戻る