# Matroid Theory

Instructor: Rafael S. González D'León
Email: rafael.gonzalezl@usa.edu.co
Homepage: http://dleon.combinatoria.co
Office hours: Monday 3:00-4:00 pm, Tuesday 2:00-3:00 pm, and by appointment.

## Classes

Mondays 6:00-8:00 pm and Wednesdays 4:00-6:00 pm.

## Literature

Matroid theory. Oxford University Press. Oxley, J.G.
Matroid theory. Courier Corporation. Welsh, D.J.

## Course content

A matroid is a mathematical object that abstracts the idea of independence: linear, algebraic, etc. In particular, many of the theorems about linear independence in linear algebra have their generalizations to matroids where proofs are many times more elegant and clean. The concept of a Matroid was introduced by H. Whitney in 1935 but was further studied by many other mathematicians, and it is currently an active area of research. One of the greatest mathematicians working in the field was W. T. Tutte who developed in the 1950's a great part of the theory that is known to us today. Because of the close relation with linear algebra and vector spaces, matroids can be useful in many contexts where these appear. They appear in the theory of linear optimization generalizing the class of problems where the greedy algorithm can be used. They also play a central role in a nice stratification of the Grassmann variety (the Grassmannian).

As it happens with topologies and sigma algebras, matroids are set systems, that is, a collection of subsets of a given set satisfying a few fundamental axioms. What is amazing for matroids is what is commonly referred to as polymorphism, the fact that matroids have plenty of equivalent definitions: in terms of independence sets, bases, circuits, flats, closure operators, etc. The polymorphic nature of matroids is what have made the theory so successful since different definitions are suitable to solve different problems.

In the first part of this course we will concentrate on the basics of the theory. We will define the concepts of independence sets, bases, circuits, flats, and we will visit many contexts in which matroids appear: linear algebra, graph theory, affine and projective geometry, etc. We will cover the concepts of duality, minors, connectivity and state the most important theorems in the field. As an interesting application of the theory, we will see in the last part of the course how matroids are useful to give a stratification of the Grassmannian and furthermore we will discuss the idea of positivity that will bring us to the concept of positroids, a beautiful class of matroids that in recent years appear to have connections to the nature of our physical reality and to many other areas.

### Tests (30%)

There will be 2 tests (each of 15%) at the end of each of the first two terms. The tests will be announced at least one week in advance.

### Homework(30%)

There will be two sets problems (each of 15%) to be handed in at the end of each of the first two terms. To work on the homework problems is crucial for your understanding of the material presented in class. Be sure to separate enough time each week to think and write your solutions. It is recommended that you think and attempt every problem on your own before seeking any help. You are encouraged to discuss the material of the course with your classmates, however you must write your own solutions using your own words.

### Final project and presentation(40%)

The final presentation will consists of reading, writing and presenting about an article on the area of matroid theory. The topics will be assigned well in advance and there will be two partial submissions (each with a weight of 10%) and a final presentation (20%)

### Problem Sessions

There will be various in-class problem sessions during the semester whose goal is to reinforce the concepts learned during a given week. During the problem sessions you are strongly encouraged to share what you have learned and to learn from your fellow class mates (share and learn).

## Syllabus

We will cover some of the topics in the following list.
Topic
The idea of a matroid
Independence sets and circuits
Bases
Rank
Closure operators
Graphic matroids
Representable matroids
Geometric representations of matroids of small rank
Transversal matroids
Geometric lattices and the lattice of flats
The greedy algorithm
Dual matroids
Minors and contraction
Connectivity
Projective and affine geometries
The matroid stratification of the Grassmannian
Positroids

## Código of conducta

Los estudiantes deben consultar los derechos y debéres del estudiante en el Reglamento estudiantil. Cualquier ofensa a los lineamientos dispuestos por la universidad iniciará los procedimientos disciplinarios establecidos.

## Changes to this Syllabus

This syllabus may have some changes during the semester. It is responsibility of the students to visit frequently the webpage of the course for up to date information.