北海道大学マトロイドセミナー (HUMS) は，マトロイドやその周辺分野に関する純粋数学と応用数学の研究者・大学院生の研究交流を深めることを目的として，北海道大学で開催されるセミナーです．各回，純粋数学と応用数学の両分野から各一名，それぞれ2時間のご講演をいただきます．2024年度に2〜3回の開催を目指しています．
北海道大学と銘打っていますが，もちろん他大の方の参加も大歓迎です．
2025年1月3日：第二回セミナーの日程及び講演者を掲載しました．
2024年11月12日：キャパシティの都合により，午後の会場を変更しました．
2024年9月24日：スケジュールを微調整しました．
2024年9月23日：講演タイトル及び概要を掲載しました．
参加登録は事前にこちらからお願いします！
懇親会参加登録は締め切りました．
日程：2025年3月28日（金）
場所：北海道大学 札幌キャンパス（アクセス）理学部4号館501号室
純粋数学：三枝崎 剛 氏（早稲田大学 理工学術院 基幹理工学部 教授）
講演タイトル：マトロイドに関係する多項式不変量について
概要：符号理論における重さ多項式やグラフ理論における彩色多項式，それらを抽象化したマトロイドにおけるタット多項式など，多くの離散構造における多項式不変量は，除去縮約公式といった類似した性質をもつ．一方で，重さ多項式のよく知られた性質であり，しかし彩色多項式では得られていない性質，あるいはその逆など多くの差も知られている．本講演では，
符号理論において重さ多項式の一般化であるヤコビ多項式と調和多項式を紹介，
グラフ理論における彩色多項式の一般化である彩色対称関数，圏化を紹介し
それらを符号理論からグラフ理論，あるいはグラフ理論から符号理論へ移植する研究，さらにはマトロイド理論へ抽象化する研究を紹介したい．
応用数学：清水 伸高 氏（東京科学大学 工学院 経営工学系 助教）
講演タイトル：マトロイドのエクスパンダー性
概要：与えられたマトロイドの基の個数の効率的な数え上げは，行列木定理をはじめとした様々な離散構造の数え上げを特殊ケースとして含む重要な研究テーマである．しかし，情報理論的な下界や計算量理論的な下界が知られており，決定的（ランダムネスを使わずに）多項式時間で数え上げることは不可能であると広く信じられている．一方で決定的アルゴリズムとは対照的に，ランダムネスを用いて効率的に近似的に基の個数を数え上げるアルゴリズムが近年示されている．この乱択アルゴリズムはマルコフ連鎖モンテカルロ法に基づく近似数え上げの文脈で古くから考察されてきたものではあったのだが，その計算量解析は30年来の未解決問題であった．この未解決問題の解決の背景には抽象的単体複体上のランダムウォークのスペクトル性の理論があり，この理論は現在では効率的な誤り訂正符号の構成や対数凹性を持つ分布のサンプリングに応用されている．本講演では，抽象的単体複体の高次元エクスパンダー性の理論を紹介し，その応用としてマトロイドの基を近似的に数え上げる乱択アルゴリズムを紹介する．
講演スライド：https://nobutakashimizu.github.io/matroid_seminar/
10:00–11:00 ディスカッション（自由参加）
13:30–15:30 講演１（純粋数学）
15:30–15:50 休憩
15:50–17:50 講演２（応用数学）
19:00– 懇親会（海へ アスティ店）
日程：2024年11月12日（火）
場所：北海道大学 札幌キャンパス（アクセス）
午前：理学部3号館307号室
午後：理学部3号館205号室（午後の会場が変更になりました！）
純粋数学：菅原 朔見 氏（北海道大学 大学院理学院数学専攻 D3）
講演タイトル：超平面配置の組合せ論とトポロジー
概要：ベクトル空間内の超平面の有限集合を超平面配置と呼ぶ．超平面配置は代数幾何，トポロジー，組合せ論等幅広い分野から研究されてきた対象である．マトロイド理論の観点からは，「表現可能なマトロイド」が超平面配置に対応する．超平面配置からは，「超平面たちがどのように交わっているか」という情報を表す交叉半順序集合が定まる．超平面配置においては，「交叉半順序集合から，超平面配置の組合せ的，位相的情報がどれくらい決まるか？」というものが基本的な問題意識であり，現在も盛んに研究されている．本講演では，超平面配置の基本的な話題から導入し，交叉半順序集合から定まる特性多項式が，超平面配置の様々な組合せ的，位相的な不変量を定めることについて紹介したい．
応用数学：山口 勇太郎 氏（大阪大学 大学院情報科学研究科 准教授）
講演タイトル：組合せ最適化におけるマトロイド
概要：組合せ最適化の文脈では，マトロイドは扱いやすい離散構造の代表として語られることが多い．実際，実行可能領域が部分集合に関して閉じた非空な集合族であるとき，「任意の非負重み付けに対して，貪欲法によって重み和が最適（最大または最小）の実行可能解が求まる」ことと「実行可能領域がマトロイドの独立集合族である」ことは同値であり，このアルゴリズム的な性質でマトロイドを定義することもできる．また，基に関して「 1 要素同士の交換で重みが改善しない」こと（局所的最適性）と「重み和が最適である」こと（大域的最適性）が同値であるという，ある種の凸性を持つことも知られている．さらに，実行可能領域が 2 つのマトロイドの独立集合族の共通部分として表されるマトロイド交叉問題に対しても，完全双対整数性に代表される良い多面体的性質や，様々なアイデアに基づく効率的なアルゴリズムが知られている．本講演では，マトロイドの凸性と貪欲法の話から始めて，マトロイド交叉とその先にあるマトロイド・マッチングの理論と応用例を紹介する．