第６回組合せ論若手研究集会招待講演アブストラクト

平成 22 年 2 月 2 日（火）〜2 月 4 日（木）慶應義塾大学矢上キャンパス 12 棟 2 階 210 番教室

2 月 2 日（火） Henning Bruhn-Fujimoto 氏 （日本大学） Maya Jakobine Stein 氏（Universidad de Chile）

「Infinite graphs: Cycles & Extremes 」

Often simple facts about finite graphs become hard and interesting problems in infinite graphs. In the talk we will illustrate this observation by discussing how theorems about cycles as well as extremal results extend to infinite graphs.

2 月 2 日（火） 前原濶氏 （東海大学）

「凸多面体の直観幾何」

凸多面体に関する以下の具体的な話題について、これまでに得られている結果などを紹介する。

・凸多面体をフレームで拘束する — フレームの形とサイズ・正四面体をシリンダーに埋め込む — 埋め込みの分類・正四面体を壁穴から通す — 壁穴の形とサイズ・凸多面体族の元素凸多面体セット — 元素数の最小値

2 月 3 日（水） 澤正憲氏 （名古屋大学）

「Cubature formula 」

多変数関数の積分値を近似的に求めるために多次元空間から有限個の点を選び，それらの点における関数値の重みつき平均値によって所望の積分値を近似する公式を Cubature formula （またはデザイン）という．少ない近似点からなる Cubature formula は解析学や組合せ論において様々な角度から研究されてきた．今回の講演では，ガウス積分をはじめ直交変換により不変な積分に対して，少ない近似点からなる Cubature formula について知られていることを幾つか紹介する．

2 月 4 日（木） 牧野和久氏 （東京大学）

「単調論理関数の双対化問題について」

単調論理関数の双対化問題とは，与えられた単調な論理和形から等価な論理積形を求める問題である．この双対化問題は，数理計画，人工知能，データベース，分散システム，学習理論など様々な分野に現れる数多くの重要かつ実用的な問題と（多項式時間還元の意味で）等価であることが知られている．現在までのところ， Fredman-Khachiyan による準多項式時間アルゴリズムが知られているが，２０年以上もの間，多項式時間アルゴリズムが存在するかどうか未解決のままである．今回は，この双対化問題の歴史や最近の話題について紹介する．