Organized study toward the solution of Planar Cover Conjecture

Negami是这个项目的首席研究员，他在1986年提出了一个猜想：如果一个连通图有一个有限的平面覆盖，那么它可以嵌入到射影平面中，世界上许多拓扑图理论家都支持他的猜想，称之为“平面覆盖猜想”。到目前为止，他们的研究得出结论：如果K_&lt；1，2，2，2&gt；没有有限平面覆盖，则猜想成立。然而，要证明这样一个图没有有限平面覆盖是非常困难的，因为它有无限多个覆盖，其中可能隐藏着一个有限平面覆盖。因此，我们试图建立一个确定是否存在有限平面覆盖所需搜索的覆盖个数的理论上界，以及一种有效地生成有限搜索空间的方法。为了生成搜索空间，我们建立了一个O(N)时间算法，在假设K_&lt；1，2，2&gt；的(n-1)重平面覆盖不存在的前提下，判断是否存在它的n重平面覆盖.然而，它的存储空间变得如此之大，以至于简单地在PC上实现的程序不能一致地运行。为了建立一个限定搜索空间大小的理论，我们讨论了足够大的平面覆盖将是合成的猜想，并发现这种情况经常发生，将我们关于合成覆盖的理论与群论中关于本原置换群的理论联系起来，这表明了图的有限群和Zeta函数的研究的效率，图的有限群和Zeta函数可以被视为图中圈的一种生成函数。此外，在这个项目的推动下，我们还可以在拓扑图论中的其他主题上建立许多定理。

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.