完全グラフの R 3 への線形埋め込みと結び目 Knots in linear embeddings of complete graphs in R 3

(1)

完全グラフの R ³ への線形埋め込みと結び目 Knots in linear embeddings of complete graphs in R ³

数学専攻瀬沼勇介

SENUMA Yusuke

1 準備

1.1

グラフ

(graph) G

とは，

2

つの集合

V, E

と

1

つの関数

ψ

からなる

3

個組

(V, E, ψ)

をいう．ここで，

V

は空でない集合で，その要素を頂点

(vertex)

という．

E

は

V

と共通部分を持たない集合で，その要素を辺

(edge)

という．

V

と

E

が共に有限集合の時にそのグラフは有限であるという

.

本論文ではグラフは全て有限グラフのこととする

. ψ

は

G

の辺と

G

の頂点の非順序対を対応させる関数で，接続関数

(incidence function)

という．

u, v ∈ V

かつ

e ∈ E

で，

ψ(e) = { u, v }

^{を満たすとき，}

e

は

u

と

v

を結ぶ

(join)

といい，

u, v

を

e

の端点

(end vertices)

という．また，

u

と

v

は隣接する

(adjacent)

といい，

u, v

は

e

に接続する

(incident)

という．以後，簡単のために，

ψ(e) = { u, v }

^を

ψ(e) = uv

または

ψ(e) = vu

で表す．

例

1.1

（図

1

）

G = (V, E, ψ), V = { u, v, w, x, y } , E = { a, b, c, d, e, f, g, h } ,

ψ(a) = uv, ψ(b) = vv, ψ(c) = vw, ψ(d) = wx, ψ(e) = vx, ψ(f ) = wx, ψ(g) = ux, ψ(h) = xy.

v b

a

c e

w d

f u

g

x h

y

図1 G= (V, E, ψ)

図

1

において，

b

のように両端点が同じ辺をループ

(loop)

といい，

d

と

f

のように同じ頂点間を結ぶ辺を多重辺

(multiple edges)

という．ループも多重辺も持たないグラフを単純グラフ

(simple graph)

という

.

単純グラフでは，頂点のどの対も高々

1

本の辺で結ばれているので，端点が

u, v

である辺を

uv

または

vu

で表す．

G = (V, E, ψ)

をグラフとする．

G

のどの

2

つの頂点も辺で結ばれているとき，

G

を完全グラフ

(complete graph)

といい，

n

頂点完全グラフを

K

_n で表す．

G = (V, E, ψ), G

⁰

= (V

⁰

, E

⁰

, ψ

⁰

)

を

2

つのグラフとする．

G

⁰が

G

の部分グラフ

(subgraph)

であるとは，

V

⁰

⊆ V , E

⁰

⊆ E

で，

ψ

⁰が

ψ

の

E

⁰への制限であるときをいい，

G

⁰

⊆ G

で表す

.

グラフ

H

がグラフ

G

のマイナー

(minor)

であるとは，図

2

のような

G

から辺や頂点を

v

1

e v

2

v

2

v

1

v

2

v'

G

G − v

₁

v

1を取り除く

G − e e

を取り除く

G/e e

を縮約する

図2 頂点の除去,辺の除去,辺の縮約

取り除く操作，辺を縮約する操作を，何回か行うことにより

H

が得られるときをいう．

1

(2)

グラフ

W = (V, E, ψ)

が歩道

(walk)

とは，

V = { v

0

, v

1

, . . . , v

n

} , E = { e

1

, e

2

, . . . , e

n

} , ψ(e

i

) = v

i−1

v

i

(i = 1, . . . , n)

であるときをいう．このとき，

v

0

, v

nを

W

の端点

(end vertices)

，

v

1

, . . . , v

n−1を

W

の内点

(inner vertices)

，

n

を

W

の長さ

(length)

という．

v

i がすべて異なるような歩道を，道

(path)

という

.

また，

n ≥ 3

に対して，

v

0

= v

nで

, v

1

, . . . , v

n−1が全て異なる歩道を閉路

(cycle)

という

.

1.2

結び目

R

³に埋め込まれた単純閉曲線を結び目

(knot)

といい，互いに素な結び目の和集合を絡み目

(link)

という．

絡み目

L

が

C

1

∪ C

2

∪ · · · ∪ C

nからなるとき，各結び目

C

1

, C

2

, . . . , C

nを

L

の成分

(component)

という．

絡み目の平面への正射影が正則

(regular)

