ベッチ数を指定した連結2部グラフの総数とその応用

概要

九州大学学術情報リポジトリ
Kyushu University Institutional Repository

Total number of connected bipartite graphs with
given Betti numbers and their applications
蓮井, 太朗

https://hdl.handle.net/2324/6787425
出版情報：Kyushu University, 2022, 博士（数理学）, 課程博士
バージョン：
権利関係：

（様式３）

氏

名

：蓮井 太朗

論 文 名

：Total number of connected bipartite graphs with given Betti numbers
and their applications
（ベッチ数を指定した連結 2 部グラフの総数とその応用）

区

：甲

分

論

文

内

容

の

要

旨

Erdős–Rényi ランダムグラフ過程において，Betti 数が特定の値に変化する連結成分が出現する
回数の期待値およびその漸近挙動は計算されている．これらの導出には，辺と頂点を指定した場合
の連結グラフの総数およびその漸近挙動が必要である．一方，Erdős–Rényi ランダム 2 部グラフ過
程においては，同じような期待値やその漸近挙動は計算されていない．2 部連結グラフの総数およ
びその漸近挙動が知られていないからである．
そこで本論文では 2 部の Erdős–Rényi ランダムグラフ過程の連結グラフの総数の期待値問題を
解くため，辺と頂点の数を指定し，Betti 数を与えた場合の連結 2 部グラフの総数を数え上げる．
以下，頂点集合𝑉𝑉 = (𝑉𝑉1 , 𝑉𝑉2 )，辺集合𝐸𝐸とする単純な 2 部グラフを𝐵𝐵𝐵𝐵(𝑉𝑉1 , 𝑉𝑉2 , 𝐸𝐸)とする．また|𝑉𝑉1 | =

𝑟𝑟, |𝑉𝑉2 | = 𝑠𝑠, |𝐸𝐸| = 𝑟𝑟 + 𝑠𝑠 − 1 + 𝑘𝑘となるような連結な 2 部グラフの総数を記号𝑓𝑓(𝑟𝑟, 𝑠𝑠, 𝑟𝑟 + 𝑠𝑠 − 1 + 𝑘𝑘)で表す
とする．このとき𝐹𝐹𝑘𝑘 に関する 1 階の線型偏微分方程式，

𝑘𝑘+1

�𝐷𝐷𝑥𝑥 + 𝐷𝐷𝑦𝑦 + 𝑘𝑘�𝐹𝐹𝑘𝑘+1 = �𝐷𝐷𝑥𝑥 𝐷𝐷𝑦𝑦 − 𝐷𝐷𝑥𝑥 − 𝐷𝐷𝑦𝑦 + 1 − 𝑘𝑘�𝐹𝐹𝑘𝑘 + � 𝐷𝐷𝑥𝑥 𝐹𝐹𝑙𝑙 ⋅ 𝐷𝐷𝑦𝑦 𝐹𝐹𝑘𝑘+1−𝑙𝑙
𝑙𝑙=0

を得ることができる．ただし，𝐷𝐷𝑥𝑥 , 𝐷𝐷𝑦𝑦 はそれぞれ𝑥𝑥, 𝑦𝑦の Euler 微分演算子である．

本論文ではこうして得た 1 階線形偏微分方程式を帰納的に解き，指数型母関数の明示的な形を求

め，その係数の漸近的挙動まで計算した．なお𝑟𝑟 + 𝑠𝑠 = 𝑛𝑛, 𝑘𝑘 = 1,2の場合を主に論じている．このとき
0 以上の整数𝑘𝑘は Betti 数に相当し，𝑓𝑓の指数型母関数𝐹𝐹𝑘𝑘 (𝑥𝑥, 𝑦𝑦)において，𝑘𝑘 = 1のとき，
1
𝐹𝐹1 (𝑥𝑥, 𝑦𝑦) = − �log�1 − 𝑇𝑇𝑥𝑥 𝑇𝑇𝑦𝑦 � + 𝑇𝑇𝑥𝑥 𝑇𝑇𝑦𝑦 �
2

となることを示した．ただし，𝑇𝑇𝑥𝑥 は𝑇𝑇 ≔ 𝐹𝐹0の𝑥𝑥での Euler 微分，𝑇𝑇𝑦𝑦 は𝑇𝑇 ≔ 𝐹𝐹0の𝑦𝑦での Euler 微分であ

る．ここで，⟨𝑥𝑥 𝑛𝑛 ⟩𝐹𝐹1 (𝑥𝑥, 𝑥𝑥)は𝑛𝑛個の頂点を持つ Betti 数 1 の連結な 2 部グラフの総数を表す．この漸近

挙動を以下のように示した．

⟨𝑥𝑥 𝑛𝑛 ⟩𝐹𝐹1 (𝑥𝑥, 𝑥𝑥) = 𝑛𝑛𝑛𝑛−1

�

2≤𝑘𝑘≤𝑛𝑛/2

π
𝑛𝑛!
∼ � 𝑛𝑛𝑛𝑛−1/2
2𝑘𝑘
(𝑛𝑛 − 2𝑘𝑘)! 𝑛𝑛
8

�𝑛𝑛 → ∞�

同じく𝑘𝑘 = 2の場合，指数型母関数𝐹𝐹2 (𝑥𝑥, 𝑦𝑦)について，𝑊𝑊 ≔ 𝑇𝑇𝑥𝑥 𝑇𝑇𝑦𝑦 , 𝑍𝑍 ≔ 𝑇𝑇𝑥𝑥 + 𝑇𝑇𝑦𝑦 とすると，
𝐹𝐹2 (𝑥𝑥, 𝑦𝑦) = 𝐹𝐹2 (𝑍𝑍, 𝑊𝑊) =

