『経済研究』（明治学院大学）第 164 号

2022 年

特定の次数列を満たすランダムグラフの大きさについてⅢ

浜口幸弘

1．はじめに
本稿は以前の論文（浜口（2020，2021））の続きに相当するものである．本稿では，特定の次数列，すなわち次数 1 と次数 k の頂点から構成されるランダムグラフに対して，孤立木の存在可能性に関する定理 1，k―正則部分グラフの存在可能性について評価した定理 2，およびグラフの直径を評価する定理
3 を導出した．

2．概念と用語の定義
まず最初に，本稿に関係する概念と用語の定義を概括する．おおむね，浜口（2020，2021）における定義と概念の記号化を踏襲するので，ここでは，必要最小限の定義と概念を述べるものとする．
まず浜口（2021）と同様，頂点数 n のランダムなグラフ G が，d（1 n）個の次数 1 の頂点および d（k n）個の次数 k の頂点から構成される場合について考察を行う．以下では，この条件を満たす単純グラフを18GD として，簡単のために n1＝d（1 n）および nk＝d（k n）と記す．また次数 k は，4 ≤ k ≤ n を満たす nの関数とする．そして，2m をコンフィギュレーションにおける頂点の総コピー数（次数の総和）とし，基準値 α を以下のように定義する．
n－1d（n）

d（（k k－2）d（1 n）k n）
として， lim α は， 0 ＜ lim α ＜ 1/2を満たすよ
nn→∞
n→∞

（i i－2） i ＝－＋Σnni

α＝＝1うに収束する（なお以下では，十分大きな n を前提にするので，0 ＜ α ＜ 1/2 と考える）．このとき，n1＋nk＝n かつ 2m＝n1＋knk なので，以下を得る．
n1＝（k k－2）－αα＋1k＋αn，nk＝n，2m＝n．
（k－1）2
k－1（k－1）229『経済研究』（明治学院大学）第 164 号

また，n ＜ 2m ≤3nである．
2以下では，一定の条件下（本稿で対象にするグラフは，この条件を満たす．浜口（2020）参照）において，単純グラフの性質は多重グラフの性質から導ける事実（例えば，浜口（2020）参照）を利用する．

3．次数 1 と次数 k の頂点からなるランダムグラフの性質
まず，GD に含まれる孤立木の存在に関する定理を提示する．そのために補題 1 を与えるが，これは，浜口（2021）で示した補題の条件部分の誤りを修正したものである．なお，補題をこのように修正しても，浜口（2021）における定理の証明には何ら影響を及ぼさない．
補題 10 ＜ ε ＜ 1 とし，σ＝σ（n）＞ 0 は，σ →∞とする．そして整数 a は，σ ≤ a ≤のとき，十分大きな n に対して，以下の不等式が成り立つ．

εmを満たすとする．こkexp
1＋O（ ＋ ） ．
（2m－1）（2m－3）…（2m－2a＋1） （ 2m ）2m（ma ）
11

≤

aa2a1

証明

y＝－log（1－x）（x ＜ 1）のグラフは単調に増加するので，以下の不等式が成り立つ．
log（ 1－（Σ）m ≤∫ m2m ）t－a2t－11（2a＋1）/2m（－log（1－x））dx．

1/2＝1

ここで，| x | ＜ 1 に対して，以下の式が成り立つ．

∫（－log（1－x））dx＝（1－x）log（1－x）＋x∞xn＋x
n＝1 n（Σ ）＝（1－x）－
x2x3x4＝ 2 ＋ 6 ＋ 12 ＋… ．
この式を利用すれば，∫ m（2a＋1）/2m1/2＝（－log（1－x））dx＋＋…－（ 2（ 2m ）＋ 6（ 2m ）＋…）．
2（ 2m ） 6（ 2m ）12a＋1212a＋1111aa211＋O＋2mma））．

312すなわち，以下を得る．
aΣ（t－＝1log 1－2t－12m）≤

ところで，以下の式が成り立つ．

