ぱらぱらめくる『LinKnot Knot Theory by Computer』 - ryamadaのコンピュータ・数学メモ

結び目理論の計算機的扱い
Mathematicaのアドオンパッケージとして公開されている内容らしい
結び目を計算機が扱う方法について詳述していると思われる

LinKnot: Knot Theory by Computer (Series on Knots and Everything)

作者:Jablan, Slavik V.,Sazdanovic, Radmila
発売日: 2007/11/16
メディア: ハードカバー

目次
- 1. Notation of Knots and Links
- 2. recognition and Generation of Knots and Links
- 3. History of Knot Theory and Applications of Knots and Links
細目次
- 1. Notation of Knots and Links
  - 1.1 Basic graph theory
  - 1.2 Shadows of KLs (KLs = Knots and Links)
  - 1.3 KL diagrams
  - 1.4 Reidmeister moves
  - 1.5 Conway notation
  - 1.6 Classification of KLs
  - 1.7 LinKnot functions and KL notation
  - 1.8 Rational World and KL invariants
  - 1.9 Unlinking number and unlinking gap
  - 1.10 Prime and composite KLs
  - 1.11 Non-invertible KLs
  - 1.12 Reduction of R-tangles
  - 1.13 Braids
  - 1.14 Braid family representatives
  - 1.15 More KL invariants
  - 1.16 Borromean links
- 2. Recognition and Generation of Knots and Links
  - 2.1 Recognition of KLs
  - 2.2 Polynomial invariants
  - 2.3 Vassiliev invariants
  - 2.4 Experimenting with KLs
  - 2.5 Derivation and classification of KLs
  - 2.6 Basic polyhedra and polyhedral KLs
  - 2.7 Basic polyhedra and non-algebraic tangles
  - 2.8 KL tables
  - 2.9 Projections of KLs and chirality
  - 2.10 Families of undetectable KLs
  - 2.11 A dream --- new KL tables
- 3. History of Knot Theory and Applications of Knots and Links
  - 3.1 History of knot theory
  - 3.2 Mirror curves
  - 3.3 KLs and fullerenes
  - 3.4 KLs and logic
  - 3.5 Waveforms
  - 3.6 Knot automata
1.1 Basic graph theory
- 平面グラフが対象になる
- Embedding adjacency matrixという表現がある。平面グラフの頂点にIDを付与したとき、各頂点につき、接続頂点集合を時計回り・反時計回りのどちらかに固定して、巡回する(どの頂点から巡回を始めても同じとみなす)こととする。例えば、頂点 i が、頂点 j1,j2,j3,j4の４頂点にその順で接続しているとき、{ {i,j1,j2,j3,j4 }, { ... }, { ... } , ... , {...} } のように記す、ただし、{i,j1,j2,j3,j4} と {i,j3,j4,j1,j2} とは同一視される。これをembedding adjacency listと呼び、それをmatrix仕立てにしたものがembedding adjacency matrix
- 3-dimensional convex drawings of 3-connected planar graphs等、planar graphの2次元埋め込み方法や、グラフがplanarかどうかの判定法には理論・アルゴリズムなどがあり、LinKnotではそれらを実装した関数がある
- 平面、球面だけでなく、向き付け可能面(トーラスとか)へのembeddingも扱える
1.2 Shadows of KLs (KLs = Knots and Links)
- KnotとLinkの定義
- 集合と位相空間の定義、位相同型の定義、そして埋め込みの定義
- 2つのknots(もしくはlinks)のambient-isotopicな関係を、２つの実三次元空間とを滑らかにつなげることと定義
- TameなKLsはpolygonal (有限個の直線成分の連結とみなせる)と言う。それらは滑らかなカーブとして扱える
- KLsは2次元空間に写像できる。regularな写像(KLsの位相具合を表しつつ、それに不要な重なりがないような像)は4-正則グラフになる。2次元空間へのregularな写像において、グラフ交点になったところを、3次元空間に逆写像すると、3次元空間では2点に対応する
- Component algorithmというのがある。4-正則グラフの辺を一つ取り、その終点に接続する、残りの３辺のうち、中央に来る辺を選ぶことにする。そうすると必ず最初の辺の始点に戻ってくる。この閉路がLinkの構成Knotの1つに相当する。まだ通過されていない辺があれば、そのような辺のひとつをとり、同じことを繰り返す。これにより、Knotsの個数がわかる。これをComponent number of Linkと言い、KLの不変量の一つである
- Component numberはKLsの分類に標準的に使われる不変量だそうだが、この本では、component numberによらないKLsの特徴を扱いたいとのこと。component numberによらない特徴量に何かしら重要な特性があるからと言うことなのだろう
- Component algorithmにより、訪れる頂点ID順列の集合を作ることができる。これをガウスコードという
- n頂点、j components のLinkに附番してi番目に登録されているとき $n_i^j$ と書くことがある。 $j=1$ ではjを省略することもある。Alexander-Briggs 記法という
- 4-正則グラフなので、Embedding adjacency list では、要素数５(自身と接続４頂点の併せて５個)の部分集合を要素とする集合となり、それからガウスコードが導ける
- ガウスコードでは、サイクル上に同じノードIDが連続していると、そこにループ(ノードから出て自身に戻るエッジ)があることになる。そのようなループが無いように記載したガウスコードはproperであると言われる
- ガウスコードから、さらに省略したDowker コードというものが作れる
  - 具体例の説明を先にする
  - Knotのガウスコードが{1,2,4,3,2,1,3,4}とする。1,2,3,4は頂点ID
  - 各頂点が２回、通過されるから、のべ８個の数値が並ぶ
  - その順番を(1,2,3,4,5,6,7,8)とする
  - 頂点IDのそれぞれが、何番目かを、確認すると、頂点１は(1,6)、頂点２は(2,5)、頂点3は(4,7)、頂点4は(3,8)
  - 理由があって、頂点ごとの順序数のペアは奇数と偶数のペアになる。このペアを、(奇,偶数)とすれば、1:(1,6),2(5,2),3(7,4),4:(3,8)となる
  - このペアを奇数の方の順序数の順に並べ替えると、1(1,6), 4(3,8), 2(5,2), 3(7,4) となる。順序数の順に並べ替えているので、奇数の値1,3,5,7の順は、1-8の順番の１つ飛ばしの順に並んでいる
  - (1,3,5,7)と言う４つの奇数が、順序正しく並んでいることは「わかって」いるから、省略すれば、1(*,6), 4(*,8), 2(*,2), 3(*,4) となる
  - 今、頂点のIDがなんであるかについては、興味がなく、４つの交点が、どういう順番で通過されるかのみが、興味の対象なので、(*,6),(*,8),(*,2),(*,4)としてもKnot情報としては十分
  - さらに * はなくても「わかって」いるから、(6,8,2,4)としても、情報は失われない
  - 交点数4があるのは、便利なので {{4},{6,8,2,4}}と表記することにする。ここから、(1,6), (3,8), (5,2), (7,4) は復元でき、それによってKnotを描くことが可能である
  - したがって{{4},{6,8,2,4}}はKnotの記法として成立する。これはDowker コードと呼ぶ
