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.

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.
 
Title Cubes with patterns 
Description I am collaborating with an artist "Dail Behennah" to construct a piece which will be exhibited in our new Math bilding "Fry Building" in a couple of Months. 
Type Of Art Artwork 
Year Produced 2019 
Impact I am helping Dail Behennah to construct a geometric piece using small cubes and I am making a poster describing the geometric math invariants of the piece. 
URL https://www.dailbehennah.com/section649353_728198.html
 
Description - 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 Developing and delivering new postgraduate courses on "Combinatorial Algebraic Geometry"
Geographic Reach National 
Policy Influence Type Influenced training of practitioners or researchers
Impact I taught an online course in the TCC network which was very appreciated by the postgraduate stduents in various universities in the UK. To the best of my knowledge, that was the first time to have a postgraduate course on this topic and delivering this course on the TCC website and Juliet network helped more studnets, 31 postgraduate students to attend this course.
URL https://sites.google.com/view/cag2018/home
 
Description Invited Lectures Series in the CIMPA workshop on "Commutative Algebra with Applications to Statistics and Coding Theory"
Geographic Reach Multiple continents/international 
Policy Influence Type Influenced training of practitioners or researchers
Impact CIMPA workshops are designed for postgraduate stduents in developing countries to help them to stay in the frontier of the research field who might be interetsed in.
URL http://archive.schools.cimpa.info/archivesecoles/Zacatecas2018/sites.google.com/a/cimat.mx/cimpa-201...
 
Description Lecture series in "Summer School in Algebraic Statistics" in Tromso, Norway
Geographic Reach Multiple continents/international 
Policy Influence Type Influenced training of practitioners or researchers
Impact https://uit.no/nyheter/artikkel?p_document_id=598151&p_dim=88205
URL https://site.uit.no/alg-stat/
 
Description Member of Senate in University of Bristol
Geographic Reach Local/Municipal/Regional 
Policy Influence Type Membership of a guideline committee
Impact I am one of the tw members of Senate.
URL http://www.bristol.ac.uk/university/governance/universitycommittees/senate/
 
Description Organised "Math Competitions for Undergraduate Students to attend the IMC 2019"
Geographic Reach Local/Municipal/Regional 
Policy Influence Type Influenced training of practitioners or researchers
Impact These workshops are organsied to attarct the best undergraduate students interetsed in Mathematics and train them for the Internatial Math Competitions IMC 2018
URL https://sites.google.com/view/imc2019bristol/home
 
Description Organising Workshops and Maths Contests for undergraduate students in Bristol
Geographic Reach Local/Municipal/Regional 
Policy Influence Type Influenced training of practitioners or researchers
Impact The cotests and the workshops are highly appreciated by our stduents. 60 Undergraduate students attaneded the first contest.
URL https://sites.google.com/view/imc2018bristol/home
 
Description Early Career Research Grant
Amount £600 (GBP)
Funding ID 91721 
Organisation London Mathematical Society 
Sector Learned Society
Country United Kingdom
Start 09/2018 
End 09/2019
 
Description Research grant to organise a conference in Advances in Applied Algebraic Geometry
Amount £10,400 (GBP)
Funding ID Conference Grant 
Organisation Heilbronn Institute for Mathematical Research 
Sector Academic/University
Country Unknown
Start 12/2018 
End 12/2018
 
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 Learned Society
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 Learned Society
Country United Kingdom
Start 12/2018 
End 12/2018
 
Title Computing Toric degenerations of varieties 
Description The paper on "Toric degenerations of Grassmannians from matching fields" is highly appreciated in the community. I have given several invited talks on this. 
Type Of Material Improvements to research infrastructure 
Year Produced 2018 
Provided To Others? No  
Impact The methods combined and introduced in this paper are new to our communities in Maths. 
URL https://arxiv.org/pdf/1809.01026.pdf
 
Description Algebraic Statistics (Conditional independence ideals with hidden variables) 
Organisation Max Planck Society
Department Max Planck Institute for Mathematics in the Sciences
PI Contribution The algebraic approach to study Conditional independence models with hidden variables
Collaborator Contribution Equal contribution among coauthors
Impact https://arxiv.org/pdf/1901.03059.pdf
Start Year 2012
 
