Graphs and Matroids

图和拟阵

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

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