このブログの更新は X（旧Twitter）アカウント @m_hiyama で通知されます。
Follow @m_hiyama

ご連絡は上記 X アカウントに DM にてお願いします。

［参照用 記事］

ボリソフ／マニン半グラフと半グラフ変形の形式的定義

雑記／備忘

最近また半グラフに興味を持っています。半グラフの定義は色々あるので、「半グラフの様々な定義」と「強化ファインマン・グラフとバタニン／バーガー半グラフ」で各種の定義を紹介しています。

一番扱いやすい半グラフの定義は、ボリソフ／マニンによるものでしょう。ボリソフ／マニンの半グラフの圏を調べるための準備として直前の記事「集合、商集合、標準射影： 半グラフ変形のために」も書いています。

半グラフについて調べるときは、三色ボールペンで紙に絵を描きまくっているのですが、なにごとかをちゃんと言うには形式的定義も必要です。この記事では、ボリソフ／マニンの半グラフと半グラフ変形の形式的定義を述べます。$`\newcommand{\cat}[1]{\mathcal{#1}}
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\mrm}[1]{\mathrm{#1}}
%\newcommand{\msc}[1]{\mathscr{#1}}
%\newcommand{\mbb}[1]{\mathbb{#1}}
\newcommand{\In}{\text{ in }}
%\newcommand{\H}{\text{-}}
%\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{\cinj}{\hookrightarrow }
\newcommand{\csurj}{\twoheadrightarrow}
\newcommand{\parto}{\supset\!\to}
`$

内容：

ボリソフ／マニン半グラフ

半グラフについては以下の過去記事達を参照してください。

ここでは、用語と記法の確認だけします。

ボリソフ／マニン半グラフを定義する形状グラフ $`\mbf{semigraph}`$ は次です。

$`\quad \xymatrix {
1 \ar[r]^3 \ar@(ul, dl)[0,0]_4
&2
}`$

$`\mbf{semigraph} \in |\mbf{Graph}|`$ です。「グラフの定義にグラフを使う」ことについては「属性付き半グラフ // 半グラフの定義」を見てください。

ボリソフ／マニン半グラフ $`A`$ は、上記の形状グラフから有限集合圏 $`\mbf{FinSet}`$ へのグラフ射〈graph morphism〉です。

$`\quad A : \mbf{semigraph} \to \mrm{U}(\mbf{FinSet}) \In \mbf{GRAPH}`$

ここで：

  • $`\mbf{GRAPH}`$ は大きい（小さいとは限らない）グラフ〈有向グラフ〉達の圏
  • $`\mbf{Graph}\subseteq \mbf{GRAPH}`$ なので、$`\mbf{semigraph}\in |\mbf{GRAPH}|`$ としてよい。
  • $`\mrm{U}: \mbf{CAT}\to \mbf{GRAPH}`$ は忘却関手

以下の記号と用語を使います。

  1. $`A(1)`$ を $`F(A)`$ と書いて、$`A`$ のフラグ〈flag〉達の集合と呼ぶ。
  2. $`A(2)`$ を $`V(A)`$ と書いて、$`A`$ の頂点〈vertex〉達の集合と呼ぶ。
  3. $`A(3)`$ を $`\beta_A`$ と書いて、$`A`$ の境界写像〈boundary map〉と呼ぶ。
  4. $`A(4)`$ を $`\iota_A`$ と書いて、$`A`$ のパートナー指定対合〈partner designation involution〉と呼ぶ。ペアリング対合〈pairing involution〉、カップリング対合*1〈coupling involution〉とも呼ぶ。

$`\iota_A`$ は対合なので、$`\iota_A;\iota_A = \id`$ です。

次の定義をします。

$`\quad IF(A) := \{f\in F(A)\mid \iota_A(f) \ne f \}`$ （非不動点達の集合）
$`\quad BF(A) := \{f\in F(A)\mid \iota_A(f) = f \}`$ （不動点達の集合）

$`f\in IF(A)`$ なら $`f`$ を内部フラグ〈internal flag〉、$`f\in BF(A)`$ なら $`f`$ を境界フラグ〈boundary flag〉と呼びます。

$`\iota_A|_{IF(A)}`$ も単に $`\iota_A`$ と書くことにします。その他の制限された写像も、もとの写像と同じ記号をオーバーロードします。半グラフ $`A`$ の図式は次のようにも書きます。

