Structure Theory for Graphs and Matroids

Ohio State University Research Foundation -Do Not Use, Columbus OH

Investigators

Abstract

STRUCTURE THEORY OF GRAPHS AND MATROIDS The 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.