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