数理解析研究所講究録
第 1799 巻 2012 年 44-48

442011 年度冬の LA シンポジウム [8]合同な四角形による球面タイリングの分類
赤間陽二 *

中村 公亮 \d ag er

坂野 雄大 \dag er

平成 24 年 3 月 19 日

1

はじめに
球面タイリングは，世界で流行しつつある日本の伝統工芸である手毬の模様として見ることができる 1.
アルキメデス多面体・アルキメデスタイリングという名があるように，多面体や多角形によるタイリングの研究は 2000 年前に終わっていると考える人間もいる．しかし，決して狭く完結してはない．生体分子のみならず金属がつくるクラスタとしての離散幾何的構造は，研究が必要と思われる [13].

応用を研究している．彼らが開発したプログラム
plantri [5, 6] は球面の四角形分割 (すなわち球面に埋め込める graph で面が全て四角形であるもの) を列挙できる．第一著者は Brinkmam のグループを訪問し，冬の LA で発表した内容に以下の命題 1 を加えたものを ”Classification of spherical tilings bycongruent quadrangles” として 2 月 14 日に発表し，彼らと討論した．討論の内容と，彼らが開発したグラフ理論教育支援ソフトウェアについて報告し，合同な四角形による球面タイリングの分類に有用な予想

球面は定曲率の曲面の一つであり，その他の定曲 などを提示する．

率の曲面は，平面と双曲面である．それらの曲面の上での，合同な凸な多角形の辺に関してその多角形を折り返して，タイリングができるか否かは，単純逆数2条件として調べられている [Poincar\’e]. 平面的な 3連結なグラフの “convex embedding” がまた，定曲率の曲面のタイリング全てを表す Delaney-Dress 記

合同な四角形による球面タイリングの列挙戦略

球面の四角形分割の map を，Gunnar Brinkmann
Brendan McKay 2 らが開発したプログラム
著者は合同な四角形による球面タイリングの分類 plantri [6] で列挙する．プログラム plan-tri は，の研究を行っているが [1,2,3], 合同な凹な四角形に (合同な図形に埋め込めるという意味で) 同型なグラ
よる球面タイリングは直観に反するものがある [1,2] フを棄却する方法として，McKay の canonical conので，計算機で合同な凹な四角形による球面タイリ struction path method [14] ([12] では canonic 下 1 augングを列挙したい．
mentation と呼ばれている) を用いている 3.
ベルギーの Ghent 大学の Department of
彼らに著者の ”Classification of spherical tilings
plied Mathematics and Computer Science の Gun- by $\infty ngment$ quadrangles” を説明したところ，まず
nar Brinkmann のグループは，Australian National 定曲率の曲面のタイリング全てを表す Delaney-Dress
University の Research School of Computer Science 記号 [8,9,11] を紹介された．球面の時は若干取扱の Brendan McKay とともに化学へのグラフ理論の が特別になっている．Delaney-Dress 記号は，flag の号 [8,9,11] がある．と$A_{I\succ}$

東北大学大学院理学研究科数学専攻
国際協力機構東北大学理学研究科化学専攻
1 http: $//-.temari.\infty m$$*$$\dagger$$\downarrow$$R(4,5)=25$
2McKay は $B_{A}maey$ 数のいくつかを計算した．

[16], $R(3,8)=28[15]$ を証明した

3Brinkmaon によると，McKay の方法を特殊化したものが福田先生の逆探索法とのことである45
概念に基づいて辺に関する折り返しなどを群を用いて記述し，タイリングの対称型の議論がしやすいそうだ．

彼らは，合同な四角形による球面タイリングを列挙するにあたり，そのタイリングのグラフの次数の種類の個数があらかじめ分かっていれば効率的に列挙できる (表 1 参照) ことに注目した．
$]$$\vdash$1: 左の図は deltoidal hexecontahedron (風形六面体). 右の図はそのグラフ．

合同な四角形による球面タイリングにおける，次の種類の個数のみならず，タイルの内角とグラフ満らかじめ分かったとしても，合同な四角形によ$\lambda$$|$5 球面タイリングが一意に決まるわけではない (命$\underline{\ovalbox{\tt\small REJECT}}1)$

表 1: 球面の 4 角形分割の map を，異なる次数の個. とりあえずタイルを凸に限って議論していくべきと思われる．

