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

6/7(金): 東谷章弘 (大阪大学大学院情報科学研究科情報基礎数学専攻)
１２点定理とピックの公式の一般化

格子多角形とは、（凸とは限らない）多角形で頂点が格子点（整数点）にあるものを
言う。
格子多角形に関する古典的な結果として、「１２点定理」や「ピックの公式」がよく
知られている。
これらは、主張そのものは純粋に組合せ論的なものである一方、
代数幾何やトポロジーなどの様々な数学の分野と関連する非常に興味深い話題である。
本講演では、１２点定理とピックの公式の復習をするとともに、
それぞれの一般化について紹介する。
（本講演は、枡田幹也氏との共同研究に基づく。）

6/21(金): 岡本吉央 (電気通信大学大学院情報理工学研究科情報・通信工学専攻)
望みの場所が重心となるように錘を置くこと

与えられる複数の錘 (質点) は，どの錘の質量も他の
錘の質量の和の半分以下である，という性質を満たす
ものとする．このとき，任意の単純多角形Pとその中の
任意の点tに対して，錘をPの境界上にうまく置くと，
錘の重心がtと一致させられる．これが主結果である．
本発表では，この結果の証明と関連する問題を紹介
する．
共同研究者： L. Barba, J.-L. de Carufel, R. Fleischer,
A. Kawamura, M. Korman, Y. Tang, T. Tokuyama, S. Verdonschot,
T. Wang

7/12(金): 篠原英裕 (東北大学大学院情報科学研究科)
巡回群の繰上りのないnear-factorizationと1-overlapped factorization

有限群のnear-factorizationおよび1-overlapped factorizationは
partitionable graphやLehman行列を生成するためperfect graphや
ideal clutterの分野で重要な概念である。本講演では巡回群のnear/
1-overlapped factorizationの中で最も基本的なクラスであるKrasnerと
呼ばれるクラスを決定する。本研究は山形大学の佐久間雅氏との共同
研究である。

7/19(金): 戸田貴久 (ERATO湊離散構造処理系プロジェクト研究員)
二分決定グラフに基づく極小横断の列挙

本講演では、ハイパーグラフが与えられるとき、すべての極小横断（極小ヒッ
ティング集合）を列挙する問題を扱う。
この問題は単調論理関数の双対化など重要な問題と等価であり、データマイニン
グ、人工知能、論理などの分野に多くの応用がある。
この問題を解く出力多項式時間アルゴリズムの存在は、数十年もの間大きな未解
決問題として残されている。
一方で、近年、実際的に高速に計算する手法の研究が盛んに行われている。
本講演では、後者の研究を推し進めるために二分決定グラフに基づく極小横断の
計算法を提案する。
二分決定グラフはハイパーグラフを表現するデータ構造であり、多くの大規模組
合せ問題に対してその有効性が認められている。
本講演では、二分決定グラフに基づく計算の枠組み、および、それに基づく極小
横断の列挙法について解説する。