組合せ数学セミナー
発表内容の概要
一般荷重ゼータは一般佐藤ゼータともよばれ、
有限有向グラフに対して定義される組合せ論的ゼータである。
よって「三種の表示」、すなわち指数表示・オイラー表示・橋本表示を
自然に持つことが理解される。
この講演では、有限単純グラフの対称有向グラフに対する場合には、
一般荷重ゼータがさらに伊原表示まで持つことを紹介する。
Richard Stanleyは有限半順序集合から２種類の格子凸多面体，order polytope
とchain polytopeを定義した．この２つの多面体は一般には異なるが，非常に
近い性質を持つ．特に，膨らました格子凸多面体に含まれる格子点の数え上げ
に関する不変量であるEhrhart多項式は，同じ有限半順序集合のorder polytope
とchain polytopeに対して一致している．さらにそのEhrhart多項式は，付随す
る有限半順序集合のP-partitionの数え上げと一致している．一方，John
StembridgeはP-partitionの類似として，enriched P-partitionを定義した．
本講演では，有限半順序集合から２種類の格子凸多面体，enriched order polytope
とenriched chain polytopeを定義し，その性質，特に，enriched P-partition
との関連について紹介する．
本講演は関西学院大学の大杉英史氏との共同研究に基づく．
n文字の置換からランダムに一つ選ばれた置換の性質を調べる，という問題は
古典的でありよく議論されてきた．
特に，選ばれた置換を巡回置換の積として表現したときの長さ毎の巡回置換の
数やその和（全ての長さの巡回置換の数）は興味の対象で，nが大きい場合に
それらがどういう漸近挙動を示すかが調べられてきた．
本講演では，ランダムな置換および関連する組み合わせ構造についていくつか
の結果を紹介した後，講演者が得た結果を紹介する．
本講演では既存のグラフゼータを特別な場合にもつ「一般荷重ゼータ」の伊原
型行列式表示（以下，伊原表示）を導出する．グラフゼータは２０１１年に今
野紀雄氏と佐藤巌氏により量子ウォークとの接点が示されており，特に量子
ウォークの性質の解明に貢献していることから，その注目度は年々高まってい
る．今回はその接点に触れつつ，グラフゼータの伊原表示について述べる．
また，今回の荷重やグラフの設定は大半のグラフゼータの設定を包含するもの
であり，一般荷重ゼータの伊原表示は，言わば伊原表示の再定義となる．
A graph puzzle ${\rm Puz}(G)$ of a graph $G$ is defined as follows.
A configuration of ${\rm Puz}(G)$ is a bijection from the set of vertices
of a board graph $G$ to the set of vertices of a pebble graph $G$.
A move of pebbles is defined as exchanging two pebbles which are adjacent
on both a board graph and a pebble graph.
For a pair of configurations $f$ and $g$, we say that $f$ is equivalent to
$g$ if $f$ can be transformed into $g$ by a sequence of finite moves.
Let ${\rm Aut}(G)$ be the automorphism group of $G$, and let ${\rm 1}_G$ be
the unit element of ${\rm Aut}(G)$.
The pebble exchange group of $G$, denoted by ${\rm Peb}(G)$, is defined as
the set of all automorphisms $f$ of $G$ such that ${\rm 1}_G$ and $f$ are
equivalent to each other.
In this talk, some basic properties of ${\rm Peb}(G)$ are studied.
Among other results, it is shown that for any connected graph $G$, all
automorphisms of $G$ are contained in ${\rm Peb}(G^2)$, where $G^2$ is a
square graph of $G$.
This work is a joint work with Tatsuoki Kato and Tomoki Nakamigawa.
アブストラクト：本講演では辺に色が付いたグラフの分割問題について議論する。
グラフの各頂点に隣接する辺の色数をその点における色次数といい，グラフの各
頂点における色次数の最小値を最小色次数と呼ぶことにする．講演者は，「辺着
色グラフGの最小色次数がa+b+1以上であれば，グラフGの頂点集合をA, B二つに
分割して，Aで誘導される部分グラフの最小色次数がa以上，Bで誘導される部分
グラフの最小色次数がb以上となるような分割が存在する」と予想している．本講
演では，この予想に対する部分的解決について紹介し，この予想が関連する他の
問題についても紹介する．
本講演で扱う話題は，西北工業大学のRuonan Liと山東大学のGuanghui Wangとの
共同研究に基づく．
トップに戻る