30（（3特定の次数列を満たすランダムグラフの大きさについてⅢ（ 1－ 2m （） 1－ 2m ）…（ 1－ 2m ））（2m－1）（2m－3）…（2m－2a＋1） （ 2m ）（1＝1a1a1a1（ 2m ）elog（（＝1－a－t＝112m（ 2m ）e（ Σlog（＝2a－13－1（）1－ 2m ）…（ 1－ 2－m ））2a32t－12m1－1－1））．

したがって，前述の式を用いて以下を得る．

exp
1＋O（ ＋ ） ．
（2m－1）（2m－3）…（2m－2a＋1） （ 2m ）2m（ma ）
11

≤a1aa2□
そこで，次数 1 の頂点 i 個と次数 k の頂点 j 個からなる孤立木（isolated trees）を T（i, j）と記し，

GD における T（i, j）の存在可能性に関する定理を導く．なお，以下の定理 1 では近似計算を簡単にするために，k の範囲に関して，σ →∞となるような σ＝σ（n）＞ 0 に対して，σ ≤ k ≤ n1/8とする．
定理 1（n）（ⅰ）σ＝σ＞ 0 は，σ →∞とし，σ ≤ k ≤ n1/8とする．このとき，0 ＜ ε ＜ 1 に対して，j が/（2 log（11＋＋εα）e ）を満たすとき，ほとんどすべての G は T（i, j）を含む．
α3≤ j ≤ log nlog（1＋ε）

3D（ⅱ）σ＝σ（n）＞ 0 は，σ →∞ とし， σ ≤ k ≤ n1/8 とする．このとき，0 ＜ ε ＜ 1－1＋α/eαに対して，j が（1－ε）eαn2 log n log≤ j ≤ 3 を満たすとき，ほとんどすべての GD は，このような T（i, j）をすべて1＋αk含まない．
証明（ⅰ）確率変数 X（ j）をコンフィギュレーションに含まれる T（i, j）の個数とする．このとき，浜口（2021）
における定理から，以下の式が成り立つ．
j（k－1）k（j）！

（ i （） jk ）（2m－1）（2m－3）…（2m－2（k－1）j－1）．

E（X（ j））＝n1n（k－1）j＋1 本であることに注意する．さて，こなお，i＝（k－2）j＋2 であり，辺の総数は i＋j－1＝の式を近似評価すると，以下を得る．

E（X（ j））＝（1 （k－1）j＋1（kj）2
n1i nk j jk（（k－1）j）！
1＋Oi！ j！
n2m（）（））．

）X（ j） 1）
ここで，確率変数 X（ j）の順序付けられた 2 個の組を（X（ j））2＝X（ j（－ と記すと，以下を得る．

E（（X（ j））2）
n1－i

n －j

（ （） jk ）（ i ）（ k j ）n＝ i1n31/（2≤ j ≤ log nlog（1＋ε）

『経済研究』（明治学院大学）第 164 号
j（k－1）
2（k（j）！）

×（2m－1）…（2m－2（k－1）j－1）（2m－2（k－1）j－3）…（2m－4（k－1）j－3）（（ n ））．

＝（E（X（ j）））2 1＋O（kj）2

また，0 ＜ ε ＜ 1 として，以下を得る．ただし，n ! の大きさの評価として，以下の不等式を用いる．

（ e ） ≤ n！≤ en（ e ）．
n ne
E（X（ j））＝（ni eii nk jej）

1

en1 i en1

（ 2m ）（k－1）j （k－1）j1

je（2m（（k－1）je（ n ））

1＋O（kj）2（ n ））1＋O（kj）2

