組合せ数学セミナー
発表内容の概要

6/4(金):籾原幸二 (筑波大学 大学院システム情報工学研究科)
差集合族と有限体上の指標論

講演内容：差集合や差集合族とよばれる組合せ構造の存在性や構 
成法を調べる上で，群の指標は有効な道具である．特にこの講演
では差集合族への有限体上の指標和の応用について，いくつかの
代表的な先行研究の紹介を行い，時間が許せば私の最近の結果に
ついても紹介したい．（バックグラウンドが異なる方でも研究の
外観をできるだけ分かっていただけるよう，導入部分にできるだ
け時間をかけ，込み入った細かい議論はできるだけ避けるつもりです）

6/18(金): 並木誠 (東邦大学理学部情報科学科)
P行列と２者択一の定理、線形相補性問題について

任意の主座小行列式が正である実正方行列をP行列という。
ここで主座小行列式とは，行と列が同じ添字集合でからなる
部分正方行列の行列式のことを言う。P行列で定義される
線形相補性問題は、任意の右側ベクトルbに対して、
唯一の解をもつという特徴がある。しかしながら、
P行列であるかの判定問題は、co-NP完全問題として知られており、
多項式時間のアルゴリズムは絶望視されている。

発表では、P行列クラスに含まれたり、P行列クラスを含んだり
する行列のクラスをいくつか紹介する。それらの行列クラスに属するかどうかの判定は、
いずれも２者択一の定理により、効率よく判定可能である。
さらに、ある特定の行列クラスに関しては、その行列によって
定義される線形相補性問題さえも効率よく解けることも紹介する。

7/2(金):高橋里司 (筑波大学 大学院システム情報工学研究科)
単一財複数ユニットオークションの勝者決定問題に対する高速解法

オークションの勝者決定問題は、入札者に財を割当てる割当て問題と支
払い価格を決定する問題を含んでおり、それらの問題は、オークション
メカニズムに依存する。本研究では、 Vickrey-Clarck-Groves(VCG)メカ
ニズムを用いたオークションを対象とする。
  VCGメカニズムを用いたオークションの勝者決定問題は計算が困難で
あり、オーンラインオークションなどの入札者数が大きい割当て問題で
は求解が困難である。そこで、本研究では、勝者決定問題に対する完全
多項式時間近似スキームを提案し、数値実験によってその有効性を示し
た。

7/9(金):東谷章弘 (大阪大学 大学院情報科学研究科情報基礎数学専攻)
有限グラフに付随するGorenstein Fano凸多面体のEhrhart多項式

整(格子)凸多面体のEhrhart多項式とは、
整凸多面体をn倍に膨らませたものの格子点の個数のことである。
最近では、Ehrhart多項式の根に関する研究が盛んに行われている。
その中でも特に、Gorenstein Fano (reflexive) 凸多面体の根は
非常に興味深い振る舞いをみせる。本講演では、
Gorenstein Fano凸多面体の中でも特に、有限グラフに付随する
symmetric edge凸多面体と呼ばれるものを考え、
そのEhrhart多項式の根に関する研究について紹介する。

7/23(金) 13:00〜14:00: 柏原賢二(東京大学 大学院総合文化研究科)
端点作用素と閉包作用素

閉包作用素はsigma:2^E\to 2^Eが
extensive、monotone、idempotentの3つの性質を満たす
ものとして定義出来る。
閉集合族が与えられることと、閉包作用素が与えられることは同じである。
閉包作用素が交換公理を満たすものがマトロイドであり、
反交換公理を満たすものが凸幾何である。
また、マトロイドや凸幾何は端点作用素を使って定義することもできる。
端点作用素とは、ユークリッド空間の点配置で言えば、与えられた点集合のうち、
凸包の端点を与えるものである。
閉包作用素と端点作用素は相互に移りあうものであり、
その1対1対応はさらに広い範囲に広げることができる。
端点作用素は、Koshevoyらによって社会科学における選択関数としても
研究されてきた。また、組合せの分野では安藤和敏先生の研究が
有名である。
今回の発表では、それらによる結果の紹介が中心である。
そして最後に、関連するクラスを禁止マイナー的に特徴づけることを考える。

7/23(金) 14:15〜16:15:宮田洋行 (東京大学 大学院情報理工学系研究科)
多面体の組合せ構造の列挙

多面体の組合せ構造(面束)の列挙は古くから研究されてきた重要な問題である。
次元が低い場合、頂点数が少ない場合は効率よく列挙できるが、一般には
多面体の面束を認識すること自体が一般の整数係数の多項式の等式・不等式系
の可解性を判定する問題と多項式時間等価であり、列挙は非常に難しい。

本講演では、まず効率よく組合せ構造を列挙できるクラスについて解説し、
その後、一般の場合に対するアプローチを紹介する。
そして、最後に9頂点からなる5次元多面体の組合せ構造の列挙を達成した
森山園子先生(東北大)、福田公明先生(チューリッヒ工科大)との共同研究
について解説する。
時間があれば、超平面配置、点配置の分類についても触れる予定である。

7/23(金) 16:30〜18:30:松浦昭洋 (東京電機大学理工学部情報システムデザイン学系)
k本ハノイの塔問題と一般化Frame-Stewart数

ハノイの塔問題は、柱の数が3本のときは移動回数の最小値がよく知られるが、
柱の数がk本(k>=4)のときは、未だ最小値が分かっていない。

本発表では、k本ハノイの塔問題について、これまで知られる最良の上・下界値
とそれらの導出法を示し、さらに、グラフ上のハノイの塔問題 (すなわち、柱は
有向グラフの各頂点上に配置され、柱間に辺が存在する場合のみ円盤の移動が可能、
としたハノイの塔問題)等、問題の一般化の試みと代表的な結果を紹介する。
また、発表者自身が最近J. Chappelon氏 (ULCO)との共同研究で得た、元のk本
ハノイの塔問題に対する再帰式の一般化となっている、ある再帰式の無限族が、
解としてsmooth numbersと呼ばれる数を体系的に取る、という結果も報告する。