Developing combinatorial theories for various geometric structures with topological representation theorems

点击翻译按钮获取中文摘要

本計画は，さまざまな幾何構造の組合せ的公理をトポロジー的表現定理とともに設計し，理解を深めていくことを目的としている．また，グラフ描画の研究も進めながら，組合せ構造の理解しやすい表現の構築を目指している．本年度得られた結果は以下の通りである．(1)申請者が以前，点とk次関数のグラフの配置の組合せ的抽象化として導入したk次有向マトロイドの公理が全く違う文脈で導入されたsigntopeと呼ばれる構造と一致することを前年度見出した．今年度は，その周辺をさらに調査し，いくつか新たな知見を得た．具体的には，k次有向マトロイドのトポロジー的表現として導入したk-交差擬点配置が，k=1とのとき，グラフ描画における擬線形x単調描画の定義を少し弱めたものに対応することがわかった．また，k=1の場合は，上記２つの概念どちらでもk次有向マトロイドが表現できるが，k>1の場合は，似たような結果が成り立たないことを示した．(2)以下のグラフの描画に関する研究をいくつか行った．１つに，学部学生との研究で，平面的グラフのなるべく最小角度をなるべく大きく描画することに関し，限界を示す新たな例を構成した．1990年代の結果で，どのような描画でも最小角度がO(\sqrt{\log d/d^2}) (d: グラフの最大次数)となってしまう例が知られているが，頂点数が3^d個程度の大きな例であった．本研究では，頂点数がd^2程度で同じ性質を持つ例を構成した．また，前年度に引き続き，大学院生とパスを凸に描画するグラフ描画の研究を行った．今年度はより扱いやすい定義を導入し，前年度の結果をより簡潔に示した．また，その概念を少し弱めた概念を導入し，その概念の下，任意の木が描画できることを示した．この結果はより深めたうえで，来年度結果を公表する予定である，