所員 -谷川 眞一-

名前 谷川 眞一 (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]では,この予想を肯定的に解決した。 この主張から導かれる高速かつ頑健な分子構造の自由度計算アルゴリズムは, 幾つかのタンパク質の挙動解析ソフトウェアに組み込まれており, 本結果はこれらの応用研究に対する理論的妥当性を与えている。
 [4]ではグラフの大域剛性の組合せ的特徴付け問題に取り組み,大域剛グラフを逐次的に構成するための新たな手法を提案し,局所剛性に対する頂点冗長性が大域剛性の十分条件であることを証明した。またこの手法を利用することでJackson-Jordánの 2次元大域剛性定理やFrank-Jiangのk-chainに関する大域剛性予想が容易に導かれる事を示した。 さらに論文[5]では,3次元大域剛性に関するConnelly予想の反例を与えた。我々の例は,剛体ヒンジ構造と呼ばれる構造モデルの大域剛性特徴づけから得られたものである。 Connelly-Jordán-Whiteley(2013)は剛体ヒンジ構造の大域剛性の十分条件を予想したが,その条件が実は必要十分で成立することを証明した。
 [2,3,9,6]では ゼオライト等の結晶構造の振動や対称性の高いメカニズムに潜む組合せ的性質の解明に向け,既存の有限グラフに対する理論の拡張を行った。Malestein-TheranやRossは,周期グラフに対する群ラベル付き商グラフを考える事でLamanの2次元一般剛性定理を2次元周期グラフに拡張可能である事を証明している。この成果に触発され [3,9]では, 群ラベル付き商グラフ上の新たなマトロイド構成法を構築し,既存の成果や幾つかの未解決問題がそのマトロイドの表現理論から従う事を示した。
 論文[8]では,ユークリッド空間と球面空間での剛性の等価性に着目し,$d$次元剛性と$d+1$次元剛性を補完する剛性概念を導入し,Lamanの2次元剛性定理の拡張を行った。 また論文[7]では,剛性判定問題と行列補完問題の類似性を利用して,階数制限付き行列補完問題の解の唯一性を解析し,組合せ的十分条件の導出を行った。
 論文[10]では,行列補完問題の解空間の構造を解析した。距離多面体の面構造と最大階数補完・最小階数補完の関係を明らかにした。さらに行列補完問題の解の唯一性と球面空間での剛性の関係から,odd-$K_4$をマイナーとして含まない球テンセグリティ構造の普遍剛性の特徴づけを導いた。さらにConnelly-Gortler(2015)によって指摘された普遍剛性の特徴づけと半正定値計画問題の面的縮小法の関係に着目し,論文[11]では行列補完問題における面的縮小回数の組合せ的特徴づけを行った。
  1. A proof of the molecular conjecture, Discrete Comput. Geom., 45 (2011), 647--700. (with N. Katoh)
  2. Infinitesimal rigidity of symmetric frameworks, SIAM J. Discrete Math., 29 (2015), 1259--1286. (with B. Schulze)
  3. Matroids of gain graphs in applied discrete geometry, Trans. Amer. Math. Soc., 367 (2015), 8597--8641.
  4. Sufficient conditions for globally rigidity of graphs, J. Comb. Theory Ser. B, 113 (2015), 123--140.
  5. Generic global rigidity of body-hinge frameworks, J. Comb. Theory Ser. B, 117 (2016), 59--76. (with T. Jordán and C. Király)
  6. Gain-sparsity and symmetry-forced rigidity in the plane. Discrete Comput. Geom., 55 (2016), 314--372. (with T. Jordán and V. Kaszanitzky)
  7. Unique low rank completability of partially filled matrices, EGRES Technical Reports, TR-2015-08, (2015) (with B. Jackson and T. Jordán)
  8. Rigidity of frameworks on expanding sphere, arXiv:1501.01391, (2015). (with A. Nixon, B. Schulze and W. Whiteley)
  9. Count matroids of group-labeled graphs, arXiv:1507.01259, (2015) (with Rintaro Ikeshita)
  10. The signed positive semidefinite matrix completion problem for odd-$K_4$ minor free signed graphs, arXiv:1603.08370, (2016)
  11. Singularity degree of the positive semidefinite matrix completion problem, arXiv:1603.09586, (2016)