$`\quad \xymatrix{
*{BF(A)} \ar@(ul, dl)[0,0]_{\id} \ar[dr]^{\beta_A}
&{}
\\
*{IF(A)} \ar@(ul, dl)[0,0]_{\iota_A} \ar[r]_{\beta_A}
&V(A)
}\\
\quad \In \mbf{FinSet}
`$

$`f, f'`$ のあいだの関係 $`\iota_A(f) = f'`$ から生成される $`F(A)`$ 上の同値関係による商集合を $`E(A)`$ と書きます。$`E(A)`$ の要素（同値類）を $`A`$ の辺〈edge〉と呼びます。商集合への標準射影は $`\pi_A`$ と書きます。次の定義をします。

$`\quad BE(A) := \{e\in E(A) \mid \exists f\in BF(A). \pi_A(f) = e\}`$ （境界フラグの像集合）
$`\quad IE(A) := \{e\in E(A) \mid \exists f\in IF(A). \pi_A(f) = e\}`$ （内部フラグの像集合）

$`e\in IE(A)`$ なら $`f`$ を内部辺〈internal edge〉、$`e\in BE(A)`$ なら $`e`$ を境界辺〈boundary edge〉と呼びます。境界フラグと境界辺を区別しないことも多いですが、ここでは区別します。$`f`$ が境界フラグのとき $`\{f\}`$ が境界辺です。

半グラフの同型射

$`A`$ と $`B`$ が半グラフのとき、そのあいだの同型射は、半グラフの構造を保つ可逆写像〈同型写像〉のペアです。同型射 $`\phi`$ は次の2つの可逆写像からなります。

$`\quad \phi_V : V(A) \overset{\cong}{\to} V(B) \In \mbf{FinSet}`$
$`\quad \phi_F : F(A) \overset{\cong}{\to} F(B) \In \mbf{FinSet}`$

同型射は以下の図式を可換にします。

$`\quad \xymatrix{
F(A) \ar[r]^{\beta_A} \ar[d]_{\phi_F}^{\cong}
&V(A) \ar[d]^{\phi_V}_{\cong}
\\
F(B) \ar[r]_{\beta_B}
&V(B)
}\\
\quad \text{commutative }\In \mbf{FinSet}
`$

$`\quad \xymatrix{
F(A) \ar[r]^{\iota_A} \ar[d]_{\phi_F}^{\cong}
&F(A) \ar[d]^{\phi_F}_{\cong}
\\
F(B) \ar[r]_{\iota_B}
&F(B)
}\\
\quad \text{commutative }\In \mbf{FinSet}
`$

同型射で結ばれる2つの半グラフは、事実上同じものです。

$`\phi_V, \phi_F`$ を可逆とは限らない写像として、半グラフの準同型射〈homomorphism〉を定義できます。半グラフ達と準同型射達で圏を形成しますが、興味の中心はこのような圏ではありません。半グラフ変形を射とする圏を次節で定義します。

半グラフ変形

半グラフ変形〈semi-graph deformation〉は、前節の最後に触れた準同型射とは違います。反対方向の2つの写像から構成されます。

2つの（「一致する1つの」でもかまわない）半グラフ $`A, B`$ に対して、そのあいだの半グラフ変形は次の2つの写像で構成されます。

$`\quad \phi_V : V(A) \to V(B) \In \mbf{FinSet}\\
\quad \phi^F : F(B) \to F(A) \In \mbf{FinSet}
`$

$`\phi_V`$ を半グラフ変形 $`\phi`$ の頂点パート〈vertex part〉、$`\phi^F`$ を半グラフ変形 $`\phi`$ のフラグパート〈flag part〉と呼びます。頂点パートとフラグパートの向きが反対であることに注意してください。頂点パートの向きを、グラフ変形の向きとします。

次の条件を課します。

  • 頂点パート $`\phi_V`$ は全射である。
  • フラグパート $`\phi^F`$ は単射である。

フラグパートの像を生存フラグ〈living flag〉達の集合と呼び、次のように書きます。（「半グラフ変形とDead-Or-Alive構造」で alive flag と書きましたが、alive は名詞の前に置かないようです。）

$`\quad \mrm{Liv}F(\phi) := \mrm{img}(\phi^F)`$

生存フラグ達の集合の $`F(A)`$ における補集合を亡骸フラグ〈dead flag〉達の集合と呼び、次のように書きます。

$`\quad \mrm{Dead}F(\phi) := F(A)\setminus \mrm{Liv}F(\phi)`$

