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 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.

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.