Problems in Graph Structure Theory

罗伯逊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.