Problems in Graph Structure Theory

该奖项将提供资金发展与图次关系相关的结构图论的几个项目。大部分工作涉及与保罗·西摩、罗宾·托马斯等人正在进行的联合项目；研究生的研究由首席研究员指导。本提案的主要议题摘要如下。这些主题涵盖了图结构理论的很大一部分，因为它与图小包含关系有关。事实上，每个主题都包含重大问题，通常是众所周知的和困难的，因此在任何方向上取得重大进展都可能需要花费大量时间。目前，在图论社区的其他地方，对许多这些问题进行了严重的攻击（我们的小组欢迎）。主要研究内容如下：(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.