α＋1（k－1）j （k－1）j（ j （k－1） n）k（j（k－1）j－j＋22k－1））（k－1）j） （ 2m ）（k k－2）－αej2）e（ ＋O（ n ））（k－1）j（kj）21）（（ ））11 en（（k k－2）－α）j （k－1）j （k α＋1）（（k－2）j＋2） j
1－Ok（（ij （kj）2 （（k－2）j＋2）（k＋α）
k k－2）－α）j1（） （（（）/（1＋ k ＋ （k k－2）j ））（）/（1－ （k k－2）））（ 1－O（ k ））（k－2）j ）enα1－2ij （kj）
（k k－2）（（2（k＋α） （k－1）jα2× （1＋α）1＋≥）e1n）
2meij（（k－2）j＋2 （k－1）（（k＋α）n ）≥kj（ j k）k（j2meij（ i ）×≥j（（k－1）j （k－1）j e（ ） ej（ ） （≥（1 （k－1）j＋1（kj）2
n1i nk j jk（（k－1）j）！
1＋Oi！ j！
n2m

≥ ei1
≥n nα）（1j（ ））

j
en
1＋α
1
1－O
2αlog
（1ε）
+kij （kj） e e

1（（ e（1）（ 1－O（ k ））α ＋ε）
1＋αenkj≥ 34（1j（1＋ε）eα 4 n /→∞．
1＋α（log n）4≥ 2 log

1 8）

最後から 3 番目および最後の不等式は，3/（2 log（11＋＋εα）e ）による．

≤ j ≤ log nlog（1＋ε）α

さて，これらの結果を用いて Chebyshev の不等式を適用すると，以下となる．
）X（ j） 1）
E（（X（ j））2）
E（X（ j（－ ）＋E（X（ j））
1－1
2－ ＝（j）（X ））（X（ j）））2（E（EP（X（ j））＝0）≤32特定の次数列を満たすランダムグラフの大きさについてⅢ＝）X（ j） 1）
E（X（ j（1－ ）－1＋ （ j） → 0 ．
（（X j）））2
E（X ）（Eしたがって主張は示された．

□（ⅱ）まず （ （ j））の上限を，補題 1，上記（ⅰ）に示す

n ! の評価式，および以下の不等式を用いてE X評価する．

en r（ r ）≤（ r ）．
nそして，0 ＜ ε ＜ 1－1＋αeαに対して，以下を得る．
j（k－1）k（j）！

（ i （） jk ）（2m－1）（2m－3）…（2m－2（k－1）j－1）

E（X（ j））＝n1n

en1 i enjen1 i enj（k－1）j （k－1）j（ i ）（ j k）k j（e k－1）（j≤（k－1）j （k－1）j（ i ）（ j k）k（j≤ee1（k－1）j＋1（k－1）j（e k－1）j） （ 2m ）1） （ 2m ）2m（（k－1）j＋1）2（1＋o（1））2m（exp）（kj）2（m ）exp（ kj （）（1－ （k k－2））/（1＋ k ＋ （k k－2）j ））n≤O（（αα（ （k－2）j ））/（×（1＋α）1＋n1＋α2

1－2（k＋α） （k－1）j）exp（ m ）（k k－2））jα（kj）2．
（ kj （） e（1α －ε））

≤Ok2jjn（ m ）において， k j ≤ k が成り立つことによる．したがって， j ＝2 log n/log 1－＋α

最後の不等式は， exp2（11（1－ε）eα（1－ε）eα（注：＞ 1）とすると，Markov の不等式から以下となる．
1＋α1＋αj1＝2 log n/log

P（（X（ j1）≥ 1）∪…∪（（X（ n/k3）≥ 1））≤

≤
≤

n/k3

P（X j ≥ 1）
Σj j（ ）

＝1n/k3E（X j ）
Σj j（ ）

＝1n/k3n1＋αjn1＋αj1O（ （Σα －ε））kj ） e（1j j＝1n（ kj ）k（ e（1α －ε））

≤O

311（1－ε）eα（ 2k log n log 1＋α ）→ 0 ．

≤O4

よって，P（（X（ j1）＝0）∩…∩（X（ n/k3）＝0））→ 1 であり，主張は示された．
33

□ε）eα

『経済研究』（明治学院大学）第 164 号

