半グラフに関する過去記事を見返していて、「これマズイな」と思ったところがあります。
- 半グラフの併置を余デカルト積〈圏論的直和〉だと書いていた。
- 半グラフ変形に切断〈cut〉を入れていた。
明白に間違っていた箇所は一箇所ずつで、追記で修正すれば済みます。しかし、間違ってしまった／ハマってしまった背景には混乱しがちな事情があるので、この事情を明らかにしておきます。また、ボリソフ／マニン半グラフの圏に対する新しい見方も提案します。$`\newcommand{\cat}[1]{\mathcal{#1}}
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\mrm}[1]{\mathrm{#1}}
\newcommand{\msc}[1]{\mathscr{#1}}
\newcommand{\msf}[1]{\mathsf{#1}}
%\newcommand{\mbb}[1]{\mathbb{#1}}
\newcommand{\In}{\text{ in }}
\newcommand{\msc}[1]{\mathscr{#1}}
%\newcommand{\mbb}[1]{\mathbb{#1}}
\newcommand{\In}{\text{ in }}
%\newcommand{\twoto}{\Rightarrow }
%\newcommand{\op}{\mathrm{op} }
%\newcommand{\id}{\mathrm{id}}
%\newcommand{\u}[1]{\underline{#1}}
%\newcommand{\o}[1]{\overline{#1}}
%\newcommand{\T}[1]{\text{#1}}
\newcommand{\hyp}{ \text{－} }
%\newcommand{\Iff}{ \Leftrightarrow }
%\newcommand{\Imp}{ \Rightarrow }
\newcommand{\proto}{\not\to}
\newcommand{\pcomp}{\diamond}
`$
内容：
- 準備
- ややこしい同義語・曖昧多義語
- 間違っていた： 併置は余デカルト積ではない
- 間違っていた： 切断は射ではない
- 射、変換写像、コンビネータ
- 半グラフ・コンビネータ
- 半グラフ・コンビネータと半グラフ変形の関係
- ボリソフ／マニン半グラフ圏の新しい定式化
準備
ボリソフ／マニンの半グラフは次で定義しています。
上記記事で定義した $`\mbf{semigraph}`$ は半グラフの形状グラフ（実体は有向グラフ）です。有向グラフからは自由圏 $`\mrm{FreeCat}(\mbf{semigraph})`$ が作れますが、自由圏も再び $`\mbf{semigraph}`$ と書きます（名前のオーバーロード）。
次の関手圏が定義できます。
$`\quad \mbf{SemiGraphC} := \mbf{CAT}(\mbf{semigaph}, \mbf{Set})`$
これは関手圏なので、射は自然変換です。末尾の $`\mbf{C}`$ は Category の意味です。この固有名は「半グラフの二重圏と半グラフ変形 // 半グラフ射」で導入しました。
上記の関手圏のコア亜群〈core groupoid〉を次のように名付けます。
$`\quad \mbf{SemiGraphG} := \mrm{Core}(\mbf{SemiGraphC}) \\
\qquad = \mrm{Core}(\mbf{CAT}(\mrm{semigaph}, \mbf{Set}) )`$
末尾の $`\mbf{G}`$ は Groupoid の意味です。
半グラフ変形を射とする半グラフ達の圏は $`\mbf{BM}`$ とします。名前の由来を「集合、商集合、標準射影： 半グラフ変形のために // 動機： 半グラフ変形の標準形」から引用すると：
BM は Borisov, Manin からです。このようなネーミングをするのは、“半グラフ達の圏”が人により違っているからです（「半グラフの様々な定義」参照）。
そもそも半グラフの圏がイッパイあるので、$`\mbf{SemiGraphC}`$ も $`\mbf{BMSemiGraphC}`$ とでもすべきでしょうが、今の文脈ではボリソフ／マニン流の半グラフしか扱わないのでいいとしましょう。
$`\mbf{BM}`$ のコア亜群は次のように名付けます。
$`\quad \mbf{BMG} := \mrm{Core}(\mbf{BM})`$
$`\mbf{SemiGraphC}`$ と $`\mbf{BM}`$ は違う圏（性質が全然違う）ですが、対象集合〈set of objects〉とコア亜群を共有しています。
$`\quad |\mbf{BM}| = |\mbf{SemiGraphC}|\\
\quad \mrm{Core}(\mbf{BM}) = \mrm{Core}(\mbf{SemiGraphC})
`$
ボリソフ／マニン半グラフでハマる原因のひとつは、$`\mbf{SemiGraphC}`$ と $`\mbf{BM}`$ がまったく違う圏でありながら混同しがちなことでしょう。$`\mbf{SemiGraphC}`$ はある意味でありきたりの（よくある）圏ですが、$`\mbf{BM}`$ は非常に変わった異質の圏です。
なお、この記事で参照するボリソフ／マニン半グラフに関する参考文献は次の3つです。
- [BM06-11]
- Title: Generalized operads and their inner cohomomorphisms
- Authors: D. Borisov, Yu. I. Manin
- Submitted: 27 Sep 2006 (v1), 7 Jan 2011 (v5)
- Pages: 71p
- URL: https://arxiv.org/abs/math/0609748
- [BK22-]
- Title: Trees, graphs and aggregates: a categorical perspective on combinatorial surface topology, geometry, and algebra
- Authors: Clemens Berger, Ralph M. Kaufmann
- Submitted: 25 Jan 2022
- Pages: 48p
- URL: https://arxiv.org/abs/2201.10537
- [DHR20]
- Title: Circuit algebras are wheeled props
- Authors: Zsuzsanna Dancso, Iva Halacheva, Marcy Robertson
- Submitted: 21 Sep 2020
- Pages: 29p
- URL: https://arxiv.org/abs/2009.09738
ややこしい同義語・曖昧多義語
半グラフに対するいくつかの操作があります。それらを動詞の形で並べます。1つの箇条書き項目にある語は同義語です。
- bridge, graft, connect
- cut, disconnect
- shrink, contract
- merge, identify, product
- substitute, graft, insert
ボリソフ／マニン [BM06-11] では、graft, contract, merge（名詞は merger）が使われていたのですが、僕は bridge, shrink, merge に変えました。contract〈縮約する〉 を shrink〈縮減する〉 に変えた理由を「半グラフの二重圏と半グラフ変形」から引用すると：
グラフ理論では、内部辺の縮減〈実縮減〉を辺の縮約〈edge contraction〉と呼びます。このため、半グラフにおける縮減（実縮減も仮想縮減も）「縮約〈contraction〉」と呼ぶのが普通です。が、縮減を縮約と呼ぶのはかなりミスリーディングです。
幾何的〈位相的〉意味で可縮〈contractible | 縮約可能〉というときの幾何的縮約操作は、サイクルを一点に潰すことはできません。しかし、半グラフの縮減操作は自己ループ辺を潰すことができます。つまり、半グラフ縮減操作は、半グラフの幾何的・ホモトピー的性質を変えてしまうことができます。幾何的〈位相的〉縮約とは違います。また、テンソル計算やトレース付きモノイド圏のストリング図における縮約は、外部辺の架橋〈bridging〉（または架橋した後で縮減）に対応します。架橋と縮減は別な操作です。といった事情で、半グラフに対して「縮約〈contraction〉」は使いません。
graft〈接ぎ木する〉 を bridge〈架橋する〉に変えたのは、graft が substitute〈置き換える〉の意味で使われることがあるからです。特に、ツリーに対するリーフの置き換え〈substitution〉は接ぎ木〈grafting〉と呼ばれます。
ところで、"substitution" は「置換」と訳していたのですが、"permutation" が一緒に出てくると（実際一緒に出てくる）困ります。"permutation" を「置換」にして、"substitution" は「代入」にするとか、ですね。
半グラフを扱う著者達のほとんどは、半グラフを単に「グラフ」を呼んでいます。半グラフだけを扱う文脈では問題ないですが、より広い文脈では、「グラフ」は有向グラフを意味するか、または有向グラフと無向グラフの総称です。すべてを一緒に扱うことがあるので、僕は、半グラフを単に「グラフ」と略称はしません。
一方で僕は、半グラフ、ワイヤリング図、ストリング図テンプレートをあまり区別していません（態度が一貫してないかも）。ワイヤリング図とストリング図テンプレートは完全に同義語として問題ありませんが、半グラフとワイヤリング図の定義は少し違います（同じにする人もいますが）。しかし、次の事実があります。
- 半グラフと無向ワイヤリング図は一対一対応する。
- 有向半グラフとワイヤリング図は一対一対応する。
したがって、半グラフに関する議論と無向ワイヤリング図に関する議論は同じことです。
例えば、以下の過去記事で「半グラフ」と呼んでいるものは、無向ワイヤリング図です。
最近の記事「ボリソフ／マニン半グラフと半グラフ変形の形式的定義」の定義は、ボリソフ／マニンのオリジナルの定義です。
間違っていた： 併置は余デカルト積ではない
以下の2023年の記事達には「余デカルト圏」という言葉が出てきます。
この当時は、スケマティック系（当初はスケマティック圏）の構成素の圏 $`\cat{C}`$ を余デカルトだと想定していたので間違いではありません。この当時は、$`\mbf{BM}`$ は“後から組み立てる”つもりでいました。今は、最初から $`\mbf{BM}`$ を使うように変更があったのです。
早い時期から半グラフの直和も考えています。
- 型付き半グラフと指標（2023年8月）
上記過去記事は、$`\mbf{SemiGraphC}`$（過去記事内では $`\mbf{SemiGraph}`$）において直和を定義しているので問題ないです。$`\mbf{SemiGraphC}`$ においては、半グラフの併置は実際に圏論的直和〈余デカルト積〉になっています*1。
間違ったのは、次の最近の記事です。
おそらく過去記事の引用に引きずられて、迂闊にも $`\mbf{BM}`$ が余デカルト圏であるかのような記述がありました。「余デカルト」に打ち消し線〈取り消し線〉を引いて修正します。
「型付き半グラフと指標 // 半グラフの直和」で定義されている直和は、$`\mbf{BM}`$ 内では圏論的直和〈余デカルト積〉にはなってないのです。単なるモノイド積です。
$`\mbf{BM}`$ の射は半グラフ準同型射ではなくてグラフ変形です。直和に対する標準入射〈canonical injection〉は（一般には）半グラフ変形になりません。したがって、圏論的直和の条件を満たさないのです。
よく知られた例で言えば、集合の直積は集合圏の圏論的直積ですが、関係圏（集合達と関係達の圏）では圏論的直積ではなくて単なるモノイド積です。事物として同じでも、環境である圏により圏論的直和・直積になるかどうかは変わります。
「型付き半グラフと指標 // 半グラフの直和」で定義した直和は：
- 圏 $`\mbf{SemiGraphC}`$ においては圏論的直和
- 圏 $`\mbf{BM}`$ においては圏論的直和ではなくて、単なるモノイド積
混乱を避けるために、今後 $`\mbf{BM}`$ を語る文脈においては「直和」ではなくて「半グラフの併置モノイド積〈juxtaposition monoidal product〉」あるいは単に「併置〈juxtaposition〉」を使います。
間違っていた： 切断は射ではない
2023年の記事「半グラフの二重圏と半グラフ変形 // 半グラフ・プロ射／半グラフ変形」において：
次のような基本変形操作を組み合わせた変形が半グラフ・プロ射です。
- 内部辺の切断
- 外部辺の架橋
- 内部辺の縮減
- 外部辺の縮減
これは、頂点の同一視〈頂点併合 | merger〉が欠けています。が、末尾の「追記： 頂点同一視」にその旨は書いています。問題は、切断をグラフ変形に入れていることです。切断はグラフ変形には入れません。他の記事では、ちゃんと切断を除外しているのですが。
「半グラフ変形とDead-Or-Alive構造 // 半グラフ架橋・縮減変形」より：
このなかで、切断を使わずに、架橋と縮減（実縮減と仮想縮減）と頂点同一視から構成された半グラフ変形を半グラフ架橋・縮減変形〈semigraph bridging-shrinking deformation〉と呼ぶことにします。
切断は扱いにくい面があるので、架橋・縮減変形だけを考えることは理にかなっています。ボリソフ／マニン〈D. Borisov, Yu. I. Manin〉、コステロ〈Kevin Costello〉、バーガー／カウフマン〈Clemens Berger, Ralph M. Kaufmann〉などが扱っている半グラフ変形は架橋・縮減変形です。
「メタ計算メカニズムとしての半グラフ変形」より：
内部辺を切り分ける切断〈cutting〉は指令に入れてません。
間違いの修正は箇条書きの一項目を削除するだけですが、「切断がグラフ変形ではないとすると、それは一体何なんだ？」という問題が生じます。切断を使った解剖〈dissection | 腑分け | 切り分け分解〉という操作もあります。切断や解剖の位置付けをハッキリさせたいところです。
射、変換写像、コンビネータ
$`\mbf{SemiGraphC}`$ と $`\mbf{BM}`$ は対象集合とコア亜群を共有しますが違う圏です。これらを区別するために、$`\mbf{SemiGraphC}`$ の射を半グラフ準同型射、$`\mbf{BM}`$ の射はグラフ変形と呼び分けていました。
しかし、[BM06-11], [BK22-], [DHR20] のいずれにおいても、グラフ変形を単に「射〈morphism〉」と呼んでいます。特に [BM06-11] では変形理論〈deformation theory〉の意味の「変形」が登場するので deformation は使えなかったでしょう。[BK22-] では（deformation ではなくて）mutation が別な半グラフ操作の意味で使われています。
もし、$`\mbf{BM}`$ の射を単に「半グラフ射」と呼ぶと、$`\mbf{SemiGraphC}`$ の射と区別できなくなります。そこで、$`\mbf{SemiGraphC}`$ の射は半グラフ変換写像〈semi-graph transformation map〉と呼び替えることにします。$`\mbf{SemiGraphC}`$ の射は自然変換なので、「変換」を入れました。
それとは別に、幾つかの半グラフを受け取って半グラフを返すような関数を半グラフ・コンビネータ〈semi-graph combinator〉と呼ぶことにします。引数〈argument〉の個数を $`n`$ として、半グラフ・コンビネータはおおよそ次の形です。
$`\quad |\mbf{BM}|^n \to |\mbf{BM}| \In \mbf{SET}`$
もっと精密な形〈プロファイル〉は後述します。
これで3つの異なる概念を区別できるようになりました。
- 半グラフ変形 ＝ 半グラフ射
- 半グラフ変換写像
- 半グラフ・コンビネータ
これら異なる3つの概念がゴチャゴチャになってしまうことも、半グラフのハマリ所です。
半グラフ・コンビネータ
半グラフの内部辺を切断〈cut〉する操作について考えます。切断は、半グラフを受け取って半グラフを返す関数ですが、引数に半グラフだけではどの内部辺を切断するか分かりません。したがって、引数は次の2つです。
- 半グラフ $`A`$
- $`A`$ の内部辺 $`e`$
半グラフ $`A`$ の内部辺 $`e`$ を切断した結果である半グラフは
$`\quad \mrm{Cut}(A, e)`$
と書けます。2つの引数 $`A, e`$ を独立に選ぶわけにはいきません。半グラフ $`A`$ を選んだ後でその内部辺 $`e`$ を選ぶことになります。つまり、半グラフ・コンビネータ $`\mrm{Cut}`$ の引数型は依存型です。
依存型のひとつであるシグマ型（集合の総和）を使って $`\mrm{Cut}`$ のプロファイル（入出力の仕様）を書くと次のようです。
$`\quad \mrm{Cut} : \sum_{A\in |\mbf{BM}|} IE(A) \to |\mbf{BM}| \In \mbf{SET}`$
ここで、$`IE(A)`$ は、半グラフ $`A`$ の内部辺〈internal edge〉達の集合です。
依存型を使うと、他の半グラフ・コンビネータのプロファイルも正確に書けます。準備として、集合 $`X`$ に対する $`X^{[2]}`$ を次のように定義します。
$`\quad X^{[2]} := \{(x, y)\in X^2\mid x \ne y\}`$
他に次の記法を使います。
- $`BE(A)`$ ： $`A`$ の境界辺〈外部辺〉の集合（境界フラグの集合と同型）
- $`V(A)`$ ： $`A`$ の頂点の集合
境界辺の架橋：
$`\quad \mrm{Bridge} : \sum_{A\in |\mbf{BM}|} BE(A)^{[2]} \to |\mbf{BM}| \In \mbf{SET}
`$
内部辺の縮減：
$`\quad \mrm{Shrink} : \sum_{A\in |\mbf{BM}|} IE(A) \to |\mbf{BM}| \In \mbf{SET}
`$
外部辺の縮減〈仮想縮減〉：
$`\quad \mrm{VShrink} : \sum_{A\in |\mbf{BM}|} BE(A)^{[2]} \to |\mbf{BM}| \In \mbf{SET}
`$
頂点の併合：
$`\quad \mrm{Merge} : \sum_{A\in |\mbf{BM}|} V(A)^{[2]} \to |\mbf{BM}| \In \mbf{SET}
`$
2つの半グラフの併置モノイド積の対象パートも半グラフ・コンビネータとして書けます。
2つの半グラフの併置：
$`\quad \mrm{Juxta} : |\mbf{BM}|^2\to |\mbf{BM}| \In \mbf{SET}
`$
半グラフの解剖〈dissection | 腑分け | 切り分け分解〉は、すべての内部辺を切断した結果である半グラフです。次のような半グラフ・コンビネータです。
解剖：
$`\quad \mrm{Diss} : |\mbf{BM}| \to |\mbf{BM}| \In \mbf{SET}
`$
半グラフの完全縮減〈完全縮約 | {full| total} {shrinking | contraction}〉は、すべての内部辺を縮減した結果である半グラフです。次のような半グラフ・コンビネータです。
完全縮減：
$`\quad \mrm{FullShrink} : |\mbf{BM}| \to |\mbf{BM}| \In \mbf{SET}
`$
半グラフの完全併合〈full merger〉は、すべての頂点を一点に併合した結果である半グラフです。次のような半グラフ・コンビネータです。
完全併合：
$`\quad \mrm{FullMerge} : |\mbf{BM}| \to |\mbf{BM}| \In \mbf{SET}
`$
完全縮減の後に完全併合する半グラフ・コンビネータは潰し〈crush〉と呼ぶことにします。
潰し：
$`\quad \mrm{Crush} : |\mbf{BM}| \to |\mbf{BM}| \In \mbf{SET}
`$
半グラフを潰すと、頂点は1個だけになり、すべての内部辺は消滅します。境界辺〈外部辺〉は残ります。
半グラフ・コンビネータと半グラフ変形の関係
前節で出した半グラフ・コンビネータと $`\mbf{BM}`$ の射（半グラフ変形）は深く関係しています。そのため、半グラフ・コンビネータと半グラフ変形がゴッチャになるのです。
4つの半グラフ・コンビネータ $`\mrm{Bridge}`$ 、$`\mrm{Shrink}`$ 、$`\mrm{VShrink}`$ 、$`\mrm{Merge}`$ はそれぞれに対応するグラフ変形を持ちます。半グラフ・コンビネータに対応する射を先頭小文字の名前で表わすことにします。
$`\quad \mrm{bridge}(A, s, t) : A \to \mrm{Bridge}(A, s, t) \In \mbf{BM}`$
$`\quad \mrm{shrink}(A, e) : A \to \mrm{Shrink}(A, e) \In \mbf{BM}`$
$`\quad \mrm{vshrink}(A, s, t) : A \to \mrm{VShrink}(A, s, t) \In \mbf{BM}`$
$`\quad \mrm{merge}(A, v, w) : A \to \mrm{merge}(A, v, w) \In \mbf{BM}`$
これらの射達は、圏 $`\mbf{BM}`$ の（up-to-isoの）生成系になります。$`\mbf{BM}`$ を生成系と関係系〈generators and relations〉により記述する話はバーガー／カウフマン [MB22-] にあります。
半グラフ・コンビネータ $`\mrm{Cut}`$ に対応する半グラフ・変形はありません。半グラフ変形としての内部辺の切断は禁止されています。しかし、$`\mrm{Cut}`$ から作った半グラフ・コンビネータ、例えば解剖 $`\mrm{Diss}`$ は重要です。
結局、半グラフ変形は同型を除けば（up-to-isoで）半グラフ・コンビネータで表現可能だが、逆は成立しないということです。特に、切断は半グラフ・コンビネータですが、対応する半グラフ変形を持ちません。
ボリソフ／マニン半グラフ圏の新しい定式化
圏 $`\mbf{BM}`$ は、「ボリソフ／マニン半グラフと半グラフ変形の形式的定義 // ボリソフ／マニン半グラフ」のように定義できます。が、コンビネータ一式を備えた亜群とみなしたほうが都合がいいと思います。
まず、亜群 $`\mbf{MBG}`$（ボリソフ／マニン亜群〈Borisov-Manin groupoid〉）を考えます。この亜群に、既に述べた4つの半グラフ・コンビネータ $`\mrm{Bridge}`$ 、$`\mrm{Shrink}`$ 、$`\mrm{VShrink}`$ 、$`\mrm{Merge}`$ を一緒に考えます。4つ（4種類）のコンビネータ達の組み合わせにより、たくさんの複合コンビネータを作れます。
亜群の射である半グラフ同型〈semi-graph isomorphism〉と基本コンビネータ（4種）／複合コンビネータから圏 $`\mbf{BM}`$ は構成できます。圏 $`\mbf{BM}`$ がプライマリーに在るというよりは、コンビネータ付き亜群の表現手段が $`\mbf{BM}`$ だとみなすことができます。
亜群 $`\mbf{BMG}`$ に最初から備わった対象達と同型達に、コンビネータ達から生成系・関係系スタイルで構成された構造が $`\mbf{BM}`$ だと考えます。主役は、半グラフ変形から半グラフ・コンビネータに移ります。
ボリソフ／マニンの圏を、ボリソフ／マニン亜群上の依存的なコンビネータ計算の体系とみなせば、普通のありきたりな圏 $`\mbf{SemiGraphC}`$ と混同することもなくなるでしょう。
他の点においても、スケマティック系は亜群とコンビネータ中心の定式化が都合が良いように思えます。
