Matroids in Applied and Computational Algebra

点击翻译按钮获取中文摘要

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.