Evelyn Lamb: Welcome to My Favorite Theorem. I'm your host Evelyn Lamb, a freelance math and science writer in Salt Lake City, Utah, and this is your cohost.

Kevin Knudson: I'm Kevin Knudson, professor of mathematics at the University of Florida. How are you doing, Evelyn?

EL: I am still on an eclipse high. On Monday, a friend and I got up, well got up in time to get going by 5 in the morning, to get up to Idaho and got to experience a total eclipse, which really lived up to the hype.

KK: You got totality?

EL: Yes, we got in the band of totality for a little over two minutes.

KK: We had 90 percent totality. It was still pretty impressive. Our astronomy department here set up their telescopes. We have a great astronomy department here. They had the filters on. There were probably 500 kids in line to see the eclipse. It was really pretty spectacular.

EL: It was pretty cool. I'm already making plans to go visit my parents on April 8, 2024 because they're in Dallas, which is in the path for that one.

KK: Very nice.

EL: So I've been trying to get some work done this week, but then I just keep going and looking at my friends' pictures of the eclipse, and NASA's pictures and everything. I'm sure I will get over that at some point.

KK: It was the first day of classes here for the eclipse. It was a bit disruptive, but in a good way.

EL: My spouse also had his first day of class, so he couldn't come with us.

KK: Too bad.

EL: But anyway, we are not here to talk about my feels about the eclipse. We are here to welcome Federico Ardila to the podcast. So Federico, would you like to say a bit about yourself?

Federico Ardila: Yeah, first of all, thanks so much for having me. As Evelyn just said, my name is Federico Ardila. I never quite know how to introduce myself. I'm a mathematician, I'm a DJ, I'm an immigrant from Colombia to the US, and I guess most relevant to the podcast, I'm a math professor at San Francisco state university. I also have an adjunct position in Colombia at theUniversidad de los Andes. I'm also spending the semester at MSRI [Mathematical Sciences Research Institute] in Berkeley as a research professor, so that's what I'm up to these days.

KK: I love MSRI. I love it over there. I spent a semester there, and every day at teatime, you walk into the lounge and get the full panoramic view of the bay. You can watch the fog roll in through the gate. It's really spectacular.

FA: Yeah, you know, one tricky thing is you kind of want to stay for the sunset because it's so beautiful, but then you end up staying really late at work because of it. It's a balance, I guess.

KK: So, the point of this thing is that someone has a favorite theorem, so I actually don't know what your favorite theorem is, so I'm going to be surprised. What's your favorite theorem, Federico?

FA: Yeah, so first of all I apologize for not following your directions, but it was deliberate. You both asked me to tell you my favorite theorem ahead of time, but I'm not very good at following directions. But I also thought that since I want to talk about something that I think not a lot of people think about, maybe I shouldn't give you a heads-up so we can talk about it, and you can interrupt me with any questions that you have.

EL: Get our real-time reactions here.

FA: Exactly. The other thing is that instead of talking about a favorite theorem, I want to talk about a favorite object. There's a theorem related to it, but more than the theorem, what I really like is the object.

EL: Okay.

FA: I want to talk a little about matroid theory. How much do you two think about matroids?

KK: I don't think about them much.

EL: Not at all.

KK: I used to know what a matroid is, so remind us.

FA: Excellent. Yeah, so matroid theory was basically an abstraction of the notion of independence. So something that was developed by Hassler Whitney, George Birkhoff, and Saunders MacLane in the '30s. Back then, you could write a thesis in graph theory at Harvard. This was part of Hassler Whitney's Ph.D. thesis where he was trying to solve the four-color theorem, which basically says that if you want to color the countries in a map, and you only have four colors, you will always be able to do that in such a way that no two neighboring countries are going to have the same color. So this was one of the big open problems at the time. At the time they were trying to figure out a more mathematical grounding or structure that they could put on graphs, and so out of that the theory of matroids was born. This was in a paper of Whitney in 1935, and he had the realization that the properties that graphs have with regards to how graphs cycle around, what the cycles are, what the spanning trees are, and so on, are exactly the same properties that vectors have. So there was a very strong link between graph theory and linear algebra, and he basically tried to pursue an axiomatization of what was the key combinatorial essence of independence?

