ファイル置き場 Sendai Logic Homepage

(1)

theorem in Reverse mathematics

榊原拓

論文紹介 Definitions Matching Perfect Matching

Tutte’s theorem Reverse Mathematics References

Tutte’s theorem in Reverse mathematics

榊原拓

東北大学

2010/11/26

(2)

榊原拓

1 ^論文紹介

2 Definitions

3 Matching

4 Perfect Matching Tutte’s theorem Reverse Mathematics

5 References

(3)

榊原拓

論文紹介

Definitions Matching Perfect Matching

論文紹介

Title：組合せ的グラフ理論と逆数学

グラフ理論に関する逆数学の総合報告，および結果の紹介．

1 ^準備

2 ^{今までの結果のまとめ}

3 Menger’s theorem^{に関する考察}

4 Tutte’s theorem^{に関する結果}

(4)

榊原拓

論文紹介

1 ^準備

(5)

榊原拓

論文紹介

1 ^準備

(6)

榊原拓

論文紹介

1 ^準備

(7)

榊原拓

Definitions

Graph

Definition (Graph)

有向グラフ(Directed Graph)^とは頂点(vertex)^{と呼ばれるもの} の集合_V と辺_(edge)と呼ばれるものの集合_E _{⊆ V × V} からなるものの集合である．_{Edge set E}に対して

∀(v1, v2) ∈ E ((v2, v1) ∈ E )^{となるとき，}G ^{は無向グラフ} (Undirected Graph)^という．RCA0上で考えるときは頂点を自然数として考える．

(8)

榊原拓

Definitions

Branch

Graph G^{が与えられたとき，}G ^上のvertex set,edge set^をそれぞれ_V(G ), E (G )^で表す．

Definition (Finite branching)

G^上のvertex v ^に対しv^{の隣接点の個数}

|{w ∈ V | (v , w ) ∈ E }|^をv^の次数(degree)^といいdeg(v )^で表す．_Graph上の任意の_{vertex v}に対しdeg(v ) < ∞^となるとき，その_Graphは有限分岐(finite branching)^{であるという．} 本発表では_Graphは_nonemptyかつ_undirectedかつ_finite branching^{であるとする．}

(9)

榊原拓

Definitions

Branch

(10)

榊原拓

Definitions

Branch

(11)

榊原拓

Definitions

path

Definition (Path)

Graph G^に対しvertex^の有限列P = hvn∈ V (G ) | n < ki^がG

上の道_(path)であるとは，以下の条件を全てみたすときを

言う．

