5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)

Presentation on theme: "5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)"— Presentation transcript:

1 5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)
D3 杉原堅也

2 内容 線形樹化数（linear arboricity） 連結成分が全てパスの森を線形森（linear forest）という．
　 グラフGの線形樹化数 la(G) とは，Gの全ての辺をカバーするような線形森の最小数．

3 予想 5.5.1 予想 5.5.1(線形樹化数予想) [Akiyama, Exco, Harary. ’80]
全ての d-正則グラフの線形樹化数は 　d-正則グラフの辺の数は nd/2, 線形森は最大 n－1 本の辺をもつから， 最大次数Δのグラフ G はΔ-正則グラフの部分グラフなので，この予想は 　 la(G) ≦ 　　　　　　　 と同値．

4 定理 5.5.7 定理 5.5.7 定数 c > 0 が存在し，全ての d-正則無向グラフ G が を満たす． （Δが偶数）
確率的な手法を使わない結果は， （Δが偶数） （Δが奇数） 最も良い結果は，1988年の Alon の結果 この節で示すのは下の結果． 定理 5.5.7 　定数 c > 0 が存在し，全ての d-正則無向グラフ G が 　　　　　　　　　　　　　　　　　　　を満たす．

5 予想 5.5.2 予想 5.5.2 (有向グラフ) [Nakayama, Peroche. ’87]
全ての d-正則有向グラフ D の線形樹化数は d-正則有向グラフ ： 各節点の indegree と outdegree が両方とも d． ：有向グラフ G の線形樹化数 (⇔ G の枝を全てカバーする線形有向森の最小数) 森の連結成分が有向パス．

6 無向と有向の関係 2d-正則無向グラフの辺をオイラー閉路に沿って向き付ければ，d-正則有向グラフになる．
d-正則有向グラフに対する予想 （または，dla の上界） 　 ⇒ 2d-正則無向グラフに対する予想（または，la の上界） 4-正則 2-正則 全ての(2d-1)-正則無向グラフは，ある2d-正則無向グラフの部分グラフなので， 対応する d-正則有向グラフが存在する．

7 定理 5.5.6 定理 5.5.6 定理 5.5.7（再褐） 定数 c > 0 が存在し，全ての d-正則有向グラフ G が
　　　　　　　　　　　　　　　　　　　を満たす． 定理 5.5.7（再褐） 　定数 c > 0 が存在し，全ての d-正則無向グラフ G が 　　　　　　　　　　　　　　　　　　　を満たす．

8 命題 5.5.3 命題 5.5.3 H = (V, E) を最大次数 d の無向グラフ， を分割（Vi は互いに共通部分を持たない），
　各Vi は|Vi|≧2ed を満たすとすると， 　各Vi の節点を含む独立集合 W⊆Vが存在する． 証明 全ての Vi で　　　　　　 　　　 　　となることを示せば十分． Vi から節点を一つずつランダムに選んで W とし，W が独立集合となる確率が正となることを示す．

9 命題 5.5.3の証明 辺 f に対し，Af を W が f の端点を両方含む事象とする．明らかに，Pr(Af) ≦ 1/g2
Af は，両端点が Vi∪Vj に含まれない辺 f’ に対する事象 Af’ と独立． 独立とならない事象は 2gd－1 個以下． 　 → Corollary 5.1.2 (Local Lemma; Symmetric Case) Vi Vj f H

10 命題 5.5.3の証明 Corollary 5.1.2 A1, A2, ..., An を事象とする．
　 各 Ai が他の高々 d 個以外の事象と独立で， Pr(Ai) ≦ p (1 ≦ i ≦ n)の時， ep(d+1) ≦ 1 ならば 上の p, d に前スライドで得られたものを代入すると， 従って，全てのAf が起こらない確率（W が独立）は正．

11 定理 5.5.4 定理 5.5.4 G = (U, F ) が d-正則有向グラフで，有向内周 g が g ≧ 8ed を満たすとすると，
(有向)内周： 最小な(有向)閉路の長さ |F| = d|U| ，有向線形木は高々|U|－1 本の辺をもつので， を示す．

12 定理 5.5.4の証明 辺集合 F は d 個の disjoint な 1-正則の全域部分グラフに分割することができる．
1-正則な全域部分グラフ： 連結成分が有向閉路． 2-正則

13 定理 5.5.4の証明 辺集合 F は d 個の disjoint な 1-正則の全域部分グラフに分割することができる．
1-正則な全域部分グラフ： 連結成分が有向閉路． 2-正則 それぞれの閉路から一つずつうまく辺を選び，線形森を作れば d+1 個の線形木で 分割できることを示せる． 実際には，マッチングとなるように辺を選べる．

14 定理 5.5.4の証明 G=(U, F)の線グラフ (節点集合がFで，Gで同じ節点を共有していた f, f’ ∈ F の間に辺があるグラフ)をつくる． Gのマッチング ⇔ 線グラフの独立集合 2-正則 線グラフ

