所員 -谷川 眞一-

名前 谷川 眞一 (Tanigawa, Shinichi)
助教
E-Mail tanigawa (emailアドレスには@kurims.kyoto-u.ac.jp をつけてください)
研究内容 離散数学・離散アルゴリズムの研究
紹 介
 離散幾何学における一研究課題であるグラフやリンケージの剛性に関してその組合せ的側面の研究を行なってきた。 ユークリッド空間内に埋め込まれたグラフの各辺を棒材,各頂点を節点と捉えることでグラフの局所剛性や大域剛性を定義することが出来る.一般的な埋め込みに対する剛性は一般剛性と呼ばれており,Asimov-Roth(1978)によって一般局所剛性が,Gortler-Healy-Thurston(2010)によって一般大域剛性がグラフの性質であることが示されている. 2次元の場合,Maxwellの条件によってグラフの一般局所剛性が組合せ的に特徴付けされることがLaman(1971)によって示されているが,3次元以上の場合においてはMaxwellの条件は十分ではなく,特に3次元一般剛性の組合せ的特徴付けは剛性理論における重要な未解決問題である.同様に大域剛性に対しては,2次元の場合Jackson-Jord{\'a}n(2005)によるConnelly予想の肯定的解決によって組合せ的特徴付けが与えられているが,3次元以上は未解決である. この一般剛性/大域剛性の組合せ的特徴付け問題を解決することを目標として,これまで幾つかの部分的成果をあげてきた。 また一般性の仮定が成立たない対称な埋め込みのリンケージに対する理論展開 や関連するアルゴリズム設計問題 に対しても一定の成果を得ている。
 TayとWhiteleyは,分子グラフと呼ばれる特殊なグラフクラスに対し Maxwellの条件が3次元一般剛性の必要十分条件であると予想した。 [1]では,この予想を肯定的に解決した。 この主張から導かれる高速かつ頑健な分子構造の自由度計算アルゴリズムは, 幾つかのタンパク質の挙動解析ソフトウェアに組み込まれており, 本結果はこれらの応用研究に対する理論的妥当性を与えている。
 論文[6]では,ユークリッド空間での剛性と球面上での剛性の等価性に着目し,$d$次元剛性と$d+1$次元剛性を補完する剛性概念を導入し,Lamanの2次元剛性定理の拡張を行った。 また論文[4]では,剛性判定問題と行列補完問題の類似性を利用して,行列補完問題の解の唯一性を解析し,組合せ的十分条件の導出を行った。
 [7,8,2]では ゼオライト等の結晶構造の振動や対称性の高いメカニズムに潜む組合せ的性質の解明に向け,既存の有限グラフに対する理論の拡張を行った。Malestein-TheranやRossは,周期グラフに対する群ラベル付き商グラフを考える事でLamanの2次元一般剛性定理を2次元周期グラフに拡張可能である事を証明している。 この成果に触発され[8]では, 群ラベル付き商グラフ上の新たなマトロイド構成法を構築し,既存の成果や幾つかの未解決問題がそのマトロイドの表現理論から従う事を示した。 また群ラベル付き商グラフの構築法による剛性解析手法の開発[2] や分子剛性定理の拡張に向けた取り組み[7]を行った。
 [9]ではグラフの大域剛性の組合せ的特徴付け問題に取り組み,大域剛グラフを逐次的に構成するための新たな手法を提案し,局所剛性に対する頂点冗長性が大域剛性の十分条件であることを証明した。またこの手法を利用することでJackson-Jordánの2次元大域剛性定理やFrank-Jiangの$k$-chainに関する大域剛性予想が容易に導かれる事を示した。 さらに論文[5]では,3次元大域剛性に関するConnelly予想の反例を与えた。我々の例は,剛体ヒンジ構造と呼ばれる構造モデルの大域剛性特徴づけから得られたものである。 Connelly-Jordán-Whiteley(2013)は剛体ヒンジ構造の大域剛性の十分条件を予想したが,その条件が実は必要十分で成立することを証明した。
  1. A proof of the molecular conjecture, Discrete Comput. Geom., 45 (2011), 647--700. (with N. Katoh)
  2. Infinitesimal rigidity of symmetric frameworks, (2013), arXiv1308.6380. (with B. Schulze)
  3. Linking rigid bodies symmetrically, Eur. J. Comb, 42 (2014) 145--166. (with B. Schulze)
  4. Combinatorial conditions for the unique completability of low rank matrices, SIAM J. Discrete Math., 28 (2014), 1797--1819. (with B. Jackson and T. Jordán)
  5. Generic global rigidity of body-hinge frameworks, EGRES Technical Reports, TR2014-06, (2014). (with T. Jordán and C. Király)
  6. Rigidity of frameworks on expanding sphere, arXiv:1501.01391, (2015). (with A. Nixon, B. Schulze and W. Whiteley)
  7. Periodic body-and-bar frameworks, SIAM J. Discrete Math. 29 (2015), 93-112. (with C. Borcea and I. Streinu)
  8. Matroids of gain graphs in applied discrete geometry, To appear in Trans. Amer. Math. Soc.
  9. Sufficient conditions for globally rigidity of graphs, To appear in J. Comb. Theory Ser. B.