• ∀m < k∀n < m(vn6= vm⁾^，

• ∀n < k − 1((vn, vn+1) ∈ E )^．

始点が_v，終点が_w であるfinite path^をv-w path^{という．同} 様にしてinfinite path^{も定義できる．}

(12)

榊原拓

Definitions

Connected component

Definition (Connected) Graph G^に対し

∀v , w ∈ V (G )∃P(P is v -w path)

となるとき，_Gは連結している(connected)^という． Definition (Connected component)

Graph G^に対し，G^の極大なconnected subgraph^{を連結成分} (connected component)^とよぶ．

(13)

榊原拓

Definitions

Connected component

Definition (Connected) Graph G^に対し

∀v , w ∈ V (G )∃P(P is v -w path)

となるとき，_Gは連結している(connected)^という． Definition (Connected component)

Graph G^に対し，G^の極大なconnected subgraph^{を連結成分} (connected component)^とよぶ．

(14)

榊原拓

Definitions

Bipartite Graph

Definition (Bipartite)

Graph G = (V , E )^がV = V1∪ V2^かつV1∩ V2 = ∅^かつ E ⊆ V1× V2∪ V2× V1 ^{となるとき，}G ^{は二部グラフ} (bipartite graph)^といいG = (V1, V2; E )^で表す．

(15)

榊原拓

Matching

Definition (Matching)

ふたつの辺(e, f ), (e^′, f^′) ∈ E (G )^が独立(independent)^しているとは，_e _{6= e}

′∧ e 6= f^′∧ f 6= e^′∧ f 6= f^′ ^{を満たすときをい} う．_{Graph G}に含まれるindependent edge set M ⊆ E (G )^をマッチング_(matching)と呼ぶ．つまり，

e∈ M ⇔ ∀e^′ ∈ M(e 6= e^′ → e^とe^′^はindependent).

(16)

榊原拓

Matching

Marriage theorem

Fact (Marriage theorem for countable graph)

Bipatite graph G= (A, B; E )^に対し，G ^がA^のmatching^を持つ⇔ ∀finite setS ⊆ A(|∂S| ≥ |S|).

|∂S|^でS^上のvertex^{と隣接する}vertex set^を表す．

J.S.Hirst^によってRCA0^上ACA0と同値になることが示さている．

(17)

榊原拓

Matching

Marriage theorem

Fact (Marriage theorem for countable graph)

Bipatite graph G= (A, B; E )^に対し，G ^がA^のmatching^を持つ⇔ ∀finite setS ⊆ A(|∂S| ≥ |S|).

|∂S|^でS^上のvertex^{と隣接する}vertex set^を表す．

J.S.Hirst^によってRCA0^上ACA0と同値になることが示さている．

(18)

榊原拓

Matching

K¨onig’s duality theorem

Fact (K¨onig’s duality theorem for countable graph)

Bipartite graph G = (A, B; E )^に対し，matching M^とM^の各 edge^からvertexを一つずつ選んだ集合になっている_{cover C} が存在する．

C ⊆ V (G )^が被覆(cover)^{であるとは}

∀(v1, v2) ∈ E (G )(v1 ∈ C ∨ v2 ∈ C )^．

S.G.Simpson^とR.A.Shore^{らによって}RCA0^上ATR0^と同値に

なることが示されている．

(19)

榊原拓

Matching

K¨onig’s duality theorem

Fact (K¨onig’s duality theorem for countable graph)

Bipartite graph G = (A, B; E )^に対し，matching M^とM^の各 edge^からvertexを一つずつ選んだ集合になっている_{cover C} が存在する．

C ⊆ V (G )^が被覆(cover)^{であるとは}

∀(v1, v2) ∈ E (G )(v1 ∈ C ∨ v2 ∈ C )^．

S.G.Simpson^とR.A.Shore^{らによって}RCA0^上ATR0^と同値に

なることが示されている．

(20)

榊原拓

Motivation

• Marriage theorem , K¨onig’s duality theorem^{はいずれも} bipartite graph^上でのmatchingの性質を述べている主張．

• Countable graph上で何か考えられないか？

• Countable graph^上のperfect matching^{に関して成り立つ}

性質を_Tutteが求めており，その主張の複雑さを調べる．

(21)

榊原拓

Motivation

(22)

榊原拓

Motivation

(23)

榊原拓

Perfect Matching Definition (Perfect Matching)

Graph G^上のmatching M^が完全(perfect)^{であるとは} V(M) = V (G )^{となるときをいう．}

Definition (Augmenting path)

Graph G^とG ^上のmatching Mがあたえられたとする．_G上のfinite path P = hvn| n < kiが以下の条件を満たすとき M-augmenting path^という．

• v0, v_k−1∈ V (G ) \ V (M)^，

• ∀2m < k((v2_m, v2_m+1) ∈ E (G ) \ M)^，

• ∀2m + 1 < k − 1((v2_m+1, v2_m+2) ∈ M)^．

同様にしてinfinite path^がM-augmenting path^{であることも} 定義できる．

※ M-augmenting finite path^{は奇数長さ．}

(24)

榊原拓

• v0, v_k−1∈ V (G ) \ V (M)^，

• ∀2m < k((v2_m, v2_m+1) ∈ E (G ) \ M)^，

• ∀2m + 1 < k − 1((v2_m+1, v2_m+2) ∈ M)^．

(25)

榊原拓

• v0, v_k−1∈ V (G ) \ V (M)^，

• ∀2m < k((v2_m, v2_m+1) ∈ E (G ) \ M)^，

• ∀2m + 1 < k − 1((v2_m+1, v2_m+2) ∈ M)^．

(26)

榊原拓

Fact (Tutte’s theorem(1947))

Finite graph Gに対し以下は同値である． (1) G ^がperfect matching^を持つ，

(2) G ^{上の任意の}subgraph S^に対しq(G − S) ≤ |V (S)|^．

ただし_{q(G )}で_G上の頂点の数が奇数個の連結成分の数を

表す．

Fact (Countable ver(K.Steffens-1977)) Countable graph Gに対し以下は同値である．

(1) G ^がperfect matching^を持つ，

(2) (A)G ^{上の任意の}matching M^と任意のvertex

v ∈ V (G ) \ V (M)^に対し，v^{を始点とする}M-augmenting path^{が存在する．}

この定理が_RCA₀上_ACA₀と同値になることを示した．

(27)

榊原拓

表す．

(28)

榊原拓

表す．

(29)

榊原拓

Reverse Mathematics

Lemma (Tutte’s theorem in RCA0)

RCA0上で以下は同値である．Finite graph G ^に対し (1) G ^がperfect matching^を持つ，

(2) G ^{上の任意の}subgraph S^に対しq(G − S) ≤ |V (S)|^， (3) G ^{上の任意の}matching M^と任意のvertex

(30)

榊原拓

Proof.

((1)⇒(3))G^がperfect matching M^{をもつとし，任意に}G^上の_{matching M}

′

とvertex v ∈ V (G ) \ V (M^′)^{をとる．以下のよ} うな構成で_v_i を定める．

• v0:= v^，

• ^{ある自然数}n∈ N(n ≥ 1)^に対しi = 2n^のときv_i ^を (v_{i −1}, v_i) ∈ M^′^{となるようにとる，}

• ^{ある自然数}n_{∈ N}^に対しi = 2n + 1^のときv_i^を (v_{i −1}, v_i) ∈ M^{となるようにとる．}

G^がfinite graphであることからこの構成は高々有限回で止ま

り，_P _{= hv}_i | i < ki^はv^{を始点とする}M-augmenting path^である．

((3)⇒(1)) G^上のedge e ∈ E を任意にとる．明らかに_eのみからなる_{edge set}は_matchingである．₍₃₎より

{e}-augmenting pathが存在し，これから再び_matchingがとれる．同じ操作を繰り返せばperfect matching^{がとれる．}

(31)

榊原拓

Proof.

′

• v0:= v^，

(32)

榊原拓

Proof.

′

• v0:= v^，

(33)

榊原拓

Proof.

′

• v0:= v^，

(34)

榊原拓

figure(1)⇒(3)

(35)

榊原拓

figure(1)⇒(3)

(36)

榊原拓

figure(1)⇒(3)

(37)

榊原拓

figure(1)⇒(3)

(38)

榊原拓

figure(3)⇒(1)

(39)

榊原拓

figure(3)⇒(1)

(40)

榊原拓

figure(3)⇒(1)

(41)

榊原拓

figure(3)⇒(1)

(42)

榊原拓

figure(3)⇒(1)

(43)

榊原拓

Lemma

RCA0^{上で以下が示せる．}

Countable graph G^がperfect matching^{を持つならば，}G ^上の任意の_{matching M}と任意の_{vertex v} ∈ V (G ) \ V (M)^に対し， v^{を始点とする}M-augmenting path^{が存在する．}

Theorem

RCA0上で以下は同値である． (1) ACA0^，

(2) Countable graph G ^が条件(A)^{を満たすならば}G ^は perfect matching^を持つ．

(44)

榊原拓

Lemma

RCA0^{上で以下が示せる．}

Countable graph G^がperfect matching^{を持つならば，}G ^上の任意の_{matching M}と任意の_{vertex v} ∈ V (G ) \ V (M)^に対し， v^{を始点とする}M-augmenting path^{が存在する．}

Theorem

RCA0上で以下は同値である． (1) ACA0^，

(2) Countable graph G ^が条件(A)^{を満たすならば}G ^は perfect matching^を持つ．

(45)

榊原拓

Proving theorem(1)→(2)

条件_(A)をみたすgraphG = (N, E )を与える．ここで，各自然数_n_{∈ N}に対して_RCA₀を用いて以下の集合をとる．

M_n:= {M | M^はfinite matching ∧ V (M) ⊃ {0, 1, . . . , n}}. ここで二つの主張を示す．

Claim.1

∀n ∈ N(Mn6= ∅)^．

論理式_ϕを，_ϕ(hk₀, . . . , k_ii) :≡

∀j∃M({(0, k0), (1, k1), . . . , (i, ki)} ⊆ M ∈ Mj)^{と定義する．} Claim.2

ϕ(hk0, . . . , k_ii) → ∃l(ϕ(hk0, . . . , k_ii^⌢hli)).

(46)

榊原拓

条件_(A)をみたすgraphG = (N, E )を与える．ここで，各自然数_n_{∈ N}に対して_RCA₀を用いて以下の集合をとる．

M_n:= {M | M^はfinite matching ∧ V (M) ⊃ {0, 1, . . . , n}}. ここで二つの主張を示す．

Claim.1

∀n ∈ N(Mn6= ∅)^．

論理式_ϕを，_ϕ(hk₀, . . . , k_ii) :≡

∀j∃M({(0, k0), (1, k1), . . . , (i, ki)} ⊆ M ∈ Mj)^{と定義する．} Claim.2

ϕ(hk0, . . . , k_ii) → ∃l(ϕ(hk0, . . . , k_ii^⌢hli)).

(47)

榊原拓

Proving claim.1

Σ⁰₁-帰納法公理を用いて示す．

j = 0^のとき，0と隣接する辺をひとつとってくればよい． j = nまで成り立つとする．帰納法の仮定から_M _{∈ M}_nとなる有限マッチング_M が存在する．

もし，∃l ≤ n((l, n + 1) ∈ M ∈ Mn⁾^のときは

M^′ = M ∪ {(n + 1, l)}^{とすればよい．}

そうでない場合は₍₂₎より頂点_n_{+ 1}を始点とする_M-付加道をとってこれる．

この道は明らかに有限道なので，有限版の証明と同じ手法で {0, 1, . . . , n, n + 1} ⊂ M^′^{となる有限マッチング}^M^′^が構成できる．

よって_M

′ ∈ Mn+1となるので主張が成り立つ． _¤Claim.1

(48)

榊原拓

Proving claim.2

ϕ(hk0, . . . , k_ii)が成り立つとする．前主張より，

∀j ≥ i + 1∃M∃k({(0, k0), . . . , (i + 1, k)} ⊆ M ∈ M_j).

今_Gは有限分岐であるから_i_{+ 1}と隣接する頂点は高々有限個しかないので，

∃^∞j ≥ i + 1 ∈ N∃M({(0, k0), . . . , (i + 1, l)} ⊆ M ∈ M_j)

を満たす頂点_lが存在する．

M_j ^{の定義から}{(0, k0), (1, k1), . . . , (i, k_i), (i + 1, l)} ⊆ M ∈ M_j となる_j _{≥ i + 1}と_Mをとったとき，∀l < j(M ∈ Ml)^となるので，

∀j ∈ N∃M({(0, k0), . . . , (i + 1, l)} ⊆ M ∈ Mj).

よって_ϕ(hk₀, . . . , k_ii^⌢hli)^{は成り立つ．} ¤Claim.2

(49)

榊原拓

主張と_ACAを用いて以下のような再帰的関数_f _{: N → N}が作れる．

• f(0) := min{k0| ∀j∃M((0, k0) ∈ M ∈ Mj)}^，

• f(n + 1) := min{kn+1 | ∀j ≥

n+ 1∃M({(0, f (0)), . . . , (n + 1, kn+1)} ⊆ M ∈ Mj)}^．明らかにedge set {(n, f (n)) | n ∈ N}^はG^上のperfect matching^である．

(50)

榊原拓

単射_f _{: N → N}をとる．ここで以下のような_graphを_RCA₀上で構成する．_{Graph G}の頂点の集合はN₀_{∪ N}₁_{∪ N}₂_{∪ N}₃とす

る．_{Edge set E}を以下のようにして定める．

• n _{≤ f (n)}^のとき(n0, n1), (n2, n3) ∈ E^，

• n < m^かつf(m) = n^のとき (m0, m1), (n0, m2), (n1, m3) ∈ E^．

明らかに_G は条件_(A)を満たすのでperfect matching M^が存在．すると，

n∈ rng(f ) ↔ ∃m < n(f (m) = n) ∨ (n0, n1) 6∈ M.

よって_RCA₀上で_f の値域がとれる． _¤Theorem

(51)

榊原拓

References

• K. STEFFENS, MATCHINGS IN COUNTABLE GRAPHS, Can. J. Math., Vol. XXIX, No1, 1977, pp. 165-168.

• J. Hirst, Combinatorics in subsystem of second order arithmetic, Ph.D. Thesis, The Pennsylvania State University, 1987.

• R. Aharoni, M. Maginor, and R. A. Shore, On the strength of K¨onig’s Duality Theorem for Infinite Bipartite Graphs, J. Combin. Th., Ser. B, 54(1992), 257-290.

• Stephen. G. Simpson, ON THE STRENGTH OF K ¨ONIG’S DUALITY THEOREM FOR COUNTABLE BIPARTITE GRAPHS, J. Symb. Logic. 59(1994), 113-123.

• Stephen. G. Simpson, Subsystem of Second Order Arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999.

Thanks for your attention.