Matroids and Applications

Weekly Reading Seminars

 2024 


Welcome to the Weekly Reading Seminars on Matroids and Applications taking place on Zoom every Thursdays 13:00-14:00 CET.

Registration:

Please email Fatemeh or Duy if you are interested in attending the meeting or have any questions.

Overview:

The primary aim of this reading group is to become familiar with matroid theory. Our main motivation is to grasp the theory to a level where we are equipped to use and potentially adapt it to address applied problems. Initial sessions will focus on introducing the fundamental concepts and principles of matroids, while subsequent discussions will explore diverse applications in algorithm design, coding theory, statistics, and quantum physics.


Schedule:


Matroids from algebraic and geometric perspectives (slides)


Abstract: In this presentation, I will give an introductory talk on matroids, delving into their geometric properties, including realization spaces and their corresponding polytopes. The main themes of the talk are: (1) establishing matroids through dependent sets; (2) establishing connections between their geometric properties and classical theorems in incidence geometry; and (3) exploring families of examples and providing directions for future talks.


Matroids basics (slides)

Abstract: In this talk we will introduce the formalism of matroids to see how it embraces notions of (in)dependence coming from different contexts. After an introduction reviewing the different ways in which a matroid can be introduced, we will define some of the main operations among matroids. Secondly, we will investigate the internal structure of a matroid, through the notions of rank and flats. Finally, we will see how the independent sets of a matroid can be characterized via certain properties of simplicial complexes, and through an algorithmic approach.



Oriented matroids, chirotopes and positroids (slides)

Abstract: We will introduce oriented matroids and provide characterizations via circuits and chirotopes. Then, we will consider oriented matroids arising from vector configurations and explain how to view them as elements in the Grassmannian. Following this, we define positroids as matroids realizable over the real numbers, where the chirotope exclusively yields positive values. If time permits, we will conclude by discussing some of the combinatorial objects introduced by Postnikov to enumerate positroids of a given rank on [n].



Rank metric codes and q-matroids (slides)

 

Abstract: We will define rank-metric codes, as linear spaces of matrices, and look at two kinds of linearity; giving rise to Delsarte rank-metric codes, and Gabidulin rank metric codes, respectively. For the last ones we will see how they give rise to q-matroids, whose properties will determine properties of the codes that gave rise to them.  We will take a brief look at space codes associated to rank-metric codes.  We will also show a “projectivization process” that makes us derive usual matroids from q-matroids, enabling us to find properties of Gabidulin rank metric codes from “usual” matroids in a way which earlier was possible only for codes with the Hamming metric. A remark about Chow rings of matroids will be given.  If time permits,  we will also show how certain topological descriptions of complexes associated to matroids and q-matroids, nevertheless are more easily applied for codes with the Hamming metric (giving matroids) than for the rank-metric ones (giving q-matroids).



Defining equations of matroid varieties


Abstract: In this talk we will introduce the basic definitions on matroid varieties and then we will see two methods to construct polynomials within the ideal of these varieties. One of them is via the Grassmann-Cayley algebra and the other is called liftability technique. 


Matroid polytopes and generalized permutahedra arising from graphical models 

Abstract: I will explain the notion of matroid polytopes and the submodular properties of the rank function of the matroid. As an application, I will discuss the conditional independence statements arising from loopless mixed graphical models. I will describe their associated polytopes and explain how the fan of this polytope can be obtained as a coarsening of the fan of the permutahedron, as well as through the Minkowski sum of matroid polytopes.




Matroid Stratification of ML Degrees of Independence Models


Abstract: In Algebraic Statistics, we view algebraic varieties as statistical models, which allows us to transport statistical questions to the realm of Algebra and Geometry. Given a model of a random variable and some observations, a natural question is to determine which distributions of the model most closely match the observations. This problem is known as Maximum Likelihood (ML) Estimation, and its algebraic complexity is called the ML degree of the model. In this talk I will describe the geometric interpretation of ML degree for toric varieties. In particular, I will explain how ML degrees of certain models can be characterised as matroid invariants and how we can use hyperplane arrangements to directly compute ML degrees.



Combinatorics of positroids and the Amplituhedron


Abstract: Positroids are realizable matroids with a positivity condition. In this talk we will introduce some of the classical combinatorial objects in bijection with positroids, like bounded affine permutations and Grassmann necklaces. We will then define a new family of objects associated with positroids, the essential family, and study its properties. In the end, we will discuss some applications of positroids in the study of the amplituhedron, a geometric object encoding information of interest in theoretical physics. 


 

Organizers:  Fatemeh Mohammadi

                      Duy Ho