組合せ数学セミナー
発表内容の概要
有限 poset P が与えられたとき、P の linear extensions（Pの順序と矛盾し
ない全順序）の総数を求めることは、一般に極めて難しい問題であり、今まで、
限られた poset に対してしか求められていない。 Linear extensions の総数
が計算できる poset の中で最も重要なクラスはおそらく Young 図形のなすク
ラスである。 Young 図形は自然な順序を入れることで poset とみなすことが
できるが、 Young 図形の linear extension は standard tableau と同等な
ものであり、これは表現論的に重要な意味を持つ。
Young 図形の linear extenstions の総数は hook formula によって得られる。
R.P.Stanley は有限 poset に対して P-partitions のなす generating function
を考察し、特に P が Young 図形の場合に hook formula の q-類似(q-hook formula)
を証明した。また、E.R.Gansner は Stanley の q-hook formula を拡張し、
多変数 q-hook formula を証明した。
本講演では、D.Peterson の意味の 一般化されたYoung図形 に対して、同様の
多変数q-hook formula が成り立つことを解説する。また特に、一般化された
Young図形の linear extensions の総数を与える hook formula も導く。
「美術館問題」は離散幾何学・計算幾何学における重要な研究対象であり，数
多くの研究がなされてきた．本発表では美術館問題の変種として2007年に提案
された「彫刻庭園問題」とそれに関して知られている結果を紹介する．簡単に
述べると，美術館問題は室内を監視する問題であるが，彫刻庭園問題は屋外の
定められた領域を監視する問題である．彫刻庭園問題の難しい点は壁がないこ
とであり，そのために通常の美術館問題とは異なる監視の定義を導入すること
になる．彫刻庭園問題は与えられた図形に対するコンパクトなCSG表現を求め
る問題や，ワイヤレス環境における位置同定問題とも関係している．この新し
い問題には数多くの未解決問題が残されているので，それも紹介する．
(X-codeに関する自身の研究について紹介してもらいました。)
対称二部グラフとは，二つの頂点集合を分ける軸で線対称性を持つ二部グラフである．
本発表では，対称な二部グラフのマッチング構造を調べることを目的とする．
まず対称な二部グラフに対しDulmage-Mendelsohn分解を行なうと，得られた成分(マッ
チング被覆グラフ)は対称性を有することが分かる．
マッチング被覆二部グラフは，耳分解(ear decomposition)により，ある辺に長さ奇数
のパスを繰り返し付け加えることで構成できる．
本研究では，マッチング被覆二部グラフが対称ならば高々２本のパスを付け加えること
で対称性を保持したまま耳分解できることを示す．
さらに，対称二部グラフの組合せ的行列理論への応用として，Polyaの問題を一般化し
た問題を提案し，その問題が多項式可解であることを述べる．
トップに戻る