生存フラグは、変形の余域 $`B`$ にコピーされて、$`B`$ のフラグとして生き残ります（be alive）。亡骸フラグは消滅してしまい、$`B`$ にコピーされることはありません。半グラフ変形の基本操作（のひとつ）は、フラグの選択的コピーです。もうひとつの基本操作は頂点の同一視〈vertex identification〉です。余域 $`B`$ は、$`A`$ から選ばれた生存フラグ達と、同一視された頂点達で構成されます。

半グラフ変形 $`\phi`$ のフラグパート $`\phi^F`$ は、写像として可逆とは限りません。しかし次の可逆写像を定義します。

$`\quad \phi^F|^{\mrm{img}(\phi^F)} : F(B) \to \mrm{Liv}F(A) \In \mbf{FinSet}`$

ここで、$`f|^B`$ という書き方は、写像の余域を制限することです。$`\phi^F|^{\mrm{img}(\phi^F)}`$ の逆写像 $`(\phi^F|^{\mrm{img}(\phi^F)})^{-1}`$ を $`\phi_F`$ と書きます。

$`\quad \phi_F : \mrm{Liv}F(A) \to F(B) \In \mbf{FinSet}`$

また、以下の図式で定義される部分関数も $`\phi_F`$ と書きます（オーバーロード）。

$`\quad \xymatrix{
{}
&{\mrm{Liv}F(A)} \ar@{_{(}->}[dl] \ar[dr]^{\phi_F}
&{}
\\
{F(A)}
&{}
&{F(B)}
}\\
\quad \In \mbf{FinSet}
`$

上記の部分関数は次のように書きます。

$`\quad \phi_F : F(A)\parto F(B)\In \mbf{FinSet}`$

半グラフ変形 $`\phi`$ には、もうひとつの構成素としてリカップリング対合 $`\iota_\phi`$ があり、半グラフ変形を構成する全射 $`\phi_V`$ と単射 $`\phi^F`$（あるいは双射 $`\phi_F`$ 、部分単射 $`\phi_F`$）とリカップリング対合 $`\iota_\phi`$ のあいだに色々な条件が付きます。それらは次節で述べます。

半グラフ変形の条件

どのような半グラフ $`A`$ にもカップリング対合〈パートナー指定対合〉$`\iota_A`$ があります。

$`\quad \iota_A : F(A)\to F(A) \In \mbf{FinSet}`$

カップリング対合により、フラグ達から辺（境界辺または内部辺）が構成されます。

半グラフ変形 $`\phi : A \to B`$ のリカップリング対合〈recoupling invlution〉 $`\iota_\phi`$ は、亡骸フラグ集合 $`\mrm{Dead}F(A)`$ 上に新しいカップリングを定義します。

$`\quad \iota_\phi : \mrm{Dead}F(A)\to \mrm{Dead}F(A) \In \mbf{FinSet}\\
\text{where }\\
\quad \iota_\phi ; \iota_\phi = \id\\
\quad \mrm{Fixpoint}(\iota_\phi) = \emptyset
`$

リカップリング対合は不動点を持たないことに注意してください。

亡骸フラグは、余域〈ターゲット〉 $`B`$ にコピーされずに消滅します。消滅するモノ達に新規のカップリングを導入しても意味がないように思えますが、亡骸フラグが“どのように消滅したか”の情報をリカップリングにより記述します。亡骸フラグの“消滅の仕方”は次のニ種類があります。

仮想縮減による消滅は、追加情報がないとまったく不明です。が、実縮減は内部辺（内部フラグのカップル）の消滅なので、リカップリング情報がなくても推測できます。なので、ほんとに必要なものは境界亡骸フラグ上のリカップリング対合だけです。が、ボリソフ／マニンの定義では亡骸フラグ全体でリカップリング対合が定義されています。

すぐ上の段落に書いた事情は次の可換図式で表現できます。

亡骸内部フラグ・対合公式〈dead internal flag involution formula〉：

$`\quad \xymatrix{
\mrm{Dead}IF(\phi) \ar[r]^{\iota_\phi} \ar@{_{(}->}[d]
&{\mrm{Dead}IF(\phi)} \ar@{_{(}->}[d]
\\
F(A) \ar[r]_{\iota_A}
&F(A)
}\\
\quad \text{commutatiev }\In \mbf{FinSet}
`$

ここで、$`\mrm{Dead}IF(\phi)`$ は亡骸内部フラグ達の集合です。亡骸内部フラグは、実縮減により消滅します〈削除されます〉。

リカップリング対合によりカップリングされた2本の亡骸境界フラグは、仮想縮減により消滅します〈削除されます〉。

