Problems in Graph Structure Theory

Robertson 9701317该奖项将提供资金开发与图次关系相关的结构图论中的几个项目。大部分工作涉及与保罗·西摩、罗宾·托马斯和其他人正在进行的联合项目;以及由首席研究员监督的研究生研究。本提案的主要议题概述如下。这些主题涵盖了图结构理论的很大一部分，因为它涉及到图的次要包含关系。事实上，每个主题都包含重大问题，这些问题往往是众所周知的和困难的，因此在任何方向取得重大进展都可能占用大量时间。目前有严重的攻击（我们组欢迎）正在作出许多这些问题的其他地方的图论界。主要内容如下：（1）继续研究显式有限图次结构中的公开问题。(2)继续对一般有限图子结构中的开放问题进行研究。(3)利用改进的四色定理证明和结构论结果解决着色问题。(4)继续研究柏拉图立体图和环形正则格图所显示的层次上的连通性;特别是在给定层次上的子项链或子项类型。(5)通过研究曲面上的非平凡闭曲线如何与嵌入图相交的问题，继续深化曲面嵌入结构理论。(6)将图子式理论推广到二元拟阵。(7)探讨算法图论和拟阵理论中的一些问题。这项研究是在组合数学的一般领域。组合数学的目标之一是找到有效的方法来研究如何安排对象的离散集合。离散系统的行为对现代通信极为重要。例如，大型网络的设计，如电话系统中出现的网络，以及计算机科学中算法的设计，都要处理离散的对象集，这就需要使用组合研究。

Robertson 9701317 This award will provide funds to develop several projects in structural graph theory associated with the graph minor relation. Much of the work involves ongoing joint projects with Paul Seymour, Robin Thomas and others; and the research of graduate students supervised by the principal investigator. The main topics of this proposal are summarized below. These topics cover a large part of graph structure theory as it relates to the graph minor inclusion relation. In fact, each topic contains major problems, often well known and difficult, and so significant progress in any direction is likely to absorb a great deal of time. There are at present serious attacks (which our group welcomes) being made on many of these problems elsewhere in the graph theoretical community. The main topics are as follows: (1) To continue the attack on the open problems in explicit finite graph minor structure. (2) To continue the attack on the open problems in general finite graph minor structure. (3) To attack coloring problems made accessible by the improved proof of the four-color theorem and structure theory results. (4) To continue to study connectivity at the levels exhibited by the graphs of the Platonic solids and the toroidal regular lattices; in particular chains of minors or types of minors at a given level. (5) To continue to detelop surface embedding structure theory by studying questions about how nontrivial closed curves on the surface meet an embedded graph. (6) To extend graph minor theory to binary matroids. (7) To attack some problems in algorithmical graph theory and matroid theory. This research is in the general area of Combinatorics. One of the goals of Combinatorics is to find efficient methods of studying how discrete collections of objects can be arranged. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the d esign of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research.