定理 1 によれば，GD は大きさ klog n のオーダーの孤立木を少なくとも 1 つ含むことになる．これは，Molloy, M and Reed, B（1995 1998）では指摘されていない事実である．
次に，ランダムグラフにおいて，すべての頂点の次数が k である連結成分，すなわち，k―正則（kregular）部分グラフの存在可能性について評価する．
定理 2log n ≤ k ≤ n1/8とし，j は k＋1 ≤ j ≤ nk を満たすとする．また，kj は偶数とする．このとき，ほとん
どすべての GD は，このような頂点数 j 個の k―正則部分グラフをすべて含まない．
証明
確率変数 X（ j）をコンフィギュレーションに含まれる頂点数 j 個の k―正則部分グラフの個数とする．
頂点数 j 個の k―正則部分グラフは孤立した連結成分となるので，コンフィギュレーションにおいて，（kj－1）（kj－3）…1である．また，最小頂点数の k―正則部分それが存在する確率は高々（2m－1）（2m－3）…（2m－kj＋1）
グラフは（k＋1）―完全部分グラフであることに注意する．よって，以下の不等式が成り立つ．なお，以下では，補題 1 および定理 1 の証明に用いた不等式を利用する．

P（（X（ k＋1）≥ 1）∪…∪（（X（ nk）≥ 1））≤≤≤≤≤≤≤nknk

P（X j ≥ 1）
Σj k（ ）＝ ＋1

E（X j ）
Σj k（ ）

＝ ＋1

nkn

nkn

（kj－1）（kj－3）…1kΣ
（）（2m－1）（2m－3）…（2m－kj＋1）
jj log n＝（kj）！

Σ（ jk ）（2m－1）（2m－3）…（2m－kj＋1） 2kj
j log n＝（ ）（ （nkkj（kj－2） enk j kjee
je kj－2
j＝log n

Σnk

Σ
nk

Σ

ee

（ekj

11/2Σ e （ jk ）（2（ en ） ）j log n≤Σ e （8（ en ）j log n（kj）2 2en jnk

＝kj

1/2kj

2＝（kj）2

1/2exp）

4kj k/2－1 j1（expkj2nkj
kj 1/2exp2nen≤

nk1/2kj）（（ ） （ ））j
α＋1nj （k－1）2（kj）2 e

j＝log n1） （ 2m ）1/2（ j ）（ e（ ） （ n ） （ ））（kj）2 enk j kj

j＝log n1/2－1（kj/2－1）！

→0．
34kj））kjkj（1＋o（1））8m

特定の次数列を満たすランダムグラフの大きさについてⅢ

よって，P（（X（ k＋1）＝0）∩…∩（（X（ nk）＝0））→ 1 となり，主張は示された．

□さて次に，GD 上の任意の 2 頂点間の距離の最大値，すなわち，GD の直径（diameter）の大きさを考察する．グラフの直径は，グラフの大きさに関する特徴を表す代表的な基準量の 1 つである．そして，GD の直径を diam（GD）と記す．このとき，GD の直径の大きさを評価する定理を以下のように提案する．
定理 3k は 4 ≤ k ≤ n1/8 とする．このとき，ほとんどすべての GD に対して，以下の不等式が成り立つ．

（（k log n） ）/log（α＋1）≤ diam（GD）

log

n22（ k log（nk log n））/ log（（k α＋1）/（k＋α））＋1 ．

≤ log

2m22

証明
対象にするランダムグラフにおいて，任意の固定した 2 つの頂点を u および v とし，確率変数 X（ r）を，u と v をそれぞれ端点とする長さ r のパスの個数とする．このとき，（kr）2＝ο（m）の条件の下で E（X（ r））を求めると，以下のようになる．

n －21（ rk－1 ）（r－1）！（（k k－1））r k （2m－1）（2m－3）…（2m－2r＋1）

E（X（ r））＝－1 2（ ）（1＋O（ n ））nkr－1
1（r－1）！
（（k k－1））r－1 k22m
（r－1）！

＝） 2m（（α＋1）n （k k－1） r－1 k2（（k－1）＝2m

2（kr）2r（ n ））

