位相幾何学的グラフ理論を用いたRyser予想の研究

利用拓扑图论研究Ryser猜想

基本信息

批准号：
21K13829
负责人：
大野由美子
金额：
$ 2.16万
依托单位：
Yokohama National University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Early-Career Scientists
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2026-03-31
项目状态：
未结题

项目摘要

本研究では、ハイパーグラフの最大マッチング数と最小頂点被覆数を、閉曲面上のグラフのface independence numberとguarding numberと呼ばれる不変量へそれぞれ翻訳し、位相幾何学的グラフ理論の知見を用いてRyser予想を解決することを目標としている。また、グラフの彩色を用いた観点からも研究を進めていく予定となっている。２０２２年度は主に（１）グラフの彩色に関する諸問題と、（２）特別なグラフクラスにおけるRyser予想に関連した問題について研究を進めた。（１）グラフの彩色に関しては、complete coloringと呼ばれる特別な彩色における予想が、キャタピラと呼ばれるグラフクラスにおいて成り立つことを示した。さらに、キャタピラでは、その予想よりも強い主張が成り立たない反例が見つかっておらず、その強い主張が成り立つのではないかと考え、研究を進めている。（２）Ryser予想はr-partiteという条件を満たすハイパーグラフの最小頂点被覆数が、最大マッチング数のr-1倍以下であるという予想であるが、球面上の偶三角形分割と呼ばれるグラフクラスにおいては、これらの値が等しくなり、Ryser予想よりも強い主張が成り立つのではないかと予想している。そこで、まずは球面上の偶三角形分割の中でも、四角形分割の面細分によって作られるグラフに対してこの予想が成り立つかどうかについて、考察を進めた。

在这项研究中，分别将最大匹配数和最小顶点覆盖了超图数的数量被翻译成称为面部独立数的不变性数量和封闭表面上的守卫图数，而目标是使用拓扑图理论的发现来求解雷目预测。此外，计划从使用图形着色的角度进行研究。在2022财政年度，我们主要对（1）与图形着色有关的问题以及（2）与特殊图类别中的Ryser预测有关的问题。（1）关于图形着色，我们已经表明，在称为Caterpillar的图类中，特殊着色的预测是正确的。此外，我们还没有找到比预期更强大的主张的反示例，而且我们正在继续研究，因为我们认为这种强有力的主张是正确的。（2）Ryser预测预测，满足条件R-Partite的高度图的最小顶点覆盖率小于最大匹配数的R-1倍，但是在绘图类别上称为偶数三角剖分的图类别中，这些值将是相等的，并且强烈的主张将比Ryser的预测更为。因此，我们首先讨论了该预测是否适用于矩形分裂的表面细分所产生的图，甚至在球形表面上甚至三角剖分中。