Developing combinatorial theories for various geometric structures with topological representation theorems

利用拓扑表示定理发展各种几何结构的组合理论

• 批准号: 19K20210
• 负责人: 宮田 洋行
• 金额: $ 1.75万
• 依托单位: Gunma University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19K20210/
• 关键词: 有向マトロイド; グラフ描画; 貪欲描画; 擬直線配置; トポロジー的表現定理

本計画は，さまざまな幾何構造の組合せ的公理をトポロジー的表現定理とともに設計し，理解を深めていくことを目的としている．また，グラフ描画の研究も進めながら，組合せ構造の理解しやすい表現の構築を目指している．本年度得られた結果は以下の通りである．(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程度で同じ性質を持つ例を構成した．また，前年度に引き続き，大学院生とパスを凸に描画するグラフ描画の研究を行った．今年度はより扱いやすい定義を導入し，前年度の結果をより簡潔に示した．また，その概念を少し弱めた概念を導入し，その概念の下，任意の木が描画できることを示した．この結果はより深めたうえで，来年度結果を公表する予定である，

This project aims to understand the axiom of geometric construction and the representation theorem of geometric construction. The study of composite structure, understanding of composite structure, construction of composite structure and its expression are discussed. This year's results are as follows. (1)The applicant has been abstracted and introduced into the k-th directional-oriented axiom of the previous year. The signtope has been introduced into the context of the previous year. This year, the investigation was conducted in the middle of the week, and new knowledge was obtained. Specific, k-th order directional-direction mapping of the performance and introduction of k-intersection mapping, k=1 and k=1, mapping of the quasi-linear x mapping of the definition of a small number of weak points. When k=1, the concept of 2 is recorded above. When k>1, the result of k>1 is shown. (2)The following is a new example of how to construct a plane with a minimum angle. In the 1990s, the result was a minimum angle.(\sqrt{\log d/d^2}) (d: maximum number of times of) In this study, the number of vertices is d^2, and the same property is formed. The previous year, the university students were invited to participate in the study. This year's results are presented concisely. The concept of "three" is introduced into the concept of "three", and the concept of "three" is drawn arbitrarily. The results of this year's event are set out below.

项目成果

The Dispersion Problem on Two Parallel Lines

两条平行线上的色散问题

• DOI: 10.14923/transfunj.2021jap1005
• 发表时间: 2022
• 期刊: 電子電子情報通信学会論文誌A 基礎・境界
• 作者: 田中 優輝;宮田 洋行;中野 眞一
• 通讯作者: 中野 眞一

平面グラフのトラック描画可能性判定問題の計算複雑度について

关于确定平面图上是否可以绘制轨迹问题的计算复杂度

• 发表时间: 2020
• 作者: 中島洸夢;宮田洋行;中野眞一
• 通讯作者: 中野眞一

Greedy描画可能な木の完全な組合せ的特徴づけ

贪婪可绘制树的完整组合表征

• 发表时间: 2021
• 作者: 野坂怜哉;宮田洋行;中野眞一
• 通讯作者: 中野眞一

Hiroyuki Miyata

宫田弘之

Dispersion on Intervals

区间离散度

• DOI: 10.1587/transfun.2021dmp0004
• 发表时间: 2022
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
• 作者: ARAKI Tetsuya;MIYATA Hiroyuki;NAKANO Shin-ichi
• 通讯作者: NAKANO Shin-ichi