Description Gröbner degenertions of Grassmannians and universal cluster algebras 
Organisation University Institute of Oaxaca
PI Contribution The above Research Project on the link between Gröbner degenertions and universal cluster algebras is proposed by me as a jont project with experts in cluster algebar in Oaxaca.
Collaborator Contribution This is a jointbresreach project with equal contribution among coauthors.
Impact This is a work in progress and the paper will be public soon.
Start Year 2019
 
Description Multi-state System Reliability 
Organisation University of La Rioja
PI Contribution This was an ongoing project which was facilitated by EPSRC and the Universityb of La Rioja to travel to Spain and collaborate together.
Collaborator Contribution Equal contribution in the project
Impact https://arxiv.org/pdf/1807.05743.pdf
Start Year 2018
 
Description Toric degenerations of Grassmannians 
Organisation University of Oslo
Department The Faculty of Mathematics and Natural Sciences
Country Norway 
Sector Academic/University 
PI Contribution This is a jointbproject with Professor Kristin Shaw in University of Oslo.
Collaborator Contribution Equal contribution among authors
Impact https://arxiv.org/pdf/1809.01026.pdf
Start Year 2016
 
Description Organised "Advances in Applied Algebraic Geometry" 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Study participants or study members
Results and Impact The conference covered a broad spectrum of the rapidly growing field of applied algebraic geometry, and the talks were for general audience. In recent years, modern algebraic geometry methods have been picked up by applied mathematicians, engineers, biologists, neuroscientists and computer scientists to solve real-world problems. This has resulted in a steadily-increasing emphasis on computational and algorithmic problems, and the field has blossomed to the extent that SIAM has formed a new activity group in this field and has organised annual conferences and meetings since 2011.
The meeting brought several internationally recognised experts in this field to Bristol to present their research and engage with young scientists, hence strengthening the UK position in this area. Several leading scientists of the field were at Bristol and all of them showed a great enthusiasm and support for the event.
Year(s) Of Engagement Activity 2018
URL https://sites.google.com/view/a3g-2018/home
 
Description Organised "Math Contests and Problem-Solving Workshops for Undergraduate Students 2019" 
Form Of Engagement Activity A formal working group, expert panel or dialogue
Part Of Official Scheme? No
Geographic Reach Local
Primary Audience Undergraduate students
Results and Impact Similart to the events in 2018
Year(s) Of Engagement Activity 2019
URL https://sites.google.com/view/imc2019bristol/home
 
Description Organised "Math Contests and Problem-Solving Workshops for Undergraduate Students" 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach Local
Primary Audience Undergraduate students
Results and Impact These Math Contests were very exciting and there were more than 50 students attended the first contest. There were a lot of training sessions designed for UG stduents. Some PhD students taught courses and helped with the workshops.
Year(s) Of Engagement Activity 2018
URL https://sites.google.com/view/imc2018bristol/home
 
Description Organised "One-Day Meeting in Combinatorial Algebraic Geometry" 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Postgraduate students
Results and Impact The one-day workshop on combinatorial algebraic geometry was organised as a network meeting. I would like to emphasize that talks were accessible to many graduate students, in Bristol, Warwick QMUL, and Bath. Most postgraduate students and postdoctoral researchers gave a 5-minutes presentations on their ongoing reserach.
Year(s) Of Engagement Activity 2018
URL https://people.maths.bris.ac.uk/~fm17415/Combinatorial_Alegbraic_Geometry_LMS.html
 
Description Organised "Women in Mathematics: Opportunities for the Future 2018" 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Undergraduate students
Results and Impact This two-day event was aimed at encouraging female mathematics students, including those who self-define as women or whose gender identity includes "woman" or is non-binary, to consider continuing their studies to PhD level.

The event featured talks from mathematicians working both in universities and industry, giving insight into their current roles and their careers to date. Even more importantly, there was ample time to talk in small groups to the other participants who are facing the same decisions, and to current PhD students who have recently faced the same questions.
Year(s) Of Engagement Activity 2018
URL https://www.bristol.ac.uk/maths/events/2018/women-in-maths-2018.html