| EPSRC Reference: |
EP/R023379/1 |
| Title: |
Matroids in Applied and Computational Algebra |
| Principal Investigator: |
Mohammadi, Dr F |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Mathematics |
| Organisation: |
University of Bristol |
| Scheme: |
EPSRC Fellowship |
| Starts: |
01 June 2018 |
Ends: |
28 April 2020 |
Value (£): |
362,270
|
| EPSRC Research Topic Classifications: |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
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 an
assignments 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 vertex
is 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 setting
there is an analogue of the classical Riemann-Roch theorem, and a canonical algebraic
object (a variety) encoding equivalences of divisors on it which is closely related to the graphic
matroid. I plan to solve several important problems, such as establishing algebraic properties
of this variety, by studying the Tutte polynomial.
2. Consider a network in which every edge has an associated probability of being operational. One
can think of the vertices as a set of people who pass messages among themselves and edges as communication
links 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 computed
efficiently 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.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
http://www.bris.ac.uk |