# Matroids in Applied and Computational Algebra

Lead Research Organisation:
University of Bristol

Department Name: Mathematics

### Abstract

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.

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.

### Planned Impact

The proposed research projects will bring together ideas and tools from commutative algebra, toric geometry and combinatorics. They will open up new avenues of research by applying tools from each of these fields to problems in others. Moreover, they have direct and concrete

applications

in biology, neuroscience and statistics. This will attract more postgraduate students and postdoctoral researchers to work on this topic which

is very beneficial to the UK mathematical community.

Additionally, by positively influencing the field of mathematics, my work is more likely to be exposed to other disciplines, which leads to even more direct impact.

I have ongoing collaborations with statisticians and neuroscientists in problems related to objectives A.3., A.4, B.2 and C.1.

I am currently working with A. Levina (Max Planck Institute for Biological Cybernetics) on modeling of neural networks using mathematical tools, and

I was recently invited to the ``Mediterranean Month in Phylogenetics" in Barcelona to explore further connections of my research, in particular Project B, with biological directions. This led to inception of a first concept for future collaboration with R. Yoshida (Naval Postgraduate School).

Growing such collaborations will increase the awareness about this research beyond the mathematical community to a broader audience of scientists, especially biologists. This is a potentially important impact for my work in other scientific fields and I will be following developments here very closely.

This proposal also positively impacts individuals. Most notably, a PDRA is to be hired to perform part of the proposed research.

A significant amount of time and effort will be devoted to training the PDRA and ensuring that (s)he completes a broad research programme in both theoretical and computational algebra. I will help her/him to explore a variety of

mathematical interests and grow into an independent researcher.

I will encourage the PDRA to participate in several important conferences in the field and help her/him to present her/his research and get updated on other researchers' work.

Another immediate impact of this project is to broaden the activity of algebra group in Bristol, and the UK in general. According to the EPSRC Algebra Community overview document of 2016, although the UK is a world-leader in algebra in general, its standing in commutative algebra has room for improvement. This fellowship naturally improves the UK's position in algebra as the proposed research threads are based on methods of commutative algebra, and inviting top algebraists to meetings planned in this proposal will extend collaborations with leading international universities and research centres. This will increase the standing of UK mathematical and science community, its reputation and prestige globally and attracts more investment in algebra, especially from international grants.

The EPSRC Algebra Community Overview Document of 2016 mentions that the UK has been successful in attracting PhD students in this field. However, ``given the international reputation of UK algebra and the number of researchers, this is well below capacity".

This project has already attracted one PhD student who will begin his studies in October.

I plan to recruit another PhD student using the line of research described here and its possible extensions, using funds from the university or alternative sources.

Beyond pure mathematics, mathematical science research contributes to the UK economy in a significant manner. A 2012 report for EPSRC by Deloitte indicated that it has had a part in around 16\% of UK Gross Value Added and over 2.8 million jobs. The same report also mentions that the economic benefits of pure mathematics usually come in unexpected ways and after several years. Therefore, it is a wise decision to strengthen the national research capacity in pure mathematics.

applications

in biology, neuroscience and statistics. This will attract more postgraduate students and postdoctoral researchers to work on this topic which

is very beneficial to the UK mathematical community.

Additionally, by positively influencing the field of mathematics, my work is more likely to be exposed to other disciplines, which leads to even more direct impact.

I have ongoing collaborations with statisticians and neuroscientists in problems related to objectives A.3., A.4, B.2 and C.1.

I am currently working with A. Levina (Max Planck Institute for Biological Cybernetics) on modeling of neural networks using mathematical tools, and

I was recently invited to the ``Mediterranean Month in Phylogenetics" in Barcelona to explore further connections of my research, in particular Project B, with biological directions. This led to inception of a first concept for future collaboration with R. Yoshida (Naval Postgraduate School).

Growing such collaborations will increase the awareness about this research beyond the mathematical community to a broader audience of scientists, especially biologists. This is a potentially important impact for my work in other scientific fields and I will be following developments here very closely.

This proposal also positively impacts individuals. Most notably, a PDRA is to be hired to perform part of the proposed research.

A significant amount of time and effort will be devoted to training the PDRA and ensuring that (s)he completes a broad research programme in both theoretical and computational algebra. I will help her/him to explore a variety of

mathematical interests and grow into an independent researcher.

I will encourage the PDRA to participate in several important conferences in the field and help her/him to present her/his research and get updated on other researchers' work.

Another immediate impact of this project is to broaden the activity of algebra group in Bristol, and the UK in general. According to the EPSRC Algebra Community overview document of 2016, although the UK is a world-leader in algebra in general, its standing in commutative algebra has room for improvement. This fellowship naturally improves the UK's position in algebra as the proposed research threads are based on methods of commutative algebra, and inviting top algebraists to meetings planned in this proposal will extend collaborations with leading international universities and research centres. This will increase the standing of UK mathematical and science community, its reputation and prestige globally and attracts more investment in algebra, especially from international grants.

The EPSRC Algebra Community Overview Document of 2016 mentions that the UK has been successful in attracting PhD students in this field. However, ``given the international reputation of UK algebra and the number of researchers, this is well below capacity".

This project has already attracted one PhD student who will begin his studies in October.

I plan to recruit another PhD student using the line of research described here and its possible extensions, using funds from the university or alternative sources.

Beyond pure mathematics, mathematical science research contributes to the UK economy in a significant manner. A 2012 report for EPSRC by Deloitte indicated that it has had a part in around 16\% of UK Gross Value Added and over 2.8 million jobs. The same report also mentions that the economic benefits of pure mathematics usually come in unexpected ways and after several years. Therefore, it is a wise decision to strengthen the national research capacity in pure mathematics.

### Publications

Goharshady A
(2020)

*An efficient algorithm for computing network reliability in small treewidth*in Reliability Engineering & System Safety
Herzog J
(2019)

*Measuring the non-Gorenstein locus of Hibi rings and normal affine semigroup rings*in Journal of Algebra
Mohammadi F
(2019)

*Polarization and depolarization of monomial ideals with application to multi-state system reliability*in Journal of Algebraic Combinatorics
Mohammadi F
(2019)

*Toric degenerations of Grassmannians from matching fields*in Algebraic CombinatoricsDescription | - Organising Maths Contests and Problem-Solving Workshops for Undergarduate Studnets at Bristol - Organising International Conferenecs - Teaching various one-week courses in reserach summer schools |

First Year Of Impact | 2018 |

Sector | Education |

Impact Types | Societal |

Description | Early Career Research Grant |

Amount | £600 (GBP) |

Funding ID | 91721 |

Organisation | London Mathematical Society |

Sector | Academic/University |

Country | United Kingdom |

Start | 09/2018 |

End | 09/2019 |

Description | Reserach grant to support PhD studenst to attend the conference on "Advances in Applied Algebraic Geometry" |

Amount | £600 (GBP) |

Organisation | Institute of Mathematics and its Applications |

Sector | Academic/University |

Country | United Kingdom |

Start | 12/2018 |

End | 12/2018 |

Description | Scheme 1 LMS Grant |

Amount | £5,660 (GBP) |

Funding ID | 11777 |

Organisation | London Mathematical Society |

Sector | Academic/University |

Country | United Kingdom |

Start | 12/2018 |

End | 12/2018 |