Algorithms and structure in graphs and matroids

该研究提案属于优化、组合学和理论计算机科学的背景。我们将研究流程和图表着色的常见概括。我们将研究某些较小的闭类图和二元拟阵的结构，目的是找到有效的识别算法。以下是提案中项目的摘要。 问题 A。典型的极小极大关系是最大流最小割定理，该定理指出，图中一对顶点之间可以发送的最大流量等于分隔这些顶点的最小瓶颈的容量。此外，存在找到最大流量的有效算法。我们有兴趣将这些结果推广到多种商品流动和二元拟阵中的流动。西摩关于分数流和整数流的存在的两个诱人的猜想激发了我们的工作。 问题 B. Wagner 证明了没有 K5 小数的图可以通过粘贴平面图和沿边和三角形的一个特殊图来构造。如果可以通过首先删除边的子集然后在单次切割上收缩所有边来从 G 获得 K5，则图 G 包含 K5 作为奇次子。我们希望了解不包含 K5 作为奇次要的图的结构。这些图在图中多流的研究中发挥着关键作用。这些图可以是 4 色的，是 4 色定理的推广，并且是关于着色和同态的几个重要猜想的特征。 问题 C。Geelen、Gerards 和 Whittle 证明了二元拟阵的任何次要封闭类都可以用排除次要的有限集 S 来表征。不幸的是，这些结果仅表明集合 S 是有限的，并且对如何获得它几乎没有提供指导。在排除的次要特征中，我们寻找 S 的明确描述。寻找此类特征一直是拟阵和图论研究中非常富有成果的领域。我们的目标是找到偶数周期和偶数切割拟阵的排除次要特征和识别算法。 该提案中概述的问题被广泛认为很重要，解决这些问题将产生深远的影响。另一方面，其中一些猜想已经开放了近四十年，并且非常具有挑战性。然而，正如我们在过去几年中所开发的那样，我们现在处于令人羡慕的地位，这将极大地促进我们的项目。事实上，我们非常乐观地认为，在这项研究计划期间，我们将能够解决一些长期存在的猜想。

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.