Graphs and Matroids

图和拟阵

• 批准号: RGPIN-2016-06720
• 负责人: Newman, Michael
• 金额: $ 1.09万
• 依托单位: University of Ottawa
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=710368
• 关键词: Graphs; Matroids

This research deals is in the area of mathematics known as combinatorics. This is the study of objects built from discrete objects, and especially their structural properties. My own work is in graphs, hypergraphs and matroids. Graphs are a set of vertices, some of which are adjacent and some of which are not. It is useful to think of a pair of adjacent vertices as an edge; thus we say that if two vertices are adjacent then they are joined by an edge. As a simple example, a graph can represent a computer network: the vertices correspond to computers and the edges are direct connections. This already suggests an important property: different parts of the graph can be connected (in the graph theory sense of the word) without being directly connected. The study of connectivity in graphs is extremely important, and a wide range of applications and connections. For instance, the extent to which a graph can remain connected despite some of its edges being removed is a measure of the reliability of a computer network. Perhaps surprisingly, the eigenvalues of the adjacency matrix of the graph give a lot of information about this. Hypergraphs can be thought of as a generalization of graphs where edges can contain more than two vertices. Thus a hypergraph is a set of vertices, together with some particular collection of subsets of them, each of these subsets being an "edge". My interest in these is from the point of view of factorizations, which can be thought of as a way of colouring the set of edges such that each colour is represented the same number of times at each vertex. The motivating question is: if some of the edges are already assigned colours in some way, when can we complete the colouring to a factorization? There are some "obvious" necessary conditions on the parameters (an example in the simplest case: if we want to pair up the vertices of a graph there better be an even number of them), the question is are these conditions sufficient? Are there any deep obstacles to structure, or are the trivial obstacles the only ones? Matroids are another discrete structure, with a ground set of elements, where certain subsets of these elements considered "independent". There are a few rules: the empty set should be independent, any subset of an independent set is again independent, and given two independent sets of different sizes, there is an element in the larger one but not the smaller that can be added to the smaller to make a new independent set. This is inspired by the linear independence of set of vectors in a vector space, but is much more general. It turns out that there is a strong geometrical flavour (in particular there are well-defined notions of line, plane, etc). Matroids have strong connections to discrete optimization: finding an optimal assignment between candidates and tasks, and finding the shortest path between points in a network are both examples of finding a maximum weight basis in a matroid.

这项研究涉及到被称为组合学的数学领域。这是对由离散对象构建的对象的研究，特别是它们的结构属性。我自己的工作是研究图形、超图和拟阵。 图是一组顶点，其中一些是相邻的，而另一些不是。将一对相邻的顶点视为一条边是很有用的；因此，我们说如果两个顶点是相邻的，则它们由一条边连接。举个简单的例子，一个图可以代表一个计算机网络：顶点对应于计算机，边是直接连接。这已经暗示了一个重要的性质：图的不同部分可以在不直接连接的情况下连接(在图论意义上)。图的连通性的研究是极其重要的，并且有着广泛的应用和联系。例如，即使图形的一些边被移除，它仍能保持连接的程度是计算机网络可靠性的衡量标准。也许令人惊讶的是，图的邻接矩阵的特征值提供了许多关于这方面的信息。 超图可以被认为是图的推广，其中边可以包含两个以上的顶点。因此，超图是一组顶点，以及它们的子集的某个特定集合，每个子集都是一条“边”。我对它们感兴趣的是从因式分解的观点来看，它可以被认为是一种给边集着色的方法，使得每种颜色在每个顶点上表示相同的次数。令人振奋的问题是：如果一些边已经以某种方式分配了颜色，我们什么时候可以完成因式分解的着色？参数有一些“明显”的必要条件(最简单的例子是：如果我们想把图的顶点配对，最好是偶数个)，问题是这些条件是充分的吗？结构上有没有什么深层次的障碍，或者仅仅是那些微不足道的障碍？ 拟阵是另一种离散的结构，有一个基本的元素集，其中这些元素的某些子集被认为是“独立的”。有几条规则：空集应该是独立的，独立集的任何子集都是独立的，给定两个不同大小的独立集，在较大的集合中有一个元素，但不能将较小的元素添加到较小的集合中，以形成新的独立集合。这是由向量空间中向量集合的线性无关性启发的，但要普遍得多。事实证明，这里有一种强烈的几何色彩(特别是有定义明确的线、面等概念)。拟阵与离散优化有很强的联系：寻找候选人和任务之间的最优分配，以及寻找网络中点之间的最短路径，都是在拟阵中寻找最大权基的例子。