1＋O（kr）2（ k＋α ） 2m（1＋O（ n ））．

＝（k α＋1） r－1 k2（kr）2

まず，主張の左側の不等式から示す．浜口（2020）によれば，このランダムグラフには大きさ δn/k2（δ ＞ 0）以上の連結成分 C が存在する．そして，E を u と v がともに C に含まれる事象とし，Ar（1 ≤ r ≤ r1）を u と v は長さ r のパスで接続される事象とする．また，r は（kr）2＝ο（m）を満たすものと仮定する．このとき，以下の不等式が成り立つ．

P（A1∪…∪Ar1）≥ P（E∩（A1∪…∪Ar1））＝P（E）P（A1∪…∪Ar1 | E）．

ここで，連結成分 C は大きさ δn/k2 以上なので，次数 k の頂点は少なくとも δn/k3 個ある．よって，（ 2 ）/（ 2k）＝（ k nk ）（1－O（ n ））

P（E）≥

（＝
ただし，ε＝

δδn/k3

δnnk323）（（ ））≥（ k ） ．

δn （k－1）2 2k3
1O－nk3（α＋1）nn －2ε2（ 2 ）/（ 2k）＝（ δn/kk －2 ）/（ δn/kk ）に注意する．したがって，とする．また，2（α＋1）

δn/k3

n335n3

『経済研究』（明治学院大学）第 164 号

ε（ k ）P（A ∪…∪Ar | E）．

P（A1∪…∪Ar1）≥211

すなわち，rk2k2 1P（A…
A）
P（Ar）．
∪∪≤1r1ε2ε 2 r ＝1Σ

P（A1∪…∪Ar1 | E）≤（Ar）は，Markov の不等式および先に求めた E（X（ r））から以下のように評価できる．
ところで，PP（Ar）＝P（X（r）≥ 1）≤ E（X（r））（ k＋α ） 2m（≤

（k α＋1） r－1 k2（ n ））．

1＋O（kr）2（（k log n））/ log（α＋1）とすれば（このとき，1 ≤ r ≤ r はn

したがって，前述の式において， r1＝log

212

最初に掲げた前提条件（kr）2＝ο（m）を満たすことに注意），

P（A1∪…∪Ar1 | E）≤≤≤

Σ（ k＋α ） 2m（rk2 1
ε 2 r ＝1

（k α＋1） r－1 k2

2k4（k α＋1） r1－1

（ n ））

1＋O（kr）2

ε n （ k＋α ）
22k4

ε2nr1

r1
r（1 α＋1）/n（（ε log n）2 log（α＋1））（k log n）2≤ 2 log21（ log n ）→ 0 ．

＝O

この事実は，u と v がともに連結成分 C に含まれる条件下で，この 2 つの端点間の距離は r1 より大きいことを意味する．すなわち，GD の直径は r1 より大きくなる．

（X（ r））を求め次に，主張の右側の不等式を示す．まず前述と同様に，（kr）2＝ο（m）の条件の下で Eると，以下となる．

（ ）（nkr－1
1（r－1）！
（（k k－1））r－1 k2
2m（r－1）！

E（X（ r））＝r（ n ））．

1＋O（kr）2

ここで確率変数 Y を，確率変数 X（ r）の順序付けられた t 個（t は固定した，任意の正の整数）の組として，以下のように定義する．
）X（ r） 1）
Y＝（X（ r））t＝X（ r（－ …（X（ r）－t＋1）．

そして Y を，頂点を互いに共有しない t 個のパスの組 Y1 と少なくとも 1 個の頂点が共有される t 個のパスの組 Y2 に分解する．すなわち，Y＝Y1＋Y2 である．このとき，（kr）2＝ο（m）なので，以下の式が成り立つ．

36特定の次数列を満たすランダムグラフの大きさについてⅢ

n －2

n －2－（r－1）
n －2－（t－1）（r－1）… k（（r－1）！）tr－1
r－1（ rk－1 ）（ kE（Y1）＝）（）