EL: Okay, and so by independence, is that like we would think of linear independence in a matrix? Matroid and matrix are kind of suggestively similarly named. So is that the right thing we should be thinking about for independence?

FA: Exactly, so you might think that you have a finite set of vectors in a vector space, and now you want to figure out the linear dependencies between them. And actually that information is what's called the matroid. Basically you're saying these two vectors are aligned, or these three vectors lie on the same plane. So that information is called the matroid, and Whitney basically laid out some axioms for what the kind of combinatorial properties that linear independence has, and what he realizes is that these are exactly the same axioms that graphs have when you think about independence. Now you need a new notion of independence. In a graph you're going to say you have a dependency in edges whenever they form a cycle. So somehow it is redundant to be able to walk from point A to point B in two different ways, so whenever there is that redundancy, we call it dependency in a graph.

Basically Whitney that these were the same kind of properties, and he defined a matrix to be an abstract mathematical object that was supposed to capture that notion of independence.

EL: Okay. So this is very new to me, so I'm just kind of doing free association here. So I'm familiar with the adjacency matrix of a graph. Does this contain information about the matroid, or is this a little side path that is not really the same thing?

FA: This is a really good point. To every graph you can associate an adjacency matrix. Basically what you do is if you have an edge from vertex i to vertex j in the graph, in the matrix you put a column that has a bunch of 0's with a 1 in position i and a -1 in position j. You might think of this as the vector ei-ej where the e's are the standard basis in your vector space. And you're absolutely right, Evelyn, that when you look at the combinatorial dependencies between the graph in terms of graph dependence, they're exactly the linear dependencies in that set of vectors, so in that sense, that vector perfectly models the graph as matroid theory is concerned.

EL: Okay.

FA: So, yeah, that's a really good comparison. One reason that I love matroids is that it turns out that they actually apply in a lot of other different settings. There are many different notions of independence in mathematics, and it was realized over the years that they also satisfy these properties. Another notion of independence that you might be familiar with is the notion of algebraic independence. You learn this in a course in field extensions, and you learn about extension degrees and transcendence bases and things like this. That's the notion of algebraic independence, and it turns out that that notion of independence also satisfies these axioms that Whitney laid out, and so they also form a matroid. So whenever you have a field extension, you also have a matroid.

KK: So what's the data you present? Say X is a matroid. If you're trying to write this down, what gets handed to you?

FA: That's another really good question, and I think it's a bit of a frustrating question because it depends on who you ask. The reason for this is that so many people encounter matroids in their everyday objects that they think of them in very different ways. Some people, if they hand you a matroid, they're going to give you a bunch of sets. Maybe this is the most common things. If you give me a list of vectors, then I could give you the linearly independent sets out of these sets of vectors. That would be a list, say 1 and 2 are independent, 1 and 4 are independent, 1, 6, and 7 are dependent, and so on. That would be a set system. If you asked somebody else, then they might think of that as a simplicial complex, and they might hand you a simplicial complex and say that's a matroid. One thing that Birkhoff realized, and this was very fashionable in the '30s at Harvard, is to think about lattices in the sense of posets. If you had Birkhoff, he would actually hand you a lattice and say that's a matroid. I think this is something that's a bit frustrating for people that are trying to learn matroids. I think there are at least 10 different definitions of what a matroid is, and they're all equivalent to each other. Actually Rota made up the name cryptomorphism. You have the same theory, and you have two different axiom systems for the same theory, and you need to prove they're equivalent. This is something that when I first learned about matroids, I hated it. I found it really frustrating. But I think as you work in this topic, you realize that it's very useful to have the insight someone in linear algebra would have, the insight somebody in graph theory would have, the insight that somebody in algebraic geometry would have. And so to do that, you end up kind of going back and forth between these different ways of presenting a matroid.

EL: Like the clothing that the matroid is wearing at the time. Which outfit do you prefer?

FA: Absolutely.

KK: Being a good algebraic topologist, I want to say that this sort of reminds me of category theory. Can you describe these things as a functor from something to something else? It sort of sounds like you've got these sort of structures that are preserved, they're all the same, or they're cryptomorphic, right? So there must be something, you've got a category of something and another different category, and the matroid is sort of this functor that shows a realization between them, or am I just making stuff up?