15 定理 5.5.4の証明 命題 5.5.3（再褐） H = (V, W ) を最大次数 D のグラフ， を分割（互いに共通部分を持たない），
　　　　　　　　　　　　　　 を分割（互いに共通部分を持たない）， 　各Vi は|Vi|≧2eD を満たすとすると， 　各Vi の節点を含む独立集合 W⊆Vが存在する． 線グラフに命題5.5.3を適用する． 　　Vi を最初の分割の閉路に対応した節点集合とすると， 　 |Vi| は上の条件を満たす． 　　線グラフの次数 D は 4d－2, |Vi|は G の内周 g ≧ 8ed ≧ 2e(4d－2). それぞれの閉路 （ に対応した線グラフの節点集合 ）から 　　一つずつ独立集合になるように節点を選べる，元のグラフではマッチング．　　

16 定理 5.5.4の証明 2-正則 線グラフ

17 定理 5.5.4の証明 d+1個の線形森に分割可能 つまり， 2-正則 線グラフ

18 補題 5.5.5 v 補題 5.5.5 G = (V, W ) を d-正則有向グラフとし，d は十分大きいとし．
　p を　　　　　　　　　　　 を満たす整数とすると， 　下の条件を満たす節点の p-着色(0, 1, ..., p－1)が存在する． 　が 　を満たす． 1 v 1 3 (5.8) 2 1

19 補題 5.5.5の証明 v 節点に対し，ランダムに 0,..., p－1 を着色．
v, i に対して，　　　を　　　　　　 が不等式(5.8)を満たさないという事象とする． 　　　　 も同様． 　 すると， 1 v 1 3 2 1 ∵ 　　　　　は2項分布 (期待値 d/p, 分散 　　 ) ． あとは，独立でない事象の数を見積もって Local Lemma． 全ての v, i で　　　　　　 が起こらない（式5.8を満たす）確率が正であることを示す．

20 補題 5.5.5の証明 v と独立でない は，v と隣接点を共有するような v’ に対するもの．
d-正則なので，このような v’ は高々 (2d)2 個． 色は p 個あるので， と独立でない事象は高々 (2d)2 p個． 従って次を満たす． 　　（d は十分大きく，仮定より　　　　　　 ） 　　Corollary から， 　　全ての v, i で　　　　　　 が起こらない（式5.8を満たす）確率は正となる． v 2d個 ・・・ 2d個

21 定理 5.5.6の証明 定理 （再褐） 　定数 c > 0 が存在し，全ての d-正則有向グラフ G が 　　　　　　　　　　　　　　　　　　　を満たす．

22 定理 5.5.6の証明 グラフ G を補題5.5.5を利用して p 個の部分グラフ
　　　G0,...,Gp－1に分割．(G1,...,Gp－1は内周が大きく定理5.5.4が使える) 　 　 （p は　　　　　　　　　　　 を満たす素数） G の線形樹化数は， G0,...,Gp－1の線形樹化数の上界の和でおさえられる．

23 定理 5.5.6の証明 G0,...,Gp－1 の作り方 G の節点を f : V → {0,...p-1} で彩色．
　　 補題 から，不等式 (5.8) を満たす着色が存在． Gi =(V, Ei) の辺集合 Ei を以下のようにする． 2 9 2 2 13 5 閉路の長さは p の倍数 同じ色の 節点を結ぶ … … ∵ 長さを L とすると， 2 1 2 2 p-3 p-7 を満たす，かつ， i < p で，p は素数だから． E0 E4

24 定理 5.5.6の証明 Δi は Gi の最大次数 G0 は， trivial な上界 　 定理 の証明の最初の議論で Δ0 個の 1-正則全域部分グラフに分割して，各々をさらに２つに分割． Gi (1≦ i ≦p-1) は，内周≧ p ≧10√d ＞8eΔi なので， 　 定理 から

25 定理 5.5.6の証明 Δi は Gi の最大次数 G0 は， trivial な上界 　 定理 の証明の最初の議論で Δ0 個の 1-正則全域部分グラフに分割して，各々をさらに２つに分割． Gi (1≦ i ≦p-1) は，内周≧ p ≧10√d ＞8eΔi なので， 　 定理 から 1 最大次数は補題 の N±(v, i) の不等式(5.8)による． N±(v, i) は節点 v に隣接する色 i が塗られた節点の数． つまり， N±(v, i) で v の indegree /outdegree を押さえられる． 1 v 3 1 3 (5.8)

26 定理 5.5.6の証明 ∴

27 定理 5.5.6 定理 （再褐） 　定数 c > 0 が存在し，全ての d-正則有向グラフ G が 　　　　　　　　　　　　　　　　　　　を満たす．

28 定理 5.5.7 定理 5.5.7 （再褐） 定数 c > 0 が存在し，全ての d-正則無向グラフ G が を満たす．
　　　　　　　　　　　　　　　　　　　を満たす． 前述したように， d-正則無向グラフ G に対応する d/2-正則有向グラフを考えれば定理5.5.6 から自明． d が奇数のときは，(d+1)/2-正則有向グラフを考えれば同様に定理 がいえる．