- DowkerコードのLinkへの拡張
  - Linkでは、複数のcomponent knotsのそれぞれがガウスコードで表記される
  - 頂点IDはどのcomponent knotに現れるかは様々だが、全部のKnotsについて数え上げても２回しか登場しないルールがある
  - 例えば、あるLinkが{{1,2,4,5},{1,6,4,3},{2,6,5,3}}と書かれているとする
  - 確かに、1,2,...,6のそれぞれが2回ずつ出ている
  - これを、componentsをまたいで、1,2,3,4,...,12と順番を付けることを考える
  - このままだと、例えば、頂点ID 1 の順序数は{1,5}となる
  - 奇数が２つ。KnotのDowkerコード作成では、すべての頂点IDの順序数が、偶奇ペアになっていた
  - 個々のKnotのガウスコードは始点をずらしても変わらないから、偶奇となるように、componentの構成頂点IDの順序をずらすこととする
  - {{1,2,4,5},{3,1,6,4},{2,6,5,3}}。これだと、1,2,3,4,5,6のすべてについて、偶奇となっている
  - 1:(1,6), 2:(2,9), 3:(5,12), 4:(3,8), 5:(4,11), 6:(7,10)
  - 確かに、偶奇
  - これを用いて{6,8,12,10,2,4)という偶数列ができる。３つのKnotsの長さ情報は、それぞれのcomponent ガウスコードの数値数の半分だから、この例では、３つの2が得られ、結局、{{2,2,2},{6,8,12,10,2,4}}となる
  - Dowkerコードでは、偶数列を使うが、実際には、「偶数列」であることがわかっているのなら、その半分の値の列から作成可能なので、{6,8,12,10,2,4}は{3,4,6,5,1,2}としてコーディングしても良いだろう
  - ちなみに、ガウスコードに戻した時に、同一の頂点IDの連続が起きるのは、この、偶数列を半分にした順列に置いて、i番目にiがなく、i+1番目にもiがない、という条件が必要となる
  - この条件を使うと、{s1,s2,s3}という順列をこの条件を満足するように作るには、最初の値は1ではいけないし、最大数の3でもいけないから、2と確定し、同様にして、結局、{2,3,1}しかありえないことがわかる。この非偶数Dowkerコードから、偶数Dowkerコードを復元すると、{4,6,2}となり、{{1,4},{3,6},{5,2}}という３頂点を二回ずつ通る順番情報が復元される。頂点IDを順序よくつければ、{1:(1,4),2:{3,6},3:{5,2}}となる。ここからガウスコードを復元すれば、{{1,3,2,1,3,2}}ができる。確かに、同じ頂点IDの連続がない３つの数値が二回ずつ登場した数列ができた。これは三葉結び目
  - もう１点、確認しておく。ガウスコードで、頂点IDの登場順序番号が偶奇１つずつになるように整えたものが与えられたとする。これが、一つのKnotなのか、３つのKnotsからできたLinkなのかは、これだけでは決まらない。{{1,2,4,5},{3,1,6,4},{2,6,5,3}}と書けば、３つのKnotsでできたLinkであるし、{{1,2,4,5,3,1,6,4,2,6,5,3}}と書けば、1つのKnotとなる。この２通りのKLsは、Dowkerコード的にはどちらも{6,8,12,10,2}を持ち、{{2,2,2},{6,8,12,10,2}}と{{6},{6,8,12,10,2}}との違いに対応する。{6,8,12,10,2}の方がもつ情報は、６つのペアという置換情報*1に対応し、{{6},...}と{{2,2,2},...}の方は、置換で言えば、*2という置換か、*3という置換かに対応する情報を提供しているという違いであることに気づく。また、複数のKnotsに分ける場合には、Knotsの分け目に置いては、ガウスコードで、同一の頂点IDが並んでも良いことは、１つのKnotに対応するガウスコードのルールとの違いになる。他方、Linkのガウスコードでは、Knotsの分け目に現れる頂点IDは、それぞれのKnotの別の端点IDと同一ではいけないというルールが発生していることに注意する
  - 順列でDowkerコード様のものを作ったとして、かならずしも、平面グラフならないとか、平面グラフにはなるが、球面上に実現できない(トーラス上に実現される)といった理由で、球面展開を前提にしたときには実現不可能なLKsが含まれる。トーラス等の上に実現されるリンクをvirtual linkと称する
  - 球面上実現可能性をチェックするアルゴリズムにDowker-Thistlethwaite アルゴリズムと言うものがある