FA: I should admit that I'm not a topologist, so I don't think a lot about categories, but I definitely do agree that over the last few years, one program has been to set down stronger algebraic foundations, and there's definitely a program of categorizing matroids. I'm not sure what you're saying is exactly correct.

KK: I'm sure it isn't.

FA: But that kind of philosophy is at play here.

KK: So you mentioned that there was a theorem lurking behind your love of matroids.

FA: So let me first mention one quick application, and then I'll tell you what the object is that I really like.

There's another application of this to matching problems. One example that I think academic mathematicians are very familiar with is the problem of matching job candidates and positions. It's a very difficult problem. Here you have a notion of dependences; for example, if the same person is offered two different jobs, they can only take one of those jobs, so in that sense, those two jobs kind of depend on each other. It turns out that this setting also provides a matroid. One reason that that is important is it's a much more applied situation because, you know, there are many situations in real life where you really need to do matchings, and you need to do it quickly and inexpensively and so on. Now when this kind of combinatorial optimization community got a hold of these ideas, and they wanted to find a cheap matching quickly, then one thing that people do in optimization a lot is if you want to optimize something, you make a polytope out of it. And so this is the object that I really like and want to tell you about. This is called the matroid polytope.

EL: Okay.

FA: Out of all these twelve different sets of clothing that matroids like to wear, my favorite outfit is the matroid polytope. Maybe I'll tell you first in the abstract why I like this so much.

EL: First, can we say exactly what a polytope is? So, are we thinking a collection of vertices, edges, faces, and higher-dimensional things because this polytope might live in a high-dimensional space? Is that what we mean?

FA: Exactly. If your polytope is in two dimensions, it's a polygon. If it's in three dimensions, it's the usual solids that we're used to, like cubes, pyramids, and prisms, and they should have flat edges, so they should have vertices, edges, and faces like you said. And then the polytope is just the higher-dimensional generalization for that. This is something that in combinatorial optimization is very natural. They really need these higher-dimensional polytopes because if you have to match ten different jobs, you have ten different axes you have to consider, so you get a polytope in ten dimensions.

KK: Sort of the simultaneous, feasible regions for multiple linear inequalities, right?

FA: Exactly. But yeah, I think Edmonds was the first person who said, okay, I want to study matroids. I'm going to make a polytope out of them. Then one thing that they realized is there is a notion in algorithms of greedy algorithms, which is, a greedy algorithm is when you're trying to accomplish a task quickly, what you do is you just, at each point in time, you just do the thing that seems best at the time. If we go back to the situation of matching jobs, then the first thing you might say is ask one school, okay, what do you want? And then they would hire the first person, and they would choose a person, and then you'd ask the next school, what do you want, and they would choose the next best person, and so on. We know that this strategy doesn't usually work. This is the no long-term planning solution. You just do what immediately what seems best to do, and what the community realized was that matroids are exactly where greedy strategies work. That's another way of thinking of matroids is that's where the greedy algorithm works. And the way they proved this was with this polytope.

So for optimization people, there's this polytope. It turns out that this polytope also arises in several other settings. There's a beautiful paper of Gelfand, Goresky, MacPherson, and and Serganova, and they're doing algebraic geometry. They're studying toric varieties. You don't need to know too much about what this is, but the main point is that if you have a toric variety, there is a polytope associated to it. There's something called the moment map that picks up a toric variety and takes it to a polytope. In this very different setting of toric varieties, they encounter the same polytope, coming from algebraic geometry. Also there's a third way of seeing this polytope coming from commutative algebra. If you have an ideal in a polynomial ring, and again it's not too important that you know exactly what this means, but there's a recipe, given an ideal, to get a polytope out of it. Again, there's a very natural way that, given a very natural ideal, you get the same polytope, coming from commutative algebra.

This is one reason that I like this polytope a lot. It really is kind of a very interdisciplinary object. It's nature. It drops from optimization, it drops from algebraic geometry, it drops from commutative algebra. It really captures the essence of these matroids that have applications in many different fields. So that's the favorite object that I wanted to tell you about.

