組合せ論セミナー

 


第48回 2013年12月10日 15:30〜17:00

和田山正 (名古屋工業大学)「ホログラフィック変換とマックウィリアムス恒等式」

ホログラフィック変換と呼ばれる分配関数に対する変換は変換自体は単純な線形変換であるが、これを利用することで統計物理における分配関数の高温展開、マックウィリアムス恒等式等の非自明な恒等式を自然に導くことができる。また、この変換は理論計算機科学におけるホログラフィックアルゴリズムの基礎を与える。近年、Al-Bashabsheh と Maoによる正規因子グラフに基づくホログラフィック変換の解釈が明らかとなり、道具としてホログラフィック変換を利用しやすい環境が整ってきた。本セミナーでは、ホログラフィック変換の基礎をマックウィリアムス恒等式の図式的証明を通して説明するとともに、講演者らが最近進めている集合被覆問題に関する重み母関数の双対表現、包除原理とホログラフィック変換の関係などについて紹介する。