1.3 KL diagrams
- キラリティというのがある。二次元平面に射影して4正則グラフにしたとしても、交叉点でどちらが上でどちらが下かの情報をなくしてしまっては、KLsの情報として十全ではない。どちらが上か下かを区別する記法もある。数値の下・上にバーをつける。2次元平面像を上から眺めるか、下にもぐって見上げるかによって、上下情報は反転する。それを鏡像と言う。鏡像がLK的に同一になるかならないかにより、そのKLsがキラルかアキラルかと区別する。下バー、上バーは、ガウスコード(頂点ID)にもつけるし、ガウスコードから得られる順序数にもバーをつけ、それをDowkerコードにも反映する
- Alternating and non-alternating KLs. Alternating KLsとは、紐が交叉するときに、上下・上下と交互になるもの。Non-alternatingはそうではないもの。上下バーつきのDowkerコードでは、Alternating KLsの場合、バーが上ばかり・下ばかりになる。そうならないのはNon-alternating
  - 上下通過情報については、Alternatingを基準とし、そのパターンからずれた交点に対応する数値に印をつける(負の数にするなど)と、Dowkerコードが簡略化される。もしalternatingなら印つきの数値はなし。ただし、これにより、鏡像の区別はできなくなる(alternatingには２パターンあって、全上バーか全下バーかの２通りあるが、alternatingからのずれだけを記録すると、全上バーと全下バーとのどちらを基準にしたものかは判別不能だから
  - これをDTコード(Dowker-Thistlethwaiteコード)と呼ぶ
- 紛らわしいことに、符号付Dowkerコードというのが別にある。これは、リンクの構成Knotsにそれぞれ向きをつけたときに登場する。ある紐が別の紐をくぐるとき、くぐられる紐が南から北に向かうと固定して考えた時、くぐり方は東から西向きか、西から東向きかの二通りある。この２つの向きを符号で区別したものが、符号付Dowkerコード。この違いが効いてくるのは、primeではないKLs。逆に言うとprimeなKLsでは、DTコード記載によって、向きアリLinkの符号識別問題は生じないことが知られている。ちなみに、Primeである、とは、KLsがat least 3-edge connected であるようなものを二次元平面に写像したもののこと。2-edge connectedとは、唇みたいな部分のこと(らしい)
  - この符号から得られる向き付きKLsの埋め込みの不変量をwrithe 不変量と言う(writhe:のたうち回る)。KLsの部分をくるりとひっくり返したりすることによって符号が変わることから(Writheは向き付きKLsの埋め込みが持つ不変量であって、KLs自体の不変量ではないそうだ)
- 向き付きLinksには別の不変量 Linking numberというのがある
- P-dataという情報の持ち方もある。Dowkerコードと基本的には同じという
- 記法の最小情報化。同じKLsに複数のDowkerコードが対応するので、何かルールを入れて、簡単に記録したいし、「簡単に」記録できるということは、記法表現が違うと「簡単さ」に大小があるということになる。置換・順列を互換の積とすれば、それが小さいことが「簡単」の定義とできる。そのうえで、Linksの場合には、構成Knotsを短い順に重視するなどの順序を入れることで、「最も簡潔な記法(のうちの一つ)」を与えることが可能となる

*1:1,6),(3,8),(5,12),(7,10),(9,2),(11,4

*2:1,2,3,4,5,6,7,8,9,10,11,12

*3:1,2,3,4),(5,6,7,8),(9,10,11,12