Structure Theory for Graphs and Matroids

图和矩阵的结构理论

• 批准号: 0071096
• 负责人: Neil Robertson
• 金额: $ 14.84万
• 依托单位: Ohio State University Research Foundation -DO NOT USE
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-07-01 至 2006-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0071096&HistoricalAwards=false
• 关键词: Structure; Theory; Graphs; Matroids

STRUCTURE THEORY OF GRAPHS AND MATROIDSThe investigator intends to pursue research with several colleagues in the areas of graph coloring, matroid representation, surface embeddings and graph structure. The main graph coloring project involves aspects of the Hadwiger graph coloring conjecture, that any graph that needs k colors to properly color its vertices can be contracted to the complete graph on k vertices. The main matroid theory project involves a plan to settle Rota's conjecture that matroids representable over a fixed finite field have finite obstacle sets. In contrast to these two well known open problems, there are many concrete questions on surface embeddings and other graph structures, and these are important to settle for the orderly development of the subject. Two problems which provide a focus in these areas are the Seymour-Szekeres cycle-double-cover conjecture and Hajos' conjecture that graphs that need 5 colors must contain K_5 topologically. The proposed research studies several problems, closely related to these, but perhaps more accessible. The most promising part f this project, and mathematically the most interesting, is the Rota conjecture and the related conjecture that finite matroids representable by matrices over a fixed finite field are well-quasi-ordered. This is an area with several very strong mathematicians currently active, as well as the investigators usual collaborators. The investigator feels that this topic should be strongly pursued on a wide front.About 20 years ago the investigator and his colleague, Paul Seymour, began a project concerned with the structural properties of graphs which are preserved under the elementary operations of deleting or contracting the edges of the graph. The outcome was to show that these properties are finitely based, in the sense that the list of graphs, which are minimal amongst those for which a given property fails, is always finite. This shows there is always a finite list of graphs explaining why the property fails to hold. Moreover, the dual problem was solved of characterizing the inherent structure of graphs which possess any such property (at least to a close and useful approximation). Over the years since this was done the investigator, Seymour and an expanding group of colleagues and students, have been vigorously developing the consequences of this main theory, and striving to apply the techniques to their natural scope. This has been important mathematically, and for the subject of graph theory, but also has contributed extensively to computer science and combinatorial optimization through the algorithms arising naturally from the finiteness conditions. There is real hope to extend the subject into its natural context in linear algebra known as matroid theory, where also there are finiteness conjectures when the matroids arise from matrices over a finite field. There are also still many long standing problems, open to the graph theory techniques of this area, which provide a focus for the more general development of the theory, and which are an important part of this proposal.

图和矩阵的结构理论研究者打算与几位同事在图着色、矩阵表示、表面嵌入和图结构等领域进行研究。主要的图着色工程涉及哈德维格图着色猜想的各个方面，即任何需要k种颜色来正确着色其顶点的图都可以缩并为k个顶点的完全图。主要的拟阵理论项目涉及解决Rota的猜想，即在固定有限域上可表示的拟阵具有有限障碍集。与这两个众所周知的开放问题相比，有许多关于表面嵌入和其他图结构的具体问题，这些问题对于该学科的有序发展至关重要。在这些领域中，有两个问题是Seymour-Szekeres循环双盖猜想和Hajos猜想，即需要5种颜色的图在拓扑上必须包含K_5。拟议的研究研究了几个问题，与这些密切相关，但可能更容易理解。这个项目最有希望的部分，也是数学上最有趣的部分，是Rota猜想和相关的猜想，即在固定有限域上由矩阵表示的有限阵是良拟序的。这是一个有几个非常强大的数学家目前活跃的领域，以及研究人员通常的合作者。研究者认为这个话题应该在广泛的战线上得到大力的研究。大约20年前，这位研究者和他的同事Paul Seymour开始了一个研究图的结构性质的项目，这些性质在图的边的删除或收缩的基本操作下是保留的。结果表明，这些性质是有限的，也就是说，图的列表总是有限的，这些图在给定的性质不成立的图中是最小的。这表明总是有一个有限的图列表来解释为什么这个属性不成立。此外，还解决了具有这些性质的图的固有结构的对偶问题（至少在一个接近和有用的近似下）。多年来，西摩和越来越多的同事和学生一直在大力发展这一主要理论的结果，并努力将这些技术应用于它们的自然范围。这在数学上和图论主题上都很重要，但也通过从有限条件中自然产生的算法对计算机科学和组合优化做出了广泛的贡献。确实有希望将这个主题扩展到线性代数的自然背景中，即所谓的拟阵理论，当拟阵由有限域上的矩阵产生时，也存在有限猜想。还有许多长期存在的问题，对这个领域的图论技术开放，这为理论的更普遍发展提供了一个焦点，这是本建议的重要组成部分。