Matroids in Applied and Computational Algebra

拟阵是新颖的组合对象，它概括和统一了几个独立性概念，例如向量空间和图中的概念。它们出现在编码理论和优化中，并与统计学和计算机科学有着良好的联系。1948年，英国数学家和密码破译者Tutte将多项式与每个拟阵相关联，其中包含拟阵的许多有趣性质。关于Tutte多项式的许多问题至今仍未解决。在过去的几年里，在该领域的几个突破发生使用代数几何工具。另一方面，这些领域之间的丰富联系也导致了对代数和几何中重要问题的新见解。图拟阵是第一个自然类，在我自己以前的研究中表现突出，在那里我发现了与新领域的惊人联系，如除数理论，系统可靠性理论和神经科学。在这个项目中，我建议研究新方法并解决几个重要的开放问题。这导致了许多应用。例如，这里有一些重要的问题，将在这个项目中使用拟阵研究的各个领域。图可以看作是代数曲线的类似物.图上的除数是整数到其顶点的赋值。我们可以把它看作是每个顶点都有一些“记号”。我们定义了一个游戏，其中在每一步中选择一个顶点，并将一个令牌借给每个邻居或从每个邻居那里借一个。如果有一个移动序列，其中一个移动到另一个，则两个除数是等价的。从这个过程中产生的数学结构是非常丰富的。在这种情况下，有一个类似的经典Riemann-Roch定理，和一个典型的algebraicobject（一种）编码等价的因子，这是密切相关的graphicmatroid。我计划通过研究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.