𝑊𝑊 2
{(2 + 3𝑊𝑊)𝑍𝑍 + 2𝑊𝑊(6 − 𝑊𝑊)}
24(1 − 𝑊𝑊)3

となることを示し，さらに𝑛𝑛個の頂点を持つ Betti 数 2 の連結な 2 部グラフの総数⟨𝑥𝑥 𝑛𝑛 ⟩𝐹𝐹2 (𝑥𝑥, 𝑥𝑥)の漸

近挙動を，

⟨𝑥𝑥 𝑛𝑛 ⟩𝐹𝐹2 (𝑥𝑥, 𝑥𝑥) ∼

5 𝑛𝑛+1
𝑛𝑛
48

�𝑛𝑛 → ∞�

と示した．先行研究によって𝑇𝑇 = 𝐹𝐹0 は知られている．よって𝑘𝑘 ≥ 2のとき，𝐹𝐹𝑘𝑘 = 𝑓𝑓𝑘𝑘 (𝑍𝑍, 𝑊𝑊)と書くとす
ると，帰納的な計算でこの𝑓𝑓𝑘𝑘 は，

𝑘𝑘−1

𝑤𝑤 2
� 𝑞𝑞𝑘𝑘,𝑗𝑗 (𝑤𝑤)𝑧𝑧 𝑗𝑗
𝑓𝑓𝑘𝑘 (𝑧𝑧, 𝑤𝑤) =
(1 − 𝑤𝑤)3(𝑘𝑘−1)
𝑗𝑗=0

となる予想を得た．𝑞𝑞𝑘𝑘,𝑗𝑗 は𝑤𝑤の多項式である．さらにその漸近挙動は，
⟨𝑥𝑥 𝑛𝑛 ⟩𝐹𝐹𝑘𝑘 (𝑥𝑥, 𝑥𝑥) ∼

1

2𝑘𝑘−1

ρ𝑘𝑘−1 𝑛𝑛𝑛𝑛+(3(𝑘𝑘−1)−1)/2

�𝑛𝑛 → ∞�

となる予想を立てた．なお，ρ𝑘𝑘 は既知の定数である．

また，連結な単純 2 部グラフに対応する基本グラフを導入し，ラベル付き 2 部根付き木の本数に

対する有理関数の基本グラフ上での和として，𝐹𝐹𝑘𝑘 の別の表現を与えた．基本グラフとは，連結で単

純な 2 部グラフにおいて「葉および葉に隣接する辺を削除する」という操作を葉がなくなるまで繰
り返し，次数 2 以下のサイクル構造を構成する頂点およびその頂点に隣接する辺を潰して得られる

グラフである．基本グラフは元となった 2 部グラフのサイクルに関する情報を全て保存する．さて，
このとき𝐹𝐹𝑘𝑘 は以下のように表示できる．

𝐹𝐹𝑘𝑘 (𝑥𝑥, 𝑦𝑦) = � 𝐽𝐽ℬ (𝑥𝑥, 𝑦𝑦)
ℬ∈𝐵𝐵𝐺𝐺𝑘𝑘

ただし，
𝐽𝐽ℬ (𝑥𝑥, 𝑦𝑦) =

𝑟𝑟 +𝑎𝑎1 +2𝑎𝑎2 +𝑏𝑏2 +𝑐𝑐2

𝑇𝑇𝑥𝑥 sp

𝑔𝑔ℬ �1 − 𝑇𝑇𝑥𝑥 𝑇𝑇𝑦𝑦 �

𝑠𝑠 +2𝑎𝑎1 +𝑎𝑎2 +𝑏𝑏1 +𝑐𝑐2

𝑇𝑇𝑦𝑦 sp

𝑎𝑎1 +𝑎𝑎2 +𝑏𝑏1 +𝑏𝑏2 +𝑐𝑐1 +𝑐𝑐2

である．𝐵𝐵𝐺𝐺𝑘𝑘 は基本グラフ全体の集合，𝑔𝑔ℬ , 𝑟𝑟sp , 𝑠𝑠sp , 𝑎𝑎𝑖𝑖 , 𝑏𝑏𝑗𝑗 , 𝑐𝑐𝑘𝑘 (𝑖𝑖, 𝑗𝑗, 𝑘𝑘 = 1,2)は基本グラフℬに関する情報で
ある．

論文の最後では，データ探索アルゴリズム論およびランダムグラフ理論への主結果の応用を記述

した．データ探索アルゴリズム論での応用については，2004 年に導入された Cuckoo hashing との
関連を述べている．Cuckoo hashing が最適な形で動作するには，2 つのハッシュ表において，キー
の挿入が無限ループしてはならない．ハッシュ表における各キーの挿入位置を頂点，キーの移動経
路を辺と見なすと，キーの移動がユニサイクル構造を持つ連結な単純 2 部グラフの形になる場合に
無限ループが発生する．これは本論文主結果の𝑘𝑘 = 1の場合に該当する．

ランダムグラフ理論での応用については，Erdős–Rényi ランダム 2 部グラフ過程において，特定

の Betti 数を持つ連結成分の内部に辺を加えて完成するような連結成分の出現回数の期待値を考え
る際，本論文における𝐹𝐹𝑘𝑘 の漸近挙動が必要になる．また，1 個の連結成分のみに注目するのではな

く，与えられた Betti 数を持つ 2 つの連結成分の間に辺を 1 本加え，Betti 数を 1 増加させたより
大きな連結成分が出現するような回数の期待値を求める際にも，𝐹𝐹𝑘𝑘 の漸近挙動が必要になる．