であるとは，高々有限個の多重点からなり，それらがすべて横断的な

2

重点であるときをいい，この

2

重点を交差点

(crossing)

という．絡み目のダイアグラム

(diagram)

とは，

正則射影図の各交差点に交差の上下の情報を与えたものをいう．

2 空間グラフと結び目

グラフ

G

の空間埋め込み

(spatial embedding)

または空間グラフ

(spatial graph )

とは

, R

³ ^{に頂点を配置し}

,

それらを互いに交差しない曲線で結んで得られるグラフが

G

と同型であるものをいう

.

空間グラフにおける閉路は

R

³内の単純閉曲線として考えることができるので

,

空間グラフにおける閉路は結び目である

.

また

,

空間グラフの共通部分を持たないような閉路の和集合は絡み目である

.

定理

2.1

（

J. H. Conway and C. McA. Gordon [2], H. Sachs [12]

）

K

₆の

R

³への任意の埋め込みには必ず非自明な絡み目が含まれている

.

⊃ ∼ =

定理

2.2

（

J. H. Conway and C. McA. Gordon [2]

）

K

7の

R

³への任意の埋め込みには必ず非自明な結び目が含まれている

.

⊃ ∼ =

2.1 Intrinsically linked graph

と

intrinsically knotted graph

グラフ

G

が絡み目内在

(intrinsically linked )

であるとは

, G

の任意の埋め込みが分離不可能な

2

成分の絡み目を含む時をいう

.

また

G

が

n

成分絡み目内在

(intrinsically n-linked )

であるとは

, G

の任意の埋め込みが分離不可能な

n

成分の絡み目を含む時にいう

.

グラフ

G

が結び目内在

(intrinsically knotted )

とは

G

の任意の埋め込みが非自明な結び目を含む時を言う

.

定理

2.1, 2.2

により

K

6は絡み目内在

, K

7は結び目内在であることがわかる

.

どのようなグラフがこのような性質を持つのかということに興味がわく

. Y-∆

変形

, ∆-Y

変形とは図

3

のような変形のことである

.

これらの変形を

K

₆ に適用して得られるグラフ全体の集まりをペテルセン族

(Petersen family)

という

(

図

4).

図3 Y-∆^変形, ∆-Y^変形

2

(3)

図4 ^{ペテルセン族}

定理

2.3

（

N. Robertson, P. Seymour and R. Tomas [11]

）グラフ

G

が絡み目内在であるための必要十分条件は

, G

がペテルセン族のいずれかのグラフをマイナーとして含んでいることである

.

3 線形埋め込み

定理

2.1, 2.2

においてはどのように埋め込んでも非自明な結び目

(

絡み目

)

が存在することを示しているが

,

結び目

(

絡み目

)

の型については言及していない

.

では

, K

6 の埋め込みには

hopf link, K

7の埋め込みには

trefoil knot

が必ず含まれているとは言えるか

?

この問に対しての回答は一般には否定的である

.

一例としてグラフを埋め込む際に各辺に対して局所的な結

び目

(local knot)

ができるように埋め込むと埋めこまれた閉路の随所に

(

局所的な

)

結び目を持つので

, hopf

link

にも

trefoil knot

にも成り得ないのである

.

このような理由で一般的には特定の

knot (link) type

に対してはいえないことがわかる

.

しかし

,

グラフの埋め込みが局所的な結び目ができないような埋め込みに制限をすれば特定の型の

knot (link)

が含まれているかどうかを調べることができる

.

•

^{線形埋め込み}

(linear embedding)

グラフの各辺がちょうど一つの線分

(line segment )

となっているような

R

³ への埋め込みを線形埋め込みという

.

また

,

そのように埋め込まれたグラフは線形

(linear)

であるという

.

局所的な結び目を含む例線形埋め込みの例線形埋め込みでは実現できない例

3.1 Ramsey theorem for spatial graphs

定理

3.1

（

S. Negami [6]

）任意の結び目

K

に対して

,

次のような自然数

r

が存在する

.

すなわち

n ≥ r

に対して

,

完全グラフ

K

n の任意の線形埋め込みは

K

と同じ型をもつ

cycle

を含む

.

このような自然数

r

のうち

,

最少の数を

r(K)

で表す

.

定理

3.2

（

A. F. Brown [1], J. L. Ramirez Alfonsin [8]

）

K

7 の任意の線形埋め込みは

trefoil knot,

または

trefoil knot

の

mirror

と同じ型をもつ