数で分類した結果．表側は面数．表頭は異なる次数
1 題 1([2]) 6 以上の勝手な偶数 $F$ に対して $F$ 個のの掴数．Van Cloemput 氏による計算
ロ同な凹な四角形からなる球面タイリング乃， が7-在し， と乃は合同ではないが， のタイルのそこで第一著者は次を予想した:
角と乃のタイルの対応する内角は等しく， の予憩 1 合同な四角形による球面タイリングのグラフ グラフと乃のグラフも等しい．
$\infty$$T_{2}$$\uparrow$$\overline{\{}$$\neq$$T_{1}$$\hslash$$1$$T_{1}$$T_{1}$$d$においては，異なる次数の個数は高々 3 である．
彼らからの他の質問としてというは，タイルである球面四角形の 4 個の内角を未知変数とすると，四角形であるタイルの面積はそ 5 悶 1 合同な四角形による非対称的な球面タイリン?の内角の和から’.
を引いたものであるが，異なる次 グは存在するか数の個数だけ独立な方程式が得られる場合は，線形あった．彼らの質問の背景だが，四角形分割を列挙
代数の議論により，次数の個数は高々4 である．合同 するプログラム
plantri による列挙には，自明な自な菱型，合同な凧型，合同な矢じり型による球面タイ同型射しか持たないグラフが多く含まれるという$\xi$$2\pi$$j$$\hslash\grave$$\check{(}$$\Xi$$\zeta$

リングを網羅的に分類したところ [3], この予想は正しい 実際，位相的に deltoidal hexecontahedron(凧形六十面体) [7, Ch 21] である球面タイリングは次数3, 次数 4, 次数 5 の頂点からなる (図 1 参照).
この予想を 2 週間程度一緒に彼らと考えたが解けことである．
$($

合同な四角形による球面タイリングのグラフにおてにおいて，二個の隣接する面を一つの六角形となすと，球面の六角形分割が得られる．球面の四角 形分割の場合のように，球面のどんな六角形分割なかった．オイラーの法則から，4 角形による球面タも，基本的なグラフから有限個の局所的な拡張操作
イリングのグラフには必ず次数 3 の頂点があり，そより得られるとの結果が McKay の周辺から最近
い$l^{t}$$\ovalbox{\tt\smallREJECT}$$\mathfrak{k}$$f$$\dot{\eta}$$\ovalbox{\tt\small REJECT}|$ REJECT}_{\llcorner}^{\vee}$$\ovalbox{\tt\smallの頂点に集まる内角の最大値は $2\pi/3$ 以上で最小値5 表された．また日本のグラフ理論の専門家からの$\not\equiv\xi$は $2\pi/3$ 以下である．このような条件を線形計画法としてとらえると予想の解決に有用かもしれない．

g 献があったそうだ．この六角形分割の考え方によ$\Rightarrow$$\overline{\overline{\neq}}$$l$

Van Cleemput 氏は次を証明した．まず，合同な

46と辺の記号的長さ割り当てがきまる．すると，部分グラフたちの球面上での合同性が議論できる．結晶の点群を表すシェーンフリース記号を決めるように，最も回転対称性の高い軸を定める．ここで，Symmetryfinding [4] などのテクニックが使えるかもしれない．

その後に，球面三角法を用いて実際に球面タイリン

aaグとして実現できるかを見ることになる．

図 2:2 型の四角形 (左) と 4 型の四角形 (右)3グラフ理論教育支援ソフト
予想 1 を考えるのに，Brinkmann から有用かもしれないとすすめられたのがグラフ理論教育支援ソフ
トウェア GrinvIn (Graph Invariant Investigator,http: $//www$ .grinvin.org)[18] である．グラフ理論の教育ソフトおよび，論理推論の教育ソフトとして，Houston(米), Bielefeld(ドイツ), Ghent 大学 (ベルギー), Purderbourne 大学 (ドイツ) などで使われ，
図 3: abcd 型と abab 型の四角形が不可能な理由．

四角形による球面タイリングにおいては，タイルである四角形は，菱型，凧型，矢型，あるいは，図 2 の 2型 $(=aaab$ 型 , または 4 型 $(=abca$ 型 に限ること$)$$)$

学生にグラフ理論を紹介するに当たり非常に動機づけに成功し [17], UI や描画機能もよいので化学者も使っているそうである．Journal of MathematicalChemistry などにもグラフ理論の論文が掲載される．
Mohar index, 細矢治夫先生の Hosoya index [10] な
ど様々な index が提唱されているが，化学でも利用さに注意する．つまり，タイルは長さが abcd の四角形れているそうである．GrinvIn はベルギーの Ghent
ではありえないし，長さが abab の四角形ではありえ
大学の Brinkmam と Van Cleemput らが中心となっない(図 3 参照).て開発されている．

GrinvIn の使い方であるが，グラフの不変量 (頂点Lemma 1 ([19]) 2 型の合同な四角形による球面タ
イリングにおいて，少なくとも 6 個の頂点が丁度 2 数，辺数，面数，直径，マッチング数，．．．) を 2 個以上選び，典型的なグラフのクラスから適当なグラフを個の長さ の辺に接続する．
選ぶ．すると，システムは不変量の表を適当にフィッ$a$Lemma 2 $([19|)4$ 型の合同な四角形による球面タティングした数式を「予想」として表示する．ユー

イリングにおいて，少なくとも 6 個の頂点が丁度 2 ザーはその反例であるグラフを選ぶかエディタで入個の，長さが でない辺に接続する．
力するか，あるいは，それを証明する．ユーザーであ$b$Lemma 3([19]) 4 型の合同な四角形による球面タイリングにおいて，少なくとも 6 個の頂点が丁度 2個の，長さが C でない辺に接続する．
合同な四角形による球面タイリングの分類の戦略としては，まず，記号的な角度割り当て決める．する

る学生は，先生も解決が困難な予想に挑むこともあるそうである．

47
4

おわりに

[8] A. W. M. Dress. Presentations of discretegroups, acting on simply connected manifolds.
Advances in Mathematics, Vol. 63, pp. 196212, 1987. This paper contains the formal
definitions and proofs regarding Delaney-Dresssymbols.

日本は世界最速の列挙プログラムを開発し (有村先生，上野先生，中野先生), また，多面体展開図の列
挙 (堀山先生) や折り紙関係の列挙に関する研究 (上原先生) があるので，諸賢の結果を踏まえて，研究を進めていきたい．

参考文献[9] A. W. M. Dress and D. H. Huson. On tilings ofthe plane. Geometriae Dedicata, Vol. 24, pp.
269-296, 1987.

[1] Yohji Akama. Classification of spherical tilings
by congruent quadrangles over pseudo-double
wheels $(I)-a$ special tiling by congruent concave quadrangles. Hiroshima Math. J., Vol. xx,No. , pp. xxx-xxx, 2012.

[[10]Haruo Hosoya. Topological index. a newly proposed quantity characterizing the topologicalnature of structural isomers of saturated hydrocarbons. Bulletin of the Chemical Societyof Japan, Vol. 44, No. 9, pp. 2332-2339, 1971.

$x$doi: 10. $1246/bcsj$ . 44.2332.

[2] Yohji Akama, Kosuke Nakamura, and Yudai

Sakano. On spherical tilings by congruent
quadrangles (II) –the continua and the symmetries. 2011.
[3] Yohji Akama and Yudai Sakano. Classificationof spherical tihngs by congruent rhombi (kites,darts). in preparation, 2012.

.
[11]D. H. Huson. The generation and classification of tile-k-transitive tilings on the euclidean
plane, sphere, and hyperbolic plane. Geometriae Dedicata, Vol. 47, pp. 295-310, 1993.
$[^{1}$[12] P. Kaski and P. R. J. Ostergard. Classification
Algorithms for Codes and Designs. Springer,$[\lrcorner$

2006.

[4] M. J. Atallah. On symmetry detection. IEEE

Trans. Comput., Vol. 34, pp. 663-666, 1985.
[5] G. Brinkmann and B. D. McKay. Fast generation of planar graphs. MATCH Commun.
Math. Comput. Chem., Vol. 58, pp. 323-357,2007.
[6] Gunnar Brinkmann, Sam Greenberg, Catherine Greenhill, Brendan D. McKay, Robin
Thomas, and Paul Wollan. Generation of simple quadrangulations of the sphere. Discrete
Math., Vol. 305, No. 1-3, pp. 33-54, 2005.

[7] John H. Conway, Heidi Burgiel, and Chaim

Goodman-Strauss. The symmetmes of things.
A K Peters Ltd., Wellesley, MA, 2008.

13] Leonard R. MacGillivray. Design rules: A netand archimedean polyhedra score big for selfassembly. Angewandte Chemie Intemational
Edition, Vol. 51, No. 5, pp. 1110-1112, 2012.

$|]$[114] B. D. McKay. Isomorph-free exhaustive generation. J. A lgorithms, Vol. 26, pp. 306-324,

1998.
[115] B. D. McKay and Zhang Ke. The value of$R(3,8)$
the Ramsey number. J. Graph Theory,
Vol. 16, pp. 99-105, 1992.
${\rm Min}$[116] Brendan D. McKay and Stanislaw P. Radziszowski. $R(4,5)=25$ . Joumal of Grvrph Theory, pp. 309-322, 1995.

48[17] Adriaan Peeters, Kris Coolsaet, Gunnar
Brinkmann, Nicolas Van Cleemput, and Veerle
Fack. Grinvin for graph theory teaching andresearch. In Johann Hurink, Walter Kern, Gerhard F. Post, and Georg Still, editors, $CTW$,
pp. 123-126. University of Twente, 2007.
[18] Adriaan Peeters, Kris Coolsaet, Gunnar
Brinkmann, Nicolas Van Cleemput, and Veerle
Fack. Grinvin in a nutshell. Joumal of Mathematical Chemistry) Vol. 45, pp. 471-477, 2009.
10. 1007/sl09lO-008-9420-5.
[19] Nicholas van Cleemput. personal communication, 15 Feb. 2012.