EPSRC logo

Details of Grant 

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:
Algebra & Geometry
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
23 Jan 2018 EPSRC Mathematical Sciences Fellowship Interviews January 2018 Announced
29 Nov 2017 EPSRC Mathematical Sciences Prioritisation Panel November 2017 Announced
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