Algorithms and structure in graphs and matroids

点击翻译按钮获取中文摘要

This research proposal falls into the context of optimization, combinatorics, and theoretical computer science. We will investigate common generalizations to flows and graphs colouring. We will study the structure of certain minor closed classes of graphs and binary matroids with the aim of finding efficient recognition algorithms. The following is a summary of the projects in the proposal.***Problem A. A quintessential minimax relation is the Max-Flow Min-Cut theorem that states that the largest amount of flow that can be sent between a pair of vertices in a graph is equal to the capacity of the smallest bottleneck separating these vertices. Furthermore, there exist efficient algorithms to find a maximum flow. We are interested in generalizing these results to multi-commodity flows and to flows in binary matroids. Two tantalizing conjectures by Seymour on the existence of fractional and integer flows are motivating our work.***Problem B. Wagner proved that graphs without K5 minors can be constructed by pasting planar graphs and one special graph along edges and triangles. A graph G contains K5 as an odd-minor if K5 can be obtained from G by first deleting a subset of the edges and then contracting all the edges on a single cut. We wish to understand the structure of graphs that do not contain K5 as an odd minor. These graphs play a pivotal role in the study of multi-flows in graphs. These graphs can be 4-coloured, a generalization of the 4-color theorem, and feature in several important conjectures on colouring and homomorphisms.***Problem C. Geelen, Gerards, and Whittle proved that any minor closed class of binary matroids can be characterized by a finite set S of excluded minors. Unfortunately, these results only indicate that the set S is finite and provide little guidance on how to obtain it. In an excluded minor characterization we look for an explicit description of S. Finding such characterizations has been a very fruitful area of research in both matroid and graph theory. Our goal is to find excluded minor characterizations and recognition algorithms for both even-cycle and even-cut matroids.***The problems that are outlined in this proposal are widely viewed as important and resolving those would have profound implications. On the other hand some of these conjectures have been open for nearly four decades and are very challenging. We are however, in an enviable position now, as we have developed over the past few years, machinery that should greatly facilitate our projects. Indeed, we are very optimistic that we will be able to settle some long-standing conjectures during the period of this research proposal.**