KK: I like this instead of a theorem in some sense. I learned something today. I mean, I learn something every day. But this idea that, mathematicians know this and a lot of people outside of mathematics don't, that the same structures show up all over the place. Like you say, combinatorics is interesting this way. You count things two different ways and you get a theorem. This is a meta-version of that. You've got these different instances of this fundamental object. Whitney essentially found this fundamental idea. And we can point at it and say, oh, it's there, it's there, it's there, it's there. That's very rich, and it gives you lots to do. You never run out of problems, in some sense. And it also forces you to learn all this new stuff. Maybe you came at this from combinatorics to begin with, but you've had to learn some algebraic geometry, you've had to learn all these other things. It's really wonderful.

FA: I think you're really getting at one thing I really like about studying which is that, I'm always arguing with my students that they'll say, oh, I do analysis, I don't do algebra. Or I do algebra, I don't do topology. And this is one field where you really can't get away with that. You need to appreciate that mathematics is very interconnected and that if you really want to get the full power of the objects and you really want to understand them, you kind of have to learn many different ways of thinking about the same thing, which I think is really very beautiful and very powerful.

EL: So then was the theorem that you were talking about, is this the theorem that the greedy algorithm works on polytopes, or is this something else?

FA: No, so the theorem is a little different. I'll tell you what the theorem is. Out of all the polytopes, there is one which is very fundamental, which is the cube. Now as you know mathematicians are weird, and for us cubes, a square is a cube. A segment is a cube. Cubes exist in every dimension. In zero dimensions it's a point, in one dimension it's a segment, in two dimensions it's a square, in three dimensions it's the 3-cube, and in any dimension there is a cube. And so the theorem that Gelfand, Goresky, MacPherson, and Serganova proved, which probably Edmonds knew at least to some extent, so he was coming from optimization, is that matroids are exactly the sub-polytopes of the cube-in other words, you choose some vertices of the cube and you don't choose others, and then you look at what polytope that determines-that polytope is going to be a matroid if and only if the edges of that polytope are all of the form ei-ej. This goes back to what you were saying at the beginning, Evelyn, that these are exactly those vectors that have a bunch of zeroes, and then they have one 1 and one -1. So matroid polytopes have the property that every edge is one of those vectors, and what I find really striking is that the opposite is true: if you just take any sub-polytope of the cube and the edges have those directions, then you have a matroid on your hands. First of all, I think that's a really beautiful characterization.

KK: It's so clean. It's just very neat.

FA: But then the other thing is that this collection of vectors ei-ej is a very fundamental collection of vectors, so you know, this is the root system of the Lie algebra of type A. This might sound like nonsense, but the point is that this is one of about seven families of root systems that control a lot of very important things in mathematics. Lie groups, Lie algebras, regular polytopes, things like this. And so also this theorem points to how the theory of matroids is just a theory of type A, so to say, that has analogues in many other Coxeter groups. It basically connects to the tradition of Lie groups and Lie theory, and it begins to show how this is a much deeper theory mathematically than I think anybody anticipated.

EL: Oh cool.

KK: Wow.

EL: So I understand that you have a musical pairing for us today. We all have it queued up. We're recording this with headphones, and we're all going to listen to this simultaneously. Then you'll tell us a little bit about what it is.

KK: Are we ready? I'll count us down. 3-2-1-play.

EL: There we go.

FA: We'll let this play for a little while, and I'm going to ask you what you hear when you hear this. One reason I chose this was I saw that you like percussion.

KK: I do. My son is a percussionist.

FA: One thing I want to ask you is when you hear this, what do you hear?

KK: I hear a lot.

EL: It has a really neat complex rhythm going.

FA: Do you speak Spanish?

KK: A little. Otro ves.

EL: I do not, sadly.

KK: It's called Quítalo del rincón, which, I'm sorry, I don't know what quitálo means.

FA: The song is called Quítalo del Rincón by Carlos Embales. And he was a Cuban musician. One thing is that Cubans are famously hard to understand.

KK: Sure.

FA: So I think even for Spanish speakers, this can be a bit tricky to understand. So do you have any idea what's going on, what he's singing?

EL: No idea.

FA: So this is actually a math lesson.

KK: I was going to say, he's counting. I heard some numbers in there.

FA: Yeah, yeah, yeah. It's actually a math lesson. I just think, man, why can't we get our math lessons to feel like this? This has been something that has kind of shifted a lot my understanding about pedagogy of mathematics. Just kind of imagine a math class that looks like this.

