組合せ数学セミナー 特別編(2002.7.29, 30)
発表内容の概要

7/29(月) 10:30〜 : 縫田光司(東大・数理)
「Coxeter群の生成元と可換な元について」

Coxeter群とは、Lie環論などで重要な役割を持つWeyl群を含むクラスであり、
その群構造はCoxeter graphと呼ばれるラベル付きグラフによって記述されます。
今回の発表では、Coxeter群の（標準的）生成元のcentralizerの構造に関する論文
（B.Brink, 1996）を紹介します。論文によれば、求めるcentralizerはあるCoxeter群と
自由群の半直積であり、その自由群はもとのCoxeter graphから得られる
"odd Coxeter graph"の連結成分の基本群と同型になります。

なお、発表では特別な予備知識は仮定せず、Coxeter群の基礎から紹介する予定です。

7/29(月) 14:00〜 : 森田英章(東海大・理・情報数理)
「対称群のある表現とグレブナー基底について」

対称群の表現の中でも特に重要なものに「余不変式環」
というものがあります. これは多項式環のある商環に, 変数の入れ替え
として対称群の作用を入れて得られます. この余不変式環を含む
表現の系列で, これも多項式環の商環として構成されるのですが,
「de Concini - Procesi 代数」とよばれているものがあります.
現在、中島達洋氏（明海大学）との共同研究で,
この de-Concini - Procesi 代数に関するある現象を追求しているのですが,
その際, 当然のことながら基底がわかると議論が非常にしやすくなるので,
その定義イデアルのグレブナ−基底を理解することが重要となってきています.
事実, 諸々の事情により, そのグレブナー基底がわかれば, 余不変式環の
既に知られている基底を使って, de Concini - Procesi 代数の良い基底
が構成できるであろうことが予測されています. 本講演では, 以上の話の全体の
流れ, 及び現在我々が持っている問題意識を, 主に実例を用いながらできるだけ
平易に解説したいと考えていますので, グレブナー基底についていろいろなこと
を教えていただければ, また多くのコメントやアイデアを頂戴できれば, と
思っております. よろしくお願い致します.

7/29(月) 16:30〜 : 松久 隆(茨城工専・数学)
「Robust models for Nash equilibrium」

We present the notion of rational expectations
models for a mixed strategy Nash equilibrium of
a strategic form game and to introduce a group
structure on the class of these models called the
\emph{robust class} of models for Nash equilibria
of the game. From the algebraic point of view we give a
characterization of the class of rational expectations
models  by the class of epistemic models with common-knowledge
of conjectures about the other players' actions.

7/30(火) 10:30〜 : 宇野毅明(情報学研究所)
「近傍探索の高速化」

組合せ最適化の解法のひとつに、近傍探索と呼ばれるものがある。
現在の解に対して、ある少数回の操作を行って得られる
解を、その解の近傍とし、現在の解を、その近傍のなかの良いもので
置き換える、という作業を繰り返して行い、よい解を見つけようというものである。
近傍探索を高速化する手法について解説をする。

7/30(火) 14:00〜 : 柏原賢二(東大・広域システム)
「クリーク複体とマトロイド独立集合族」（岡本吉央氏との共同研究）

本研究では、与えられたグラフから作ったクリーク複体をいくつかのマトロイ
ドの独立集合族のインターセクションとして表すことを考える。表現に必要な
マトロイド独立集合族の最小の個数は、グラフの極大安定集合のインターセク
ショングラフの彩色数に一致することを示す。また、グラフのクリーク複体が、
マトロイド独立集合族2つの共通部分で表現できることを特徴づける禁止誘導
部分グラフをすべて挙げる。

7/30(火) 16:30〜 : 岡本吉央(ETH Zurich)
「Spernerの補題について」

Spernerの補題とは，組合せ論的な不動点定理で，
この定理からBrouwerの不動点定理まで導けてしまう
非常に強力な定理です．
言明としては，まず，単体の三角形分割を考え，
その頂点に次の条件を満たすように色を与えます．
その条件とは，まず，各頂点は違う色で塗られる．
そして，単体の各面の相対的内部にある頂点の色は，
その面の端点を塗っている色から選ばなければならない，
というものです．
(つまり使われる色の数は，次元+1になります．)
このとき，Spernerの補題が主張しているのは，
単体のどんな三角形分割(単体分割)に対しても
この条件を満たす頂点彩色によって，必ず，すべての
頂点が違う色の三角形(単体)ができてしまう，というものです．

本発表では，特別な前提知識を仮定せずに，
以下のことについて，お話しさせていただく予定です．
(1) Spernerの補題の(鮮やかな)証明
(2) Spernerの補題の応用：ケーキの切り分け問題
(3) Spernerの補題の証明の計算複雑性
    (PapadimitriouによるPPAD完全性)