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

5/20(金): 八森正泰（筑波大学）
Nonpureな単体的複体のsequential partition

    単体的複体のファセット(極大面)がすべて同じ次元であるとき、
    その単体的複体はpureであるといい、そうでないときにはnonpureであるという。
    単体的複体が分割可能であるとは、ファセットを上端とする区間で分割できる
    ことをいう。単体的複体の分割可能性については、pureな場合にはh-列との
    強い関連があることなどが知られているが、nonpureな場合にはあまりよい性質が
    言えない。本講演では、nonpureな単体的複体において
    「よい性質を要請する分割可能性」を4種類導入し、それらの間の関係を示す。
  

7/29(金): Chong ZHENG（早稲田大学）
On the Weighted Tutte-Grothendieck Polynomials of Graphs

In this talk, we introduce the concept of the weighted (harmonic) chromatic
polynomials of graphs and discuss some of its properties.

We also present the notion of the weighted (harmonic) Tutte-Grothendieck
polynomials of graphs and give a generalization of the recipe theorem
between the harmonic Tutte-Grothendieck polynomials graphs and the harmonic
Tutte polynomials of matroids. Moreover, we give some constructions of the
weighted (harmonic) Tutte-Grothendieck invariants for graphs and the weighted
(harmonic) Tutte invariants for matroids. Finally, we give a remark on the
categorification of the harmonic chromatic polynomials of graphs and harmonic
Tutte polynomials of matroids.
  

10/31(月): 佐竹翔平（明治大学）
エクスパンダーグラフと暗号学的ハッシュ関数

エクスパンダーグラフは強い連結性をもつスパースなグラフであり,
組合せ論, 整数論, 符号理論, 暗号理論などへの幅広い理論的応用が知られている.
特に暗号理論の文脈では, 1990年代初頭にZe'morとTillichらによって
エクスパンダーCayleyグラフによる暗号学的ハッシュ関数の構成が提案され,
2009年にはCharles, LauterおよびGorenによって一般のエクスパンダーグラフに基づく
暗号学的ハッシュ関数 (CGLハッシュ関数)が定式化された.
CGLハッシュ関数は耐量子計算機暗号などの現代の暗号理論の理論的基盤を与えるだけでなく,
その衝突困難性・一方向性などの解析を通して, 組合せ論, 整数論, 群論などの数理科学との
興味深いインタラクションも創り出している.
本講演では, 以上の背景を概説し, 最近の講演者の研究成果である弧推移的なエクスパンダー
グラフに基づくCGLハッシュ関数の構成に関して紹介する.
本講演の一部はHyungrok Jo 特任助教 (横浜国立大学)との共同研究に基づく.
  

2/22(水): 安福智明(国立情報学研究所)
長方形型ヤング図形を開始局面とする連続フック引き抜きゲームについて

フック引き抜きゲームとは，2人のプレイヤーがヤング図形から交互にフックを抜いて
いき，最後にフックを抜いたプレイヤーの勝ちであるという組合せゲームである．
また，その必勝判定に用いられるGrundy数は，近年表現論との関係が明らかとなった．
本講演では，これまでに解析された様々なフック引き抜きゲームについて他の数学分野
との繋がりを交えながら紹介し，さらに講演者らが考案した連続フック引き抜きゲーム
について，その必勝判定，とくにGrundy数の解析について紹介する．なお，本講演は多
田将人氏（筑波大学）との共同研究に基づく．