1t （k k－1））r－1）（k k－1）…（k－t＋1））2
×（（（（2m－1）（2m－3）…（2m－2tr＋1）（（ n ））．

＝（E（X（ r）））t 1＋O（kr）2

一方，E（Y2）の大きさを評価すると，t 個のパスの間で少なくとも 1 個の頂点が共有されるので，パス全体の頂点を選択する組み合わせの数は，頂点を互いに共有しない場合に比べて，r/nk 倍以下となる．
よって，以下を得る．

E（Y2）
rrk2
．
＝O＝O
E（Y1）
nnk

（ ） （ ）

したがって，

E（（X（ r））t）＝E（Y）＝E（Y1）＋E（Y2）（（ n ））
rk2＝E（Y1） 1＋O（ n ））（＝（E（X（ r）））t 1＋O（kr）2（（ k＋α ） m ）（＝（k α＋1） r－1 k22t（ n ））．

1＋O（kr）2（k α＋1） r－1 k2（ k＋α ） 2m とすると，Poisson の近似定理（例えば，Bollobás（2001）参照）

したがって， λr＝から，以下が成り立つ．

P（X（ r）＝i）～ e－λrλri/i！．
よって，P（X（ r）＝0）～ 1/eλr．

（ ）（knここで，コンフィギュレーション上の次数 k のすべての頂点対に対して，1，2，…， k のように任意に22m（nk2 log n） log（（k α＋1）
番号付けして，i 番目の頂点対に対する X（ r）を X（i r）と記す．そして，r＝r2＝log 2 log）/（nk2 log n） log（（k α＋1）/（k＋α））＋1 とすると，（kr2）2＝ο（m）を満たす，したがって，以下を得る．

（（）n（ 2k ）P（ Xi r ＝0 ）（ （ ） ）） Σi（r2）

P X（1 r2）＝0 ∪…∪ X nk ＝0 ≤（ ）n2

＝ 2k e－λr（1＋o（1））＝nk2
2（ 2）＝1/（ （（ k＋α ） 2m ））（1＋o（1））
2exp

37

（k α＋1） r2－1 k2）/

『経済研究』（明治学院大学）第 164 号＝（（1（1＋o（1））→ 0 ．
2 log n）

（ （ ） ））（r2）

すなわち，P X（1 r2）≥ 1 ∩…∩ X nk ≥ 1 → 1 である．これは，どの頂点対にもそれらの頂点対を結2ぶ長さ r2 のパスが存在することを意味するので，GD の直径はそれ以下となる．したがって，主張は示された．

□上で示した直径の大きさを，Bollobás and Vega（1985）によるランダムな k―正規グラフのそれと比較すると，次のようになる．すなわち，Bollobás and Vega（1985）による k―正規グラフの直径はおお（k－1）であるのに対して，上の結果による GD の直径はおおよそ log（n/（k2log n）2）/
よそ log n/loglog（α＋1）から log（n/k2）/log（α＋1）である．k が定数の場合，直径はともに log n のオーダーになるが，そうでない場合は，かなり差（後者の方が大きい）があることがわかる．

4．課題
引き続き考察を行って，次回にまとめを行う予定である．

参考文献
B. Bollobás, Random Graphs（2nd edition）（2001）.Cambridge Univ. Press.
B. Bollobás and W.F. de la Vega, “The diameter of random regular graphs”, Combinatorica, 2（1982）.
M. Molloy and B. Reed, “The Size of the Largest Component of a Random Graph on a Fixed Degree Sequence”, Combinatorics, Probability and Computing 7, 295-306（1998）.
M. Molloy and B. Reed, “A Critical Point for Random Graphs with a Given Degree Sequence”, Random Structures and Algorithms 6, 161-180（1995）.
浜口幸弘，
特定の次数列を満たすランダムグラフの大きさについて，
明治学院大学経済研究 160（2020）．
浜口幸弘，特定の次数列を満たすランダムグラフの大きさについてⅡ，明治学院大学経済研究 162（2021）．

38