ファイル置き場 Sendai Logic Homepage

修士論文中間発表

グラフ理論と逆数学

藤原 誠

東北大学理学研究科数学専攻 2011.9.2 東北大学ロジックセミナー

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{1 / 21}

修士論文概要

タイトル _: グラフ理論と逆数学 ₍ 仮 ₎

1

_{逆数学について}

2

グラフ理論の逆数学における先行研究

( 結婚定理とその応用、グラフ彩色、連結性、最短

距離問題、トポロジカルソート、最小全域木

問題… ₎

3

_{グラフの平面性判定 ( クラトウスキーの定理 ) 及び}

その周辺の話題に関する逆数学的考察・ ・ ・勉強中

今日の発表

1

_{逆数学のあらすじ}

( 修論発表会を意識して… ₎

2

_{グラフ理論の逆数学}

結婚定理とその応用

グラフ彩色

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{3 / 21}

逆数学

目的：数学の諸定理をその複雑さによって分類する。

具体的には・・・

数学の諸定理に対して「それを証明するのに最低限必要な公理 系」を調べる。

これまで逆数学研究は主に二階算術と言われる自然数と自然数 の集合を扱える程度の弱い形式体系の中で行われてきた。

古典的数学の大半は二階算術の中で展開できる。

二階算術の部分体系₍公理系₎を考えることで数学の諸定理 がきれいに分類される。

逆数学

目的：数学の諸定理をその複雑さによって分類する。

具体的には・・・

数学の諸定理に対して「それを証明するのに最低限必要な公理 系」を調べる。

これまで逆数学研究は主に二階算術と言われる自然数と自然数 の集合を扱える程度の弱い形式体系の中で行われてきた。

古典的数学の大半は二階算術の中で展開できる。

二階算術の部分体系₍公理系₎を考えることで数学の諸定理 がきれいに分類される。

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{4 / 21}

逆数学

目的：数学の諸定理をその複雑さによって分類する。

具体的には・・・

数学の諸定理に対して「それを証明するのに最低限必要な公理 系」を調べる。

これまで逆数学研究は主に二階算術と言われる自然数と自然数 の集合を扱える程度の弱い形式体系の中で行われてきた。

古典的数学の大半は二階算術の中で展開できる。

二階算術の部分体系₍公理系₎を考えることで数学の諸定理 がきれいに分類される。

逆数学

目的：数学の諸定理をその複雑さによって分類する。

具体的には・・・

数学の諸定理に対して「それを証明するのに最低限必要な公理 系」を調べる。

これまで逆数学研究は主に二階算術と言われる自然数と自然数 の集合を扱える程度の弱い形式体系の中で行われてきた。

古典的数学の大半は二階算術の中で展開できる。

二階算術の部分体系₍公理系₎を考えることで数学の諸定理 がきれいに分類される。

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{4 / 21}

逆数学

目的：数学の諸定理をその複雑さによって分類する。

具体的には・・・

数学の諸定理に対して「それを証明するのに最低限必要な公理 系」を調べる。

これまで逆数学研究は主に二階算術と言われる自然数と自然数 の集合を扱える程度の弱い形式体系の中で行われてきた。

古典的数学の大半は二階算術の中で展開できる。

二階算術の部分体系₍公理系₎を考えることで数学の諸定理 がきれいに分類される。

逆数学

目的：数学の諸定理をその複雑さによって分類する。

具体的には・・・

数学の諸定理に対して「それを証明するのに最低限必要な公理 系」を調べる。

これまで逆数学研究は主に二階算術と言われる自然数と自然数 の集合を扱える程度の弱い形式体系の中で行われてきた。

古典的数学の大半は二階算術の中で展開できる。

二階算術の部分体系₍公理系₎を考えることで数学の諸定理 がきれいに分類される。

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{4 / 21}

逆数学

目的：数学の諸定理をその複雑さによって分類する。

具体的には・・・

数学の諸定理に対して「それを証明するのに最低限必要な公理 系」を調べる。

これまで逆数学研究は主に二階算術と言われる自然数と自然数 の集合を扱える程度の弱い形式体系の中で行われてきた。

古典的数学の大半は二階算術の中で展開できる。

二階算術の部分体系₍公理系₎を考えることで数学の諸定理 がきれいに分類される。

二階算術_Z2は次の₃種類の公理からなる二階言語L₂ の形式体 系である。

(1)^{自然数の順序}< や演算+, · に関する基本公理

(2)^{帰納法公理：}(ϕ(0) ∧ ∀n(ϕ(n) → ϕ(n + 1))) → ∀nϕ(n) (3)^{集合存在公理：}∃X∀x(x ∈ X ↔ ϕ(x))

ここでϕ(x) は X を自由変数に含まない 基礎理論_RCA0： ₍₁₎＋ _Σ⁰

1^{帰納法公理 ＋ ∆} 0

1^{集合存在公理}

多くの数学的主張は_RCA0上で表現できる。 WKL₀^： RCA₀+^{弱ケーニヒの補題}

ACA₀^： RCA₀+^{算術的集合存在公理} ATR₀^： RCA₀+^{算術的超限再帰法公理} Π¹₁^−CA₀^{： RCA}0⁺Π¹₁^{集合存在公理} [H.Friedman 1974]

数学の定理の多くは_RCA0上で証明できるか、そうでなければ WKL₀^、ACA₀^、ATR₀^、_Π¹₁−CA₀のどれかと論理的同値である_!

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{5 / 21}

二階算術_Z2は次の₃種類の公理からなる二階言語L₂ の形式体 系である。

(1)^{自然数の順序}< や演算+, · に関する基本公理

(2)^{帰納法公理：}(ϕ(0) ∧ ∀n(ϕ(n) → ϕ(n + 1))) → ∀nϕ(n) (3)^{集合存在公理：}∃X∀x(x ∈ X ↔ ϕ(x))

ここでϕ(x) は X を自由変数に含まない 基礎理論_RCA0： ₍₁₎＋ _Σ⁰

1^{帰納法公理 ＋ ∆} 0

1^{集合存在公理}

多くの数学的主張は_RCA0上で表現できる。 WKL₀^： RCA₀+^{弱ケーニヒの補題}

ACA₀^： RCA₀+^{算術的集合存在公理} ATR₀^： RCA₀+^{算術的超限再帰法公理} Π¹₁^−CA₀^{： RCA}0⁺Π¹₁^{集合存在公理} [H.Friedman 1974]

数学の定理の多くは_RCA0上で証明できるか、そうでなければ WKL₀^、ACA₀^、ATR₀^、_Π¹₁−CA₀のどれかと論理的同値である_!

二階算術_Z2は次の₃種類の公理からなる二階言語L₂ の形式体 系である。

(1)^{自然数の順序}< や演算+, · に関する基本公理

(2)^{帰納法公理：}(ϕ(0) ∧ ∀n(ϕ(n) → ϕ(n + 1))) → ∀nϕ(n) (3)^{集合存在公理：}∃X∀x(x ∈ X ↔ ϕ(x))

ここでϕ(x) は X を自由変数に含まない 基礎理論_RCA0： ₍₁₎＋ _Σ⁰

1^{帰納法公理 ＋ ∆} 0

1^{集合存在公理}

多くの数学的主張は_RCA0上で表現できる。 WKL₀^： RCA₀+^{弱ケーニヒの補題}

ACA₀^： RCA₀+^{算術的集合存在公理} ATR₀^： RCA₀+^{算術的超限再帰法公理} Π¹₁^−CA₀^{： RCA}0⁺Π¹₁^{集合存在公理} [H.Friedman 1974]

数学の定理の多くは_RCA0上で証明できるか、そうでなければ WKL₀^、ACA₀^、ATR₀^、_Π¹₁−CA₀のどれかと論理的同値である_!

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{5 / 21}

二階算術_Z2は次の₃種類の公理からなる二階言語L₂ の形式体 系である。

(1)^{自然数の順序}< や演算+, · に関する基本公理

(2)^{帰納法公理：}(ϕ(0) ∧ ∀n(ϕ(n) → ϕ(n + 1))) → ∀nϕ(n) (3)^{集合存在公理：}∃X∀x(x ∈ X ↔ ϕ(x))

ここでϕ(x) は X を自由変数に含まない 基礎理論_RCA0： ₍₁₎＋ _Σ⁰

1^{帰納法公理 ＋ ∆} 0

1^{集合存在公理}

多くの数学的主張は_RCA0上で表現できる。 WKL₀^： RCA₀+^{弱ケーニヒの補題}

ACA₀^： RCA₀+^{算術的集合存在公理} ATR₀^： RCA₀+^{算術的超限再帰法公理} Π¹₁^−CA₀^{： RCA}0⁺Π¹₁^{集合存在公理} [H.Friedman 1974]

数学の定理の多くは_RCA0上で証明できるか、そうでなければ WKL₀^、ACA₀^、ATR₀^、_Π¹₁−CA₀のどれかと論理的同値である_!

二階算術_Z2は次の₃種類の公理からなる二階言語L₂ の形式体 系である。

(1)^{自然数の順序}< や演算+, · に関する基本公理

(2)^{帰納法公理：}(ϕ(0) ∧ ∀n(ϕ(n) → ϕ(n + 1))) → ∀nϕ(n) (3)^{集合存在公理：}∃X∀x(x ∈ X ↔ ϕ(x))

ここでϕ(x) は X を自由変数に含まない 基礎理論_RCA0： ₍₁₎＋ _Σ⁰

1^{帰納法公理 ＋ ∆} 0

1^{集合存在公理}

多くの数学的主張は_RCA0上で表現できる。 WKL₀^： RCA₀+^{弱ケーニヒの補題}

ACA₀^： RCA₀+^{算術的集合存在公理} ATR₀^： RCA₀+^{算術的超限再帰法公理} Π¹₁^−CA₀^{： RCA}0⁺Π¹₁^{集合存在公理} [H.Friedman 1974]

数学の定理の多くは_RCA0上で証明できるか、そうでなければ WKL₀^、ACA₀^、ATR₀^、_Π¹₁−CA₀のどれかと論理的同値である_!

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{5 / 21}

グラフ理論の逆数学

RCA₀ ^{有限グラフ全般}

   有限結婚定理

有界グラフが局所_k彩色可能ならば_{2k − 1}彩色可能_{(k ≥ 2)} WKL₀ 有界結婚定理、有界対称結婚定理

   有界グラフが局所_k彩色可能ならば_{2k − 2}彩色可能_{(k ≥ 2)} グラフが局所_k彩色可能ならば_m彩色可能_{(m ≥ k ≥ 2)} ACA₀ 結婚定理、対称結婚定理

連結性 最小距離問題 最小全域木問題

トポロジー的ソーティングの存在

ATR₀ ^高々1つのハミルトン道をもつグラフの列から ハミルトン道を持つものを選択する関数の存在

Π¹₁^−CA₀ グラフの列からハミルトン道を持つものを選択する関数 の存在

グラフ理論の逆数学

RCA₀ ^{有限グラフ全般}

有限結婚定理

有界グラフが局所_k彩色可能ならば_{2k − 1}彩色可能_{(k ≥ 2)} WKL₀ 有界結婚定理、有界対称結婚定理

   有界グラフが局所_k彩色可能ならば_{2k − 2}彩色可能_{(k ≥ 2)} グラフが局所_k彩色可能ならば_m彩色可能_{(m ≥ k ≥ 2)} ACA₀ 結婚定理、対称結婚定理

連結性 最小距離問題 最小全域木問題

トポロジー的ソーティングの存在

ATR₀ ^高々1つのハミルトン道をもつグラフの列から ハミルトン道を持つものを選択する関数の存在

Π¹₁^−CA₀ グラフの列からハミルトン道を持つものを選択する関数 の存在

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{7 / 21}

結 婚 問題

少年と少女が多数います。

誰と誰が知り合いかどうかが分かっています。 少年と少女は知り合い同士でしか結婚できません。 多重婚、同性婚は認めません。

全ての少年が無事結婚することはできるでしょうか？

全ての少年が結婚できる⇔ n 人の少年は n 人の少女を知っている

結婚定理

B, G, R は集合とし、R ⊂ B × G とする。このとき

∀B^′ ⊂ B∃G^′ ⊂ G(∀g ∈ G^′∃b ∈ B^′((b, g) ∈ R) ∧ |B^′| ≤ |G^′|)

=⇒ ∃ f ( f は B から G への単射 ∧B × f (B) ⊂ R)^. 以後R を結婚問題、 f を結婚問題の解、

∀B^′ ⊂ B∃G^′ ⊂ G(∀g ∈ G^′∃b ∈ B^′((b, g) ∈ R) ∧ |B^′| ≤ |G^′|) を条件 H と言うことにする。

結 婚 問題

少年と少女が多数います。

誰と誰が知り合いかどうかが分かっています。 少年と少女は知り合い同士でしか結婚できません。 多重婚、同性婚は認めません。

全ての少年が無事結婚することはできるでしょうか？

全ての少年が結婚できる⇔ n 人の少年は n 人の少女を知っている

結婚定理

B, G, R は集合とし、R ⊂ B × G とする。このとき

∀B^′ ⊂ B∃G^′ ⊂ G(∀g ∈ G^′∃b ∈ B^′((b, g) ∈ R) ∧ |B^′| ≤ |G^′|)

=⇒ ∃ f ( f は B から G への単射 ∧B × f (B) ⊂ R)^. 以後R を結婚問題、 f を結婚問題の解、

∀B^′ ⊂ B∃G^′ ⊂ G(∀g ∈ G^′∃b ∈ B^′((b, g) ∈ R) ∧ |B^′| ≤ |G^′|) を条件 H と言うことにする。

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{8 / 21}

結 婚 問題

少年と少女が多数います。

誰と誰が知り合いかどうかが分かっています。 少年と少女は知り合い同士でしか結婚できません。 多重婚、同性婚は認めません。

全ての少年が無事結婚することはできるでしょうか？

全ての少年が結婚できる⇔ n 人の少年は n 人の少女を知っている

結婚定理

B, G, R は集合とし、R ⊂ B × G とする。このとき

∀B^′ ⊂ B∃G^′ ⊂ G(∀g ∈ G^′∃b ∈ B^′((b, g) ∈ R) ∧ |B^′| ≤ |G^′|)

=⇒ ∃ f ( f は B から G への単射 ∧B × f (B) ⊂ R)^. 以後R を結婚問題、 f を結婚問題の解、

∀B^′ ⊂ B∃G^′ ⊂ G(∀g ∈ G^′∃b ∈ B^′((b, g) ∈ R) ∧ |B^′| ≤ |G^′|) を条件 H と言うことにする。

結婚定理と逆数学 (Hirst,1987)

有限結婚定理

RCA₀ ⊢^条件Hを満たす任意の有限結婚問題(B 有限,G, R 可算) は解をもつ

結婚定理

RCA0 ^⊢条件H , I を満たす任意の結婚問題(B, G, R 可算)^は解を もつ_↔ACA0

有界結婚定理

RCA₀ ⊢条件_{H , I}^′を満たす任意の結婚問題(B, G, R 可算)^は解を もつ_↔WKL0

条件I : ∀b ∈ B∃n∀g ∈ G ((b, g) ∈ R → g < n)

条件_I^′ : ∃h(h は B から G への関数 ∧∀x, y((x, y) ∈ R → y < h(x)))

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{9 / 21}

対称結婚定理と逆数学 (Hirst,1987)

対称結婚定理 RCA0^{上以下が同値}

1 _ACA0

2 _{条件Hsym, Isym}を満たす任意の結婚問題は対称解をもつ 条件H_sym：

∀B^′ ⊂ B∃G^′ ⊂ G(∀g ∈ G^′∃b ∈ B^′((b, g) ∈ R) ∧ |B^′| ≤ |G^′|)

∧∀G^′ ⊂ G∃B^′ ⊂ B(∀b ∈ B^′∃g ∈ G^′((b, g) ∈ R) ∧ |G^′| ≤ |B^′|) 条件_Isym：∀b ∈ B∃n∀g ∈ G ((b, g) ∈ R → g < n)

∧∀g ∈ G∃n∀b ∈ B ((b, g) ∈ R → b < n) 対称解：B × f (B) ⊂ R なる B から G への全単射 f

対称有界結婚定理 RCA₀^{上以下が同値}

1 _WKL0

2 条件_{Hsym, I}^′_symを満たす任意の結婚問題は対称解をもつ

3 ∀k ≥ 1(k− 社会は対称解をもつ )

4 2− 社会は対称解をもつ 条件H_sym：

∀B^′ ⊂ B∃G^′ ⊂ G(∀g ∈ G^′∃b ∈ B^′((b, g) ∈ R) ∧ |B^′| ≤ |G^′|)

∧∀G^′ ⊂ G∃B^′ ⊂ B(∀b ∈ B^′∃g ∈ G^′((b, g) ∈ R) ∧ |G^′| ≤ |B^′|) 条件_I^′_sym：

∃h(h は B から G への関数 ∧∀x, y((x, y) ∈ R → y < h(x)))

∧∃h^′(h^′はG から B への関数 ∧∀x, y((x, y) ∈ R → x < h^′(y))) k− 社会：

それぞれの人がちょうどk 人の異性を知っている結婚問題

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{11 / 21}

証明

1 → 2 ^まずB, G を並べ挙げ、長さ k の道が B, G, R を k 番目までに 制限した時の対称解をコードするような木_{T を構成する。} このとき_{T は関数 h, h}^′から再帰的につくれる関数で抑えら れる。

有界ケーニヒの補題_(RCA0上_WKL0と同値₎より木_{T は無限} 道 p を持つ。p は対称解をコードする。

2 → 3 k− 社会は条件 H_sym, I^′_symを満たすことが示せる。

4 → 1 発想は「偶数と奇数の互換性を用いる！」

WKL₀^{を示す代わりに}RCA₀上それと同値である「値域が重 ならない₂つの単射 f , g の分離集合 S が存在する」を示す。 次のようなグラフを考える。_→黒板

このグラフは2− 社会であり、4 から対称解 s : B → G が存 在する。s から求める分離集合 S が得られる。

証明

1 → 2 ^まずB, G を並べ挙げ、長さ k の道が B, G, R を k 番目までに 制限した時の対称解をコードするような木_{T を構成する。} このとき_{T は関数 h, h}^′から再帰的につくれる関数で抑えら れる。

有界ケーニヒの補題_(RCA0上_WKL0と同値₎より木_{T は無限} 道 p を持つ。p は対称解をコードする。

2 → 3 k− 社会は条件 H_sym, I^′_symを満たすことが示せる。

4 → 1 発想は「偶数と奇数の互換性を用いる！」

WKL₀^{を示す代わりに}RCA₀上それと同値である「値域が重 ならない₂つの単射 f , g の分離集合 S が存在する」を示す。 次のようなグラフを考える。_→黒板

このグラフは2− 社会であり、4 から対称解 s : B → G が存 在する。s から求める分離集合 S が得られる。

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{12 / 21}

証明

1 → 2 ^まずB, G を並べ挙げ、長さ k の道が B, G, R を k 番目までに 制限した時の対称解をコードするような木_{T を構成する。} このとき_{T は関数 h, h}^′から再帰的につくれる関数で抑えら れる。

有界ケーニヒの補題_(RCA0上_WKL0と同値₎より木_{T は無限} 道 p を持つ。p は対称解をコードする。

2 → 3 k− 社会は条件 H_sym, I^′_symを満たすことが示せる。

4 → 1 発想は「偶数と奇数の互換性を用いる！」

WKL₀^{を示す代わりに}RCA₀上それと同値である「値域が重 ならない₂つの単射 f , g の分離集合 S が存在する」を示す。 次のようなグラフを考える。_→黒板

このグラフは2− 社会であり、4 から対称解 s : B → G が存 在する。s から求める分離集合 S が得られる。

対称有界結婚定理の応用 ₍ バナッハの定理 ₎

[ 定理 ]RCA₀^{上以下が同値}

1 _WKL0

2 f , g は N から N への単射 ∧ f , g の値域集合が存在する

→ ∃h(hは N から N への全単射_∧

∀n, m(h(n) = m → ( f (n) = m ∨ n = g(m)))⁾

※ 値域集合の存在は束縛関数の存在に対応する。 [ 定理 ]RCA₀^{上以下が同値}

1 _ACA0

2 f , g は N から N への単射

→ ∃h(hは N から N への全単射_∧

∀n, m(h(n) = m → ( f (n) = m ∨ n = g(m)))⁾

3 f , g は N から N への単射 ∧ g の値域集合が存在する

→ ∃h(hは N から N への全単射_∧

∀n, m(h(n) = m → ( f (n) = m ∨ n = g(m)))⁾

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{13 / 21}

対称有界結婚定理の応用 ₍ バナッハの定理 ₎

[ 定理 ]RCA₀^{上以下が同値}

1 _WKL0

2 f , g は N から N への単射 ∧ f , g の値域集合が存在する

→ ∃h(hは N から N への全単射_∧

∀n, m(h(n) = m → ( f (n) = m ∨ n = g(m)))⁾

※ 値域集合の存在は束縛関数の存在に対応する。 [ 定理 ]RCA₀^{上以下が同値}

1 _ACA0

2 f , g は N から N への単射

→ ∃h(hは N から N への全単射_∧

∀n, m(h(n) = m → ( f (n) = m ∨ n = g(m)))⁾

3 f , g は N から N への単射 ∧ g の値域集合が存在する

→ ∃h(hは N から N への全単射_∧

∀n, m(h(n) = m → ( f (n) = m ∨ n = g(m)))⁾

グラフ彩色と逆数学

c がグラフ (V, E) の k 彩色：

c は V から k への関数 ∧(x, y) ∈ E → c(x) , c(y)

グラフ(V, E) が k 彩色可能：(V, E) の k 彩色が存在する グラフ(V, E) が局所 k 彩色可能：

(V, E) の任意の有限部分グラフが k 彩色可能 無向グラフ(V, E) が有界：

∃h(h は V から N への関数 ∧∀v, v^′((v, v^′) ∈ E → v^′ < h(v))) [^定理] RCA₀^{上以下が同値}

1 _WKL0

2 局所k 彩色可能なグラフは k 彩色可能である (k ≥ 2)

3 局所k 彩色可能な有界グラフは k 彩色可能である (k ≥ 2) [3 → 1]^「2− 社会は対称解をもつ →WKL₀^{」の証明に用いたグラ}

フを適用できる。

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{14 / 21}

グラフ彩色と逆数学

c がグラフ (V, E) の k 彩色：

c は V から k への関数 ∧(x, y) ∈ E → c(x) , c(y)

グラフ(V, E) が k 彩色可能：(V, E) の k 彩色が存在する グラフ(V, E) が局所 k 彩色可能：

(V, E) の任意の有限部分グラフが k 彩色可能 無向グラフ(V, E) が有界：

∃h(h は V から N への関数 ∧∀v, v^′((v, v^′) ∈ E → v^′ < h(v))) [^定理] RCA₀^{上以下が同値}

1 _WKL0

2 局所k 彩色可能なグラフは k 彩色可能である (k ≥ 2)

3 局所k 彩色可能な有界グラフは k 彩色可能である (k ≥ 2) [3 → 1]^「2− 社会は対称解をもつ →WKL₀^{」の証明に用いたグラ}

フを適用できる。

定理_(Hirst＆Gasarch,1998) RCA₀^{上以下が同値}

1 _WKL0

2 局所k 彩色可能なグラフは 2k − 1 彩色可能である (k ≥ 2) [1 → 2] k ≥ 2 に対して k 彩色は 2k − 1 彩色でもあるので明らか。 [2 → 1]WKL₀^{を示す代わりに}RCA₀上それと同値である「値域 が重ならない₂つの単射 f , g の分離集合 S が存在する」を示す。 局所k 彩色可能なグラフを以下の手順で再帰的に構成する。

k 頂点完全グラフを N 個と k × N 頂点完全グラフを用意する。 2k − 1 彩色の方法が制限されるようにそれらを辺で結ぶ。 n が f または g の値域であるとき n 番目の k 頂点完全グラフ とk × N 頂点完全グラフを結ぶ。この際 f か g かに応じて

「ずらして」結ぶ。

N個のk 頂点完全グラフの彩色の情報から f , g の分離集合が再帰 的に得られる。

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{15 / 21}

定理(Schmerl,2000) RCA₀^{上以下が同値}

1 _WKL0

2 局所k 彩色可能なグラフは m 彩色可能である (m ≥ k ≥ 2) 系(Bean,1976)

任意のm ≥ k ≥ 2 に対して再帰的 m 彩色可能でない局所的 k 彩色 可能な再帰的グラフが存在する。

一般に再帰的グラフは局所k 彩色可能であっても再帰的な m(m ≥ k) 彩色をもたないかもしれないが、強再帰的グラフに関 してはそうではない。

実際、局所k 彩色可能な強再帰的グラフは必ず再帰的な 2k − 1 彩 色をもつ。

定理(Schmerl,2000) RCA₀^{上以下が同値}

1 _WKL0

2 局所k 彩色可能なグラフは m 彩色可能である (m ≥ k ≥ 2) 系(Bean,1976)

任意のm ≥ k ≥ 2 に対して再帰的 m 彩色可能でない局所的 k 彩色 可能な再帰的グラフが存在する。

一般に再帰的グラフは局所k 彩色可能であっても再帰的な m(m ≥ k) 彩色をもたないかもしれないが、強再帰的グラフに関 してはそうではない。

実際、局所k 彩色可能な強再帰的グラフは必ず再帰的な 2k − 1 彩 色をもつ。

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{16 / 21}

定理(Schmerl,2000) RCA₀^{上以下が同値}

1 _WKL0

2 局所k 彩色可能なグラフは m 彩色可能である (m ≥ k ≥ 2) 系(Bean,1976)

任意のm ≥ k ≥ 2 に対して再帰的 m 彩色可能でない局所的 k 彩色 可能な再帰的グラフが存在する。

一般に再帰的グラフは局所k 彩色可能であっても再帰的な m(m ≥ k) 彩色をもたないかもしれないが、強再帰的グラフに関 してはそうではない。

実際、局所k 彩色可能な強再帰的グラフは必ず再帰的な 2k − 1 彩 色をもつ。

deg(x) : ^頂点x^{に隣接する頂点の数}

グラフ_Gが強再帰的：_Gは再帰的∧deg : V → N^が再帰的 再帰的グラフ理論から(Schmerl,1980)

任意のk ≥ 2 に対して、局所 k 彩色可能な強再帰的グラフは 再帰的2k − 1 彩色可能である。

任意のk ≥ 2 に対して、再帰的 2k − 2 彩色可能でない局所 k 彩色可能な強再帰的グラフが存在する。

定理_(Hirst＆Gasarch,1998) RCA0^{で以下が示せる。}

局所k 彩色可能な有界グラフは 2k − 1 彩色可能である (k ≥ 2) RCA₀^{上以下が同値}

1 _WKL0

2 局所_k彩色可能な有界グラフは_{2k − 2}彩色可能である_{(k ≥ 2)}

逆数学において、有界グラフは再帰的グラフ理論における「強再帰的 グラフ」に対応するものである。

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{17 / 21}

deg(x) : ^頂点x^{に隣接する頂点の数}

グラフ_Gが強再帰的：_Gは再帰的∧deg : V → N^が再帰的 再帰的グラフ理論から(Schmerl,1980)

任意のk ≥ 2 に対して、局所 k 彩色可能な強再帰的グラフは 再帰的2k − 1 彩色可能である。

任意のk ≥ 2 に対して、再帰的 2k − 2 彩色可能でない局所 k 彩色可能な強再帰的グラフが存在する。

定理_(Hirst＆Gasarch,1998) RCA0^{で以下が示せる。}

局所k 彩色可能な有界グラフは 2k − 1 彩色可能である (k ≥ 2) RCA₀^{上以下が同値}

1 _WKL0

2 局所_k彩色可能な有界グラフは_{2k − 2}彩色可能である_{(k ≥ 2)} 逆数学において、有界グラフは再帰的グラフ理論における「強再帰的 グラフ」に対応するものである。

RCA₀^{上以下が同値}

1 _WKL0

2 局所k 彩色可能な有界グラフは 2k − 2 彩色可能である (k ≥ 2) [1 → 2] k ≥ 2 に対して k 彩色は 2k − 2 彩色でもあるので明らか。 [2 → 1] 発想は「2− 社会は対称解をもつ →WKL0^{」の証明と同}

じ。偶数と奇数の互換性を用いる！

局所k 彩色可能な有界グラフを以下の手順で再帰的に構成する。 k × k 個の頂点からなる N × N 個のブロック B_n,n^{と N 個のブ} ロック_Bnを用意する。

ブロック同士は2k − 2 彩色による組合せ的性質 P, Q が交互 に現れるように結ぶ。

B_{i, j}^とB_{i, j+1}, B_i^とB_i+1(i, j ∈ N) を結んでおく。

f (m) = n のとき Bn,m^とB2m^を結び、g(m) = n のとき Bn,m^と

B_2m+1^を結ぶ。

ブロック_Bn,0(n ∈ N) の情報から f , g の分離集合 S が得られる。

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{18 / 21}

今後の展望

幾何学的グラフ理論 ₍ 特にグラフの平面性判定 ₎ の

逆数学

グラフ彩色と逆数学

参考文献

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

2 W.Gasarch and J.Hirst, Reverse mathematics and recursive graph theory, Mathematical Logic Quarterly,vol.44, 1998.

3 D.R.Bean, Effective Coloration, J.Symb.Logic41, 1976.

4 J.Schmerl, Recursive colorings of graphs, Can.J.Math.32, 1980.

5 J.Schmerl, Graph coloring and reverse mathematics, Mathematical Logic Quarterly,vol.46, 2000.

(東北大学ロジックセミナー₎ グラフ理論と逆数学 _{20 / 21}

ありがとうございました！