Organized study toward the solution of Planar Cover Conjecture

组织研究解决平面覆盖猜想

• 批准号: 14340032
• 负责人: NEGAMI Seiya
• 金额: $ 5.44万
• 依托单位: Yokohama National University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-14340032/
• 关键词: topological graph theory; Planar Cover Conjecture; 1-2-∞ Conjecture; coverings of graphs; planarity of graphs; projective-planar graphs

Negami, the head investigator of this project, proposed in 1986 the conjecture that if a connected graph has a finite planar covering, then it can be embeddable in the projective plane and many topological graph theorists over the world support his conjecture, calling "Planar Cover Conjecture". Their studies up to the present conclude that if K_<1,2,2,2> has no finite planar coverings, the conjecture is true. However, it is so difficult to prove that such a graph has no finite planar covering since it has infinitely many coverings among which a finite planar one might hide. So we tried to establish a theoretical upper bound for the number of coverings which we should search to decide whether or not there exists a finite planar covering and a method to generate such a finite search space efficiently. Such a research strategy is called "finitizing Planar Cover Conjecture".For generating the search space, we established an O(n) time algorithm which decides whether or not there exists an n-fold planar covering of K_<1,2,2,2>, assuming the non-existence of its (n-1)-fold planar covering. However, its memory space becomes so big that a program simply implemented on PC would not run consistently. This suggests a future study on "designing a sustainable system" in an aspect of information sciences.To establish a theory to bound the size of search spaces, we have discussed it with a conjecture that sufficiently large planar coverings will be composite and found the fact that it happens very often, linking our theory on composite coverings and that on primitive permutation groups in group theory, which shows the efficiency of research on finite groups and zeta functions of graphs, which can be regarded as a kind of a generating function of cycles in graphs. Furthermore, we could establish many theorems on other topics in topological graph theory, being motivated by this project.

Negami是这个项目的主要研究者，他在1986年提出了一个猜想：如果一个连通图有一个有限的平面覆盖，那么它可以嵌入到射影平面中，世界上许多拓扑图论家都支持他的猜想，称之为“平面覆盖猜想”。到目前为止，他们的研究表明，如果K <1，2，2，2>没有有限平面覆盖，则猜想成立。然而，证明这样的图没有有限平面覆盖是非常困难的，因为它有无穷多个覆盖，其中可能隐藏着一个有限平面覆盖。因此我们试图建立一个理论上的覆盖数的上限，我们应该搜索，以决定是否存在一个有限的平面覆盖和方法，以产生这样一个有限的搜索空间有效。为了生成搜索空间，我们建立了一个O（n）时间的算法，在不存在K_<1，2，2，2>的n-1重平面覆盖的情况下，判定K_<1，2，2，2>是否存在n重平面覆盖。然而，它的内存空间变得如此之大，一个程序简单地在PC上实现将无法一致地运行。为了建立一个限定搜索空间大小的理论，我们讨论了一个猜想，即足够大的平面覆盖将是合成的，并发现它经常发生，将我们关于合成覆盖的理论与群论中关于本原置换群的理论联系起来，这表明了对有限群和图的zeta函数的研究是有效的，zeta函数可以看作是图中圈的一种生成函数。此外，我们可以建立许多定理的其他主题的拓扑图论，由这个项目的动机。

项目成果

Ore-type degree condition for heavy paths in weighted graphs

• DOI: 10.1016/j.disc.2005.06.006
• 发表时间: 2005-09
• 期刊: Discret. Math.
• 作者: H. Enomoto;J. Fujisawa;K. Ota

Bartholdi zeta functions of graph coverings

• DOI: 10.1016/s0095-8956(03)00043-1
• 发表时间: 2003-09
• 期刊: J. Comb. Theory B
• 作者: H. Mizuno;I. Sato

L-functions and the Selberg trace formulas for semiregular bipartite graphs

半正则二部图的 L 函数和 Selberg 迹公式

• 发表时间: 2003
• 期刊: Dynamical Sytems and Differential Equations (Wilmington NC, 2002), Discrete and Continuous Dynamical Systems
• 作者: H.Mizuno;I.Sato
• 通讯作者: I.Sato

Diagonal flips in Hamiltonian triangulations on the projective plane

射影平面上哈密顿三角剖分中的对角线翻转

• 发表时间: 2005
• 期刊: Discrete Math. 303 no.1-3
• 作者: Young-Bin Choe;Jin Ho Kwak;Yong Sung Park and Iwao Sato;Aiping Deng;Aiping Deng;Iwao Sato;Iwao Sato;Jin Ho Kwak;S. Negami;A. Nakamoto;I. Sato;Hideo Komuro;Atsuhiro Nakamoto;Jun Fujisawa and Katsuhiro Ota;Iwao Sato;Iwao Sato;Iwao Sato;Iwao Sato;Jin Ho Kwak and Iwao Sato;Iwao Sato;Iwao Sato and Jauen Lee;Iwao Sato;S.Fujita;J.fujisawa;H.Komuro;A.Nakamoto;I.Sato;I.Sato;Seiya Negami;Seiya Negami;Atsuhiro Nakamoto;Ryuichi Mori and Atsuhiro Nakamoto
• 通讯作者: Ryuichi Mori and Atsuhiro Nakamoto

Mizuno, Hirobumi: "L-functions for images of graph coverings by some operations"Discrete Math.. 256・1-2. 335-347 (2002)

Mizuno，Hirobumi：“通过某些操作实现图形覆盖图像的 L 函数”离散数学.. 256・1-2（2002）。