消滅する内部フラグ／境界フラグと頂点とのあいだの関係は、次の可換図式で記述されます。

亡骸フラグ・境界公式〈dead flag boundary formula〉：

$`\quad \xymatrix{
\mrm{Dead}F(\phi) \ar[r]^{\iota_\phi} \ar[d]_{\beta_A}
&{\mrm{Dead}F(\phi) } \ar[d]^{\beta_A}
\\
V(A) \ar[d]_{\phi_V}
&V(A) \ar[d]^{\phi_V}
\\
V(B) \ar@{=}[r]
&V(B)
}\\
\quad \text{commutatiev }\In \mbf{FinSet}
`$

$`\phi`$ の生存フラグ達が、余域〈ターゲット〉である $`B`$ にどのように移されるか？ は以下の2つの条件〈可換図式〉で規定されます。

生存内部フラグ・対合公式〈living internal flag involution formula〉：

（[追記]間違いがあったので図式を修正しました。[/追記]）

$`\quad \xymatrix{
\mrm{Liv}IF(\phi) \ar[r]^{\iota_A} \ar[d]_{\phi_F}
&{\mrm{Liv}IF(\phi)} \ar[d]^{\phi_F}
\\
F(B) \ar[r]_{\iota_B}
&F(B)
}\\
\quad \text{commutatiev }\In \mbf{FinSet}
`$

ここで、$`\mrm{Liv}IF(\phi)`$ は、$`\phi`$ の生存フラグであり、かつ内部フラグであるフラグ達の集合です。この公式〈可換図式〉は、内部辺が $`\phi_F`$ で保存されることを主張しています。

[追記]
最初、生存フラグ・対合公式（「生存内部フラグ」ではなかった）は次のようになってました。

$`\quad \xymatrix{
\mrm{Liv}F(\phi) \ar[r]^{\iota_A} \ar[d]_{\phi_F}^{\cong}
&{\mrm{Liv}F(\phi)} \ar[d]^{\phi_F}_{\cong}
\\
F(B) \ar[r]_{\iota_B}
&F(B)
}\\
\quad \text{commutatiev }\In \mbf{FinSet}
`$

これは内部辺も境界辺も保存します。しかし実際は、境界辺の保存は保証されません。
[/追記]

生存フラグ・境界公式〈living flag boundary formula〉：

$`\quad \xymatrix{
\mrm{Liv}F(\phi) \ar[r]^{\beta_A} \ar[d]_{\phi_F}^{\cong}
&V(A) \ar[d]^{\phi_V}
\\
F(B) \ar[r]_{\beta_B}
&V(B)
}\\
\quad \text{commutatiev }\In \mbf{FinSet}
`$

上記2つの公式〈可換図式〉は、半グラフの同型射と似ています。しかし、境界辺が保存されるとは限りません。域〈ソース〉側の生存境界フラグから余域〈ターゲット〉側の内部辺が生じるかもしれません。また、頂点パート $`\phi_V`$ が可逆〈同型〉であるとは言ってません。つまり、$`B`$ の頂点は、$`A`$ の頂点を非自明に同一視した結果かも知れません。

追記： バーガー／カウフマン論文との対応

以下のバーガー／カウフマンの論文では、ボリソフ／マニン半グラフと半グラフ変形の圏を扱っています。

  • [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

11ページの冒頭に半グラフ変形の公理が3箇条にまとめてあります。これと、前節の可換図式との対応を書いておきます。

バーガー／カウフマン この記事
(1) の前半 生存フラグ・境界公式
(1) の後半 亡骸フラグ・境界公式
(2) 亡骸内部フラグ・対合公式
(3) 生存内部フラグ・対合公式

おわりに

半グラフの定義も半グラフ変形の定義も、図式／可換図式で表現可能です。ということは、半グラフと半グラフ変形の圏は、等式的な公理系で記述できるということです。この記事では、そのような等式的公理系を淡々と記述しました。

しかし、等式的公理系は、図形的・組み合わせ的な直感に訴えないので、言い換えが必要です。半グラフ変形を記述する指令半グラフ〈instruction semi-graph〉やDead-Or-Alive構造は、半グラフ変形をより図形的・組み合わせ的に言い換えたものです。これらの図形的・組み合わせ的なツールについては以下の過去記事に書いています。

半グラフと半グラフ変形の圏は、スケマティック（「スケマティック」参照）なアプローチの基盤です。等式的公理系と図形的・組み合わせ的なツールの両方を使って調べるべき対象物です。

*1:男女のカップリングは「カプ」と省略するようです。