Problems in Graph Structure Theory

图结构理论中的问题

• 批准号: 9701317
• 负责人: Neil Robertson
• 金额: --
• 依托单位: Ohio State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-07-01 至 2000-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9701317&HistoricalAwards=false
• 关键词: Problems; Graph; Structure; Theory

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.

Robertson 9701317 该奖项将为开发与图次关系相关的结构图论中的几个项目提供资金。大部分工作涉及与 Paul Seymour、Robin Thomas 等人正在进行的联合项目；以及由首席研究员指导的研究生研究。该提案的主要主题概述如下。这些主题涵盖了图结构理论的很大一部分，因为它与图次包含关系相关。事实上，每个主题都包含重大问题，通常是众所周知的和困难的，因此任何方向的重大进展都可能会占用大量时间。目前，图论社区的其他地方正在对许多此类问题进行严重的攻击（我们的小组对此表示欢迎）。主要研究内容如下： (1)继续攻克显式有限图次结构中的开放问题。 (2)继续攻克一般有限图次结构中的开放问题。 (3)解决通过改进四色定理和结构理论结果的证明而解决的着色问题。 （4）继续研究柏拉图多面体和环形正则晶格图所展示的水平上的连通性；特别是特定级别的未成年人链或未成年人类型。 (5)通过研究曲面上的非平凡闭合曲线如何满足嵌入图的问题，继续发展曲面嵌入结构理论。 (6) 将图次要理论扩展到二元拟阵。 (7)攻克算法图论和拟阵理论中的一些问题。这项研究属于组合学的一般领域。组合学的目标之一是找到研究如何排列离散对象集合的有效方法。离散系统的行为对于现代通信极其重要。例如，大型网络的设计（例如电话系统中的网络）以及计算机科学中处理离散对象集的算法设计，都利用了组合研究。