Matroids in Applied and Computational Algebra

拟阵是一种新的组合对象，它概括和统一了一些独立性的概念，例如向量空间和图中的概念。它们出现在编码理论和优化中，并且与统计学和计算机科学有着充分的研究联系。1948年，英国数学家和密码破译者Tutte将一个多项式与每个矩阵联系起来，其中包含了矩阵的许多有趣的性质。关于图特多项式的许多问题仍未得到解决。在过去的几年中，使用代数几何工具在该领域取得了一些突破。另一方面，这些领域之间的丰富联系也导致了对代数和几何重要问题的新见解。图形拟阵是第一个自然类，在我自己之前的研究中占有突出地位，在那里我发现了与除数理论、系统可靠性理论和神经科学等新领域的惊人联系。在这个项目中，我建议研究新的方法并解决几个重要的开放性问题。这导致了许多应用程序。例如，以下是本项目将使用拟阵研究的各个领域的一些重要问题。图可以看作是代数曲线的类似物。图上的除数是对其顶点的整数赋值。你可以把它想象成每个顶点都有一些“标记”。我们定义一个游戏，在每一步中选择一个顶点，并向每个相邻顶点借一个令牌，或者从每个顶点借一个令牌。如果有一个从一个到另一个的移动序列，两个除数是等价的。从这个过程中产生的数学结构非常丰富。在这种情况下，有一个经典黎曼-洛克定理的类似物，以及一个规范代数对象（一种变体），在其上编码与图形矩阵密切相关的除数等价。我计划通过研究Tutte多项式来解决几个重要的问题，比如建立这个变量的代数性质。考虑一个网络，其中每条边都有一个相关的可操作概率。我们可以把顶点想象成一组在他们之间传递消息的人，把边想象成他们之间的通信链接。在这样的网络中计算各种消息传递的可靠性概念有许多应用。当一个人被固定为消息源，多个人被固定为目标时，就会出现一个经过充分研究的案例，目标是找到消息源能够与目标沟通的概率。通过在关联矩阵的Tutte多项式中插入特殊值来获得网络可靠性。计算可靠性还与前面提到的代数性质有关。因此，其中一个的积极结果将直接影响到另一个。计算可靠性是计算机科学中的一个难题。考虑到应用程序产生的网络通常具有特殊的属性，作为本项目的一部分，我试图统一和描述网络家族，其中可靠性可以被有效地计算并找到算法。神经网络是将大脑的不同区域建模为顶点的图形。在一种常见的设置中，一个电位与每个顶点相关联，当一个顶点的电位增加到一定阈值以上时，它将多余的电位分配给它的邻居，这些邻居可能会继续同样的过程。如果一个网络是稳定的，但一个小的外部刺激就能使它不稳定，那么这个网络就处于临界状态。然后，网络继续进行一系列潜在的传输（雪崩），直到达到稳定状态。临界状态已被证明可以提供有关大脑的有用生物学信息。临界态的组合性质使人想起拟阵。作为这个项目的一部分，我将正式定义包含所有这些信息的矩阵，并将其用作研究神经网络中雪崩大小分布的工具。

Matroids are novel combinatorial objects that generalise and unify several concepts of independence, such as the ones in vector spaces and graphs. They appear in coding theory and optimisation, and have well-studied connections to statistics and computer science. In 1948, Tutte, a British mathematician and codebreaker, associated a polynomial to each matroid which contains many interesting properties of the matroid. Many problems about Tutte polynomials are still unsolved. In the past few years, several breakthroughs happened in the field using algebraic geometry tools. On the other hand, the rich connections between these fields also led to new insights on important problems in algebra and geometry.Graphic matroids are the first natural class and feature prominently in my own previous research, where I uncovered surprising connections to new areas such as divisor theory, system reliability theory and neuroscience.In this project, I propose to investigate new methods and solve several important open problems. This leads to many applications. For example, here are some important problems of various fields that will be studied using matroids in this project.1. A graph can be viewed as an analogue of an algebraic curve. A divisor on a graph is anassignments of integers to its vertices. One can think of it as each vertex having a number of ``tokens". We define a game in which at each step a vertexis chosen and lends a token to each of its neighbours or borrows one from each. Two divisors are equivalent if there is a sequence of moves taking one to the other. The mathematical structures arising from this process are very rich. In this settingthere is an analogue of the classical Riemann-Roch theorem, and a canonical algebraicobject (a variety) encoding equivalences of divisors on it which is closely related to the graphicmatroid. I plan to solve several important problems, such as establishing algebraic propertiesof this variety, by studying the Tutte polynomial.2. Consider a network in which every edge has an associated probability of being operational. Onecan think of the vertices as a set of people who pass messages among themselves and edges as communicationlinks among them. Computing various reliability notions of messaging in such a network has many applications.A well-studied case arises when a person is fixed as a source and multiple people as targets, and the objective is to find the probability of the source being able to communicate with the targets. The network reliability is obtained by plugging special values in the Tutte polynomial of the associated matroid. Computing reliability is also related to algebraic properties mentioned in the previous part. Therefore, positive results in each of them will directly impact the other. Computing reliability is a hard problem in computer science. Given that networks arising from applications usually have special properties,as part of this project, I attempt to unify, and characterise families of networks in which reliability can be computedefficiently and find algorithms.3. A neural network is a graph modeling different regions of a brain as vertices. In one common setting, a potential is associated to each vertex and when a vertex's potential is increased above a certain threshold, it distributes the excess potential with its neighbours, who might in turn continue the same process. A network is in a critical state if it is stable but a small external stimulus is able to make it unstable. The network then continues with a series of potential transfers (avalanche) until it reaches a stable state. Criticality has been shown to provide useful biological information about the brain. Combinatorial properties of critical states are reminiscent of matroids. As part of this project, I will formally define the matroid containing all these information and use it as a tool to study avalanche size distributions in neural networks.