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

10/19(金): 松井鉄史 (国立情報学研究所)
Edge Polytope の Ehrhart 多項式を代数的に計算する方法

連結単純グラフから作られる edge polytope と呼ばれる整凸多面体の
Ehrhart 多項式をグラフの情報だけから代数的に計算することを考える。
グラフの任意の奇サイクルの対が距離 1 以下であれば edge ring という環を
用いて計算できることが知られている。本公演では、グラフが距離 2 以上の奇
サイクル対を持っている場合にも Ehrhart 多項式を計算できるように edge
ring の作り方を少し拡張して環を構成する方法を紹介する。

11/2(金): 佐野良夫 (国立情報学研究所)
最小固有値を制限したグラフについて

代数的グラフ理論の分野で重要な問題の１つに、
隣接行列の最小固有値を制限したグラフの特徴づけがある。
1976年、Cameron, Goethals, Seidel, Shult は、
ルート系を用いることで、最小固有値が−２以上のグラフの完全な特徴づけを与えた。
1977年、Hoffman は、クリークをグラフに付け加えるというテクニックを用いて
最小固有値-1-\sqrt{2}以上のグラフの研究を行った。
その後1995年、Woo & Neumaier は Hoffman のアイディアを
「ホフマン・グラフ」および「ライン・グラフの一般化」の概念を導入することで定式化し、
最小固有値-1-\sqrt{2}以上のグラフの特徴づけを与えた。

本発表では、ホフマン・グラフおよび Woo & Neumaier の結果を紹介するとともに、
発表者が最近得た結果について紹介したい。
本発表は、宗政昭弘先生(東北大)、谷口哲至氏（松江高専）との共同研究に基づく。

11/9(金): 喜多奈々緒 (慶応義塾大学大学院理工学研究科)
完全マッチングをもつ一般のグラフの標準分解

マッチング理論においては，与えられたグラフを一意に分解しマッチング構造を
記述するタイプの定理が重要な役割を果たし，これらは標準分解と呼ばれる．完
全マッチングをもつ一般のグラフを非自明に構造化する標準分解は長らく知られ
ていなかった．本発表ではある二つの2項関係：グラフ上に定まる半順序関係と同
値関係を用いて完全マッチングをもつ一般のグラフの標準分解が与えられること
を紹介する．また，最大マッチング問題の双対解に対応付けられる点集合はバリ
アとよばれるが，極大バリアの族はしばしば重要な意味をもつ．上記の結果を用
いることで一般のグラフにおいて極大バリアの族の特徴付けが与えられ，これが
Lov\'asz による canonical partition や Dulmage-Mendelsohn 分解の一般化と
みなし得ることについても述べる．

1/11(金): 高野祐一 (東京工業大学大学院社会理工学研究科経営工学専攻)
ノンパラメトリック項目反応理論のための数理最適化モデル

項目反応理論とは、テストの結果から「被験者の能力」と「各設問の正答率を表す
項目特性曲線」を推定するテスト理論であり、TOEFLやITパスポート試験などで実
際に利用されている。
現在、項目特性曲線の形状をロジスティック曲線に限定したパラメトリック項目反
応理論が広く使われているが、ロジスティック曲線では当てはまりの悪い設問が数
多く存在することがしばしば問題になる。
本研究では、項目特性曲線の形状に強い仮定を置かないノンパラメトリック項目反
応理論に着目し、ノンパラメトリック項目反応理論のための数理最適化モデルを提
案する。そして、計算実験によってその有効性を検証する。
本研究は、村木正昭先生（東京工業大学）、角田信太郎氏（東京工業大学）との共
同研究である。

1/25(金): 萩原学 (産業技術総合研究所)
組合せ論からのモダン符号

昨年、論文誌 IEEE Trans. on Information Theoryに掲載された、
講演者による論文３編の中からいくつかの話題を選んで紹介する。
特に、COMAゼミで２００６年に紹介した量子LDPC符号の続きに
焦点をあてる。