KK: Is he just trying to teach us how to count, or is there more going on back there?

FA: It's kind of an arithmetic lesson, but one thing that I really like is it's all about treating mathematics as a community lesson, and it's saying, okay, you know, if there's somebody that doesn't want to learn, we're going to put them in the middle, and they're going to learn with us.

KK: Oh. So they're not going to let anyone off the hook.

FA: Exactly. We all need to succeed together. It's not about the top students only.

KK: Very cool. We'll put a link to this on the blog post. I'm going to fade it out a little bit.

FA: Same here. Maybe I can tell you a little bit more about why I chose this song.

EL: Yeah.

FA: I should say that this was a very difficult task for me because if choosing one theorem is hard for me, choosing one song is even harder.

KK: Sure.

FA: As I mentioned, I also DJ, and whenever I go to a math conference, I always set aside one day to go to the local record stores and see what I will find. Oddly enough, I found this record in a record store in, I want to say Ann Arbor, Michigan, a very unexpected place for this kind of music. It was a very nice find that managed to explain to me how my being as a mathematician, my being as a DJ might actually influence each other. As a DJ, my job is always to provide an atmosphere where people are enjoying themselves, and it took me hearing this record to connect for me that it's also my job as a mathematician, as a math teacher, also to create atmospheres where people can learn math joyfully and everybody can have a good experience and learn something. In that sense it's a very powerful song for me. The other thing that I really like about it and why I wanted to pair it with the matroids is I think this is music that you cannot possibly understand if you don't appreciate the complexity of the history of what goes behind this music. There's definitely a very strong African influence. They're singing in Spanish, there are indigenous instruments. And I've always been fascinated by how people always try to put borders up. They always tell people not to cross borders, and they divide. But music is something that has never respected those borders. I'm fascinated by how this song has roots in Africa and then went to Cuba. Then this type of music actually went back to Congo and became a form of music called the Congolese rumba, and then that music evolved and went back to Colombia, and that music evolved and became a Colombian form of music called champeta. In my mind, it's similar to something I said earlier, that in mathematics you have to appreciate that you cannot put things into separate silos. You can't just be a combinatorialist or just be an algebraist or just a geometer. If you really want to understand the full power of mathematics, you have to travel with the mathematics. This resonates with my taste in music. I think if you really want to understand music, you have to appreciate how it travels around the world and celebrate that.

KK: This isn't just a math podcast today. It's also enthnomusicology.

FA: Something like that.

KK: Something about that, you know, rhythms are universal, right? We all feel these things. You can't help yourself. You start hearing this rhythm and you go, yeah, I get this. This is fantastic.

FA: What our listeners cannot see but I can is how everybody was dancing.

KK: Yeah, it's undeniable. Of course, Cuban music is so interesting because it's such a diverse place. So many diverse influences. People think of Cuba as being this closed off place, well that's just because from the United States you can't go there, right?

FA: Right.

KK: Everybody else goes there, and they think it's great. Of course, living in Florida there's a weird relationship with Cuba here, which is a real shame. What an interesting culture. Oh well. Maybe someday, maybe someday. It's just right there, you know? Why can't we go?

EL: Well, thanks a lot. Would you like to share any websites or social media or anything that our listeners can find you on, or any projects you're excited about?

FA: Sure, so I do have a Twitter account. I occasionally tweet about math or music or soccer. I try not to tweet too much about politics, but sometimes I can't help myself. People can find that at @FedericoArdila. That's my Twitter feed. I also have an Instagram feed with the same name. Then if people are interested in the music nerd side of what I do, my DJ collective is called La Pelanga, and we have a website lapelanga.com. We have Twitter, Instagram, all these things. We actually, one thing we do is collect a lot of old records that have traveled from Africa to the Caribbean to Colombia to various different parts. Many of these records are not available digitally, so sometimes we'll just digitalize a song and put it up there for people to hear. If people like this kind of music, it might be interesting for people to visit. And then I have my website. People can Google my name and find information there.

EL: Well thank you so much for joining us.

KK: This has been great fun, Federico.

FA: Thank you so much. This has been really fun.

KK: Take care.

[outro]