所員 -谷川 眞一-

名前 谷川 眞一 (Tanigawa, Shinichi)
助教
E-Mail tanigawa (emailアドレスには@kurims.kyoto-u.ac.jp をつけてください)
研究内容 離散数学・離散アルゴリズムの研究
紹 介
 離散幾何学の一分野である剛性理論の研究を行なっている。 ユークリッド空間内に埋め込まれたグラフの各辺を棒材, 各頂点をジョイントと捉えることでグラフの剛性を定義することが出来る。 点配置の一般性を仮定した場合の剛性は一般剛性と呼ばれており,一般剛性はグラフの性質である。 この一般剛性の組合せ的特徴付けを与えることが研究課題である。 1次元の場合,一般剛性とグラフの連結性の等価性は自明であり, 2次元一般剛性に対してはMaxwellの条件が必要十分であることがLamanによって証明されている。 しかしながら3次元以上ではMaxwellの条件は十分でなく, 特に3次元一般剛性の組合せ的特徴付けは重要な未解決問題である。 この問題の解決に向け,逐次的構築法[1],Dilworth打切り[2], グラフの木分割[5]等を用いた様々な試みを提案している。
 TayとWhiteleyは,分子グラフと呼ばれる特殊なグラフクラスに対し Maxwellの条件が3次元一般剛性の必要十分条件であると予想した。 [1]では,この予想を肯定的に解決した。 この主張から導かれる高速かつ頑健な分子構造の自由度計算アルゴリズムは, 幾つかのタンパク質の挙動解析ソフトウェアに組み込まれており, 本結果はこれらの応用研究に対する理論的妥当性を与えている。
 2次元一般剛性は交叉劣モジュラ関数の理論によってその組合せ構造が完全に理解されることがLovász-Yeminiによって明らかにされていた。 この事実に基づき[2]では, マトロイド合併とDilworth打切りの線形表現理論を利用した3次元剛性の解析法を提案した。 また[5]では,頂点上にマトロイド制約を付加した 一般化木分割問題に対し Tutte-Nash-Williamsの木詰込み定理の拡張を証明し,一般化木詰込み定理を利用したグラフの剛性解析手法を提案した。
 [3,4,6,7]では ゼオライト等の結晶構造の振動や対称性の高いメカニズムに潜む組合せ的性質の解明に向け,既存の有限グラフに対する理論の拡張を行った。Malestein-TheranやRossは,周期グラフに対する群ラベル付き商グラフを考える事でLamanの2次元一般剛性定理を2次元周期グラフに拡張可能である事を証明している。 この成果に触発され[6]では, 群ラベル付き商グラフ上の新たなマトロイド構成法を構築し,既存の成果や幾つかの未解決問題がそのマトロイドの表現理論から従う事を示した。 また群ラベル付き商グラフの構築法による剛性解析手法の開発[4,7] や分子剛性定理の拡張に向けた取り組み[3]を行った。
 [8]では剛性理論における主要課題の一つであるグラフの大域剛性の組合せ的特徴付け問題に取り組んだ。 大域剛性判定のための新たな手法を提案し, Jackson-Jordánの2次元大域剛性定理やFrank-Jiangの$k$-chainの大域剛性予想が容易に導かれる事を示した。
  1. A proof of the molecular conjecture. Discrete Comput. Geom., 45 (2011), 647--700. (with N. Katoh)
  2. Generic rigidity matroids with Dilworth truncations. SIAM J. Discrete Math., 26 (2012), 1412--1439.
  3. Periodic body-and-bar frameworks. Proc. 28th ACM Symposium on Computational Geometry, (2012), 347--356. (with C. Borcea and I. Streinu)
  4. Gain-sparsity and symmetry-forced rigidity in the plane. The EGRES technical report, TR-2012-17 (2012). (with T. Jordán and V.Kaszanitzky)
  5. Rooted-tree decompositions with matroid constraints and the infinitesimal rigidity of frameworks with boundaries. SIAM J. Discrete Math., 27 (2013) 155--185. (with N. Katoh)
  6. Matroids of gain graphs in applied discrete geometry. To appear in Trans. Amer. Math. Soc.
  7. Infinitesimal rigidity of symmetric frameworks, (2013), arXiv1308.6380. (with B. Schulze)
  8. Sufficient conditions for globally rigidity of graphs, (2014), arXiv:1403.3742.