有向グラフであって、有向辺のソースとして“複数の頂点のリスト”を許す構造が複グラフ〈multigraph〉です。複グラフがあると、それからある種の多項式関手を定義できます。その多項式関手は、複グラフの頂点集合をインデキシング集合としてモノイド圏に値を持つファミリーに対して作用します。$`\newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\In}{\text{ in } }
\newcommand{\cat}[1]{\mathcal{#1}}`$
内容：
複グラフ
「複グラフ」という呼び名については「亜群上の豊穣複グラフ： 豊穣化・基礎強化の例 // 形容詞「複」「多」、それとオペラッド」を参照してください。
複グラフ〈multigraph〉 $`M`$ は次の構成素からなります。（「亜群上の豊穣複グラフ： 豊穣化・基礎強化の例 // 複グラフ」にも記述があります。）
- 集合 $`X`$ ： 頂点の集合
- 集合 $`E`$ ： 複辺〈multiedge〉の集合
- 写像 $`\mrm{src}: E \to \mrm{List}(X)`$ ： 複辺にソース〈始点〉リストを対応させる写像
- 写像 $`\mrm{trg}: E \to X`$ ： 複辺にターゲット〈終点〉を対応させる写像
$`M = (X, E, \mrm{src}, \mrm{trg})`$ と書けます。この定義から少し変更した定義を作ります。変更した定義では、複グラフは $`M = (X, P, Q)`$ と書けます。$`P, Q`$ は次のようです。
$`\quad P := \lambda\, x\in X. \{ e\in E \mid \mrm{trg}(e) = x\}\\
\text{For }b \in X\\
\quad Q_b := \lambda\, f\in P(b).\mrm{src}(f)
`$
$`P`$ はファミリーで、$`Q`$ は依存関数です。次のように書けます。
$`\quad P: X \to |{\bf Set}| \In {\bf SET}\\
\quad Q \in \prod_{b \in X} \mrm{Map}(P(b), \mrm{List}(X))
`$
$`b\in X`$ に対する $`P(b)`$ は、$`b`$ をターゲットとするすべての複辺の集合です。$`Q_b : P(b) \to \mrm{List}(X)`$ は、複辺にそのソースリスト*1を対応させる写像です。$`Q_b`$ を $`\uparrow_b`$ とも略記します。
- $`\uparrow_b f = Q_b(f)`$ は、$`b`$ をターゲット〈終点〉とする複辺 $`f`$ のソースリスト
この記法は、有向コンテナの双対であることを強調するためです。実際、有向コンテナと双対的な定義で、色付きオペラッド〈色彩的複圏〉を定義できます。有向コンテナについては次の記事を参照してください。
順序総積と余極限
$`\cat{V} = (\cat{V}, \otimes, I)`$ （記号の乱用）をモノイド圏（対称モノイド圏でなくてもよい）とします。集合 $`X`$ からの写像 $`F: X \to |\cat{V}|`$ があるとします。ファミリーの記法を使えば次のように書けます。
$`\quad F = (X, F) \in \mrm{Fam}[X](\cat{V})`$
ファミリーについては「一般化されたファミリーの圏」と、そこからリンクされている関連記事を参照してください。
$`\vec{a}`$ は、$`X`$ の要素のリストとします。
$`\quad \vec{a} = (a_1,\cdots, a_n) \in \mrm{List}(X)`$
ファミリー $`F`$ とリスト $`\vec{a}`$ に対して、順序付きの総積を次のように定義します。
$`\quad \overset{\to}{\prod}_{x:\vec{a}} F(x) := F(a_1)\otimes \cdots \otimes F(a_n) \in |\cat{V}|`$
モノイド圏 $`\cat{V}`$ に対称性を仮定してないので、掛け算の順番を変えると、結果が変わるだけでなくて、異なる順番の掛け算結果のあいだの系統的同型関係を期待できません。
モノイド圏 $`\cat{V}`$ は、さらに離散余完備だとします。これは、任意の集合から $`\cat{V}`$ へのファミリーに（それを関手とみて）余極限が存在することです。任意の余極限とモノイド積は交換するとします。これは次が成立することです。
$`\text{For } F:X \to |\cat{V}| \In {\bf SET}\\
\text{For }V \in |\cat{V}|\\
\quad \mrm{colim}_{x\in X} (F(x)\otimes V) = (\mrm{colim}_{x\in X} F(x)) \otimes V\\
\quad \mrm{colim}_{x\in X} ( V \otimes F(x)) = V\otimes (\mrm{colim}_{x\in X} F(x))
`$
余極限を総和の記号で書くと、次の形になります。
$`\text{For } F:X \to |\cat{V}| \In {\bf SET}\\
\text{For }V \in |\cat{V}|\\
\quad \sum_{x\in X} (F(x)\otimes V) = (\sum_{x\in X} F(x)) \otimes V\\
\quad \sum_{x\in X} (V \otimes F(x)) = V \otimes (\sum_{x\in X} F(x))
`$
余極限とモノイド積の交換は、分配法則のようなものです。
$`S \subseteq \mrm{List}(X)`$ とすると、集合 $`S`$ に属するリストに渡って、順序付き総積の余極限を取ることができます。それは次のように書けます。
$`\quad \mrm{colim}_{\vec{a}\in S} \overset{\to}{\prod}_{x : \vec{a}} F(x) \;\in |\cat{V}|`$
余極限を総和の記号で書くと、次の形になります。
$`\quad \sum_{\vec{a}\in S} \overset{\to}{\prod}_{x : \vec{a}} F(x) \;\in |\cat{V}|`$
複グラフと自己関手
$`M =(X, P, Q)`$ は複グラフで、$`\cat{V}`$ は離散余完備で、余極限がモノイド積と交換するモノイド圏だとします。複グラフ $`M`$ は、次のような自己関手を定義します。
$`\quad \Phi_M : \mrm{Fam}[X](\cat{V}) \to \mrm{Fam}[X](\cat{V}) \In {\bf CAT}`$
$`\mrm{Fam}[X](\cat{V})`$ は、集合を離散圏とみれば関手圏となるので、次のようにも書けます。
$`\quad \Phi_M : [X, \cat{V}] \to [X, \cat{V}] \In {\bf CAT}`$
$`\Phi_M`$ はまた、離散圏上の前層（または余前層）の圏上の自己関手とも言えます。
$`F \in |[X, \cat{V}]|`$ に対して、$`F' := \Phi_M(F) \;\in |[X, \cat{V}]|`$ と置くと、$`F'`$ は次のように書けます。
$`\quad F'(b) := \mrm{colim}_{f \in P(b)} \overset{\to}{\prod}_{x : Q_b(f)} F(x)`$
余極限を総和の記号で書くと、次の形になります。
$`\quad F'(b) := \sum_{f \in P(b)} \overset{\to}{\prod}_{x : Q_b(f)} F(x)`$
余極限の存在が保証されているので、左辺は $`|\cat{V}|`$ の要素（対象）として（up-to-iso で）確定します。任意の $`b\in X`$ に対して値が確定すれば、ファミリー $`F':X \to |\cat{V}|`$ が（up-to-iso で）確定します。
$`F \mapsto F'`$ という対応は、関手 $`\Phi_M`$ の対象パートしか定義していません。$`\varphi : F \to G`$ というファミリーのあいだの準同型射に対しても、$`\Phi_M(\varphi)`$ を定義する必要があります。さらに、実際に関手であることの確認も必要です。そこらへんの細かいことは、またいずれ（あるいは割愛）とします。
今日のストーリーは、$`\Phi_M`$ は自己関手となればメデタシメデタシなのですが、複グラフに追加の構造を足して、$`\Phi_M`$ を台関手とするモナドを構成することが次のオハナシです。
*1:プログラムのソースコードの意味ではありません。始点となる頂点達のリストです。