cycle

を含む

.

この定理から

,

どんな

K

₇の線形埋め込みにも

trefoil knot

が含まれているので

r(trefoil knot) = 7

ということがわかる

.

さらに

, J. L. Ramirez Alfonsin

によって以下が示されている

.

3

(4)

定理

3.3

（

J. L. Ramirez Alfonsin [7]

）

r(4

²₁

) > 7 .

定理

3.4

（

J. L. Ramirez Alfonsin [9]

）

r(figure-eight), r(T(5,2)) ≥ 9 .

3.2 Polygonal index

線形埋め込みの時には

,

空間グラフは線分のみから構成されていて

,

空間グラフに含まれている結び目も線分で構成されている

,

そのように線分のみで構成されている結び目を

polygonal knot

という

.

ある結び目を表すために必要な線分の最小の数をその結び目の

polygonal index

と定義し

p(K)

で表す

. polygonal index

の定義から

p(K) ≤ r(K)

ということが分かる

.

定理

3.5

（

S. Negami [6]

）結び目

K

が自明な結び目でなければ

5 + √

25 + 8(c(K) − 2)

2 ≤ p(K) ≤ 2c(K)

が成り立つ

.

また

,

幾つかの結び目に対しての

polygonal index

が

R. Randell

によって示されている

.

定理

3.6

（

R. Randell [10]

）

p(trivial knot) = 3, p(trefoil knot) = 6, p(figure-8) = 7.

また

, crossing number c(K)

が

5

か

6

の素な結び目に対して

p(K) = 8.

それ以外の結び目に対して

p(K) ≥ 8.

定理

3.7

（

Y. Huh and C. B. Jeon [3]

）

K

₆ の線形埋め込みは高々一つの

trefoil knot

を含む

.

定理

3.8

（

Y. Huh and C. B. Jeon [3]

）

K

₆ の線形埋め込みが

trefoil knot

を含むならば

,

かつその時に限り

3

つの

Hopf link

を含む

.

上記の結果と定理

2.1

から

K

6 の線形埋め込みには次の

2

つに分類されることが分かった

.

• H opf link 1

つを含む埋め込み

,

• Hopf link 3

つと

trefoil knot 1

つを含む埋め込み

.

参考文献

[1] A.F. Brown, Embeddings of graphs inE³, Ph.D. Dissertation, Kent State University, 1977.

[2] J. H. Conway, C. McA. Gordon,Knots and links in spatial graphs, J. Graph Theory 7 (1983), 445-453.

[3] Y. Huh and C. B. Jeon,Knots and links in linear enbeddings of K6, J. Korean Math. Soc. 44 (2007), 661-671.

[4] Y. Huh,Heptagonal knots and radon partitions, J. Korean Math. Soc. 48 (2011), 367-382.

[5] M. Meissen, Edge number results for piecewise-linear knots, Knot theory (Warsaw, 1995), 235-242,Banach Center Publ., 42, Polish Acad. Sci., Warsaw, 1998.

[6] S. Negami,Ramsey theorems f or knots, links and spatial graphs, Trans. Amer. Math. Soc. 324 (1991) 527-541.

[7] J.L. Ramirez Alfonsin, On linked spatial representations, J. Knot Theory Ramifications 10 (2001) 143-150.

[8] J.L. Ramirez Alfonsin, Spatial graphs and oriented matroids: the Trefoil, Discrete Comput. Geom. 22(1999) 149-158.

[9] J.L. Ramirez Alfonsin,Spatial graphs, knots and the cyclic polytope, Beitr¨age zur Algebra und Geometrie Contri- butions to Algebra and Geometry Vol. 49, No. 2, pp. 301-314 (2008)

[10] R.Randell,Invariants of picewise−linear knots, Knot theory (Warsaw, 1995), 307-319,Banach Center Publ., 42, Polish Acad. Sci., Warsaw, 1998.

[11] N. Robertson, P. Seymour and R. Thomas, Sachs’ linkless embedding conjecture,J. Combin. Theory Ser. B64(1995) 185-277.

[12] H. Sachs, On a spatial analogue of Kuratowski s theorem on planar graphs-an open problem, Graph theory, in:M.

Borowiecki, J.W. Kennedy, M.M. Syslo (Eds.), Proceedings of the Conference in Memoriam K. Kuratowski, Lagow, Poland, 1981, Lecture Notes in Mathematics, vol. 1018, Springer, Berlin, Heidelberg, 1983, pp. 230-241.

4