Episode 90 - Corrine Yap

My Favorite Theorem

Evelyn Lamb: Hello and welcome to My Favorite Theorem, the math podcast with no quiz at the end. I'm your host Evelyn Lamb. I'm a freelance math and science writer in Salt Lake City. And this is your other host.
Kevin Knudson: Hi, I'm Kevin Knudson, professor of mathematics at the University of Florida. How's it going?
EL: All right. Yeah, I was I was trying to think about what to say. And I was like, well, the most exciting thing in my life right now is that our city is starting a pilot program of food waste, like a specific food waste bin.
KK: Okay.
EL: But then I realized I also did an 80 mile bike ride last Saturday, and that's the first time I've biked that far. And that might be slightly more exciting than compost.
KK: Are you working up the centuries? Are you are you heading for?
EL: We’ll see. I felt pretty fine after 80. I also don't feel like I wanted to do 20 more miles. So we'll see. Someday, maybe
KK: The last century I did was, wow, it was 2003. It was 20 years ago. This is one called the six gap century in Georgia. And it goes over six mountain passes in the mountains of North Georgia, one of which has, like, a 15% grade, which is quite steep. It took me about eight hours. And then I hung up my bike and didn't ride it for like three months.
EL: Well, I mean, it would probably take me at least eight hours to do a flat century.
KK: Yeah, but back in my youth I could do a flat century in about five, but not anymore. Not anymore. So let's keep this banter going because I — so Ben Orlin, a former guest on our podcast, I saw Math with Bad Drawings today had various golden ratios. One of which was the golden ratio of hot fudge to ice cream in a hot fudge sundae, which he argues is one to one, but that's way too much fudge.
EL: That is so much fudge!
KK: But the podcast, like, substance to banter golden ratio, he claims is like two to one. So like a third of this should just be like us, you know, just shooting it.
EL: Saying nothing.
KK: Yeah.
EL: Well, I must admit, that's why I listen to fewer podcasts that maybe I would want to because I have a low banter tolerance. Which brings us to our guest today. Yeah, so we are very happy to welcome Corrine Yap today. Would you like to tell us a little bit about yourself?
Corrine Yap: Yes. So I am currently a visiting assistant professor at the Georgia Institute of Technology, Georgia Tech, in the math department. I'm also a postdoc affiliated with the Algorithms and Randomness Center. But I just got my PhD in the spring from Rutgers University.
KK: Congratulations!
CY: Thank you! I do a lot of, like, probabilistic combinatorics, and stuff around that. So that's sort of my main research work. I also do some performing and some playwriting as well. I actually just got back from a performance yesterday Worcester Polytechnic Institute in Massachusetts.
EL: Oh, wow.
CY: So very busy this time.
EL: Yeah. That’s actually one of the reasons that I've been wanting to invite you for a while. And I was like, well, I should wait until I've seen one of her shows. And then it just has not aligned to work out. Because I know you've done them at the Joint Meetings and things, and the times that I have been there and you have been there, it’s just not been a good time. So it's like, well, I'm not going to put this off forever. So even though I have not yet seen one of your shows, I'm very glad that that we could invite you and have you here and yeah, well, can you talk a little bit about the kinds of theater that you do, or kinds of — I don't know if it's mostly theater or more, like other? I don't know, speaking performances?
CY: Yeah. So it really started when I was a lot younger. And also in college, I primarily studied both mathematics and theatre, with no sort of vision as to what that would turn into in terms of a job or career or anything. I just really enjoyed doing both of them. And as an undergraduate I thought I was mainly interested in acting, but I started studying playwriting while at Sarah Lawrence College in Westchester, New York. And I started writing this play, which is the play that I continue to perform. It's called Uniform Convergence. And it's a one-woman play that's about math. It tells the story of Sofia Kovalevskaya, who is a historical Russian mathematician. She was born in 1850. And it tells a little bit about her life and how she faced a lot of obstacles to be successful as one of the first few women in academia. But it also has a portion that is sort of inspired by my experiences being Asian American, and also being a woman pursuing mathematics. And the setting is that of a real analysis classroom, a lecture where the character Professor….
EL: Hence, uniform convergence.
CY: Yeah, and she is lecturing to her students. So at one point, they do reach the point of the class where they do uniform convergence as a topic. So, you know, in the past, I did a lot more — like, in college, I did, you know, the auditioning for plays and being involved in rehearsals, and all this sort of stuff. But since going to graduate school, and now having an actual job, this one play is sort of the main way that I keep my ties to doing theater and the theater world.
KK: Very cool.
EL: Yeah. Well, that's cool. I didn't realize that Kovalevskaya was the subject of this. I actually just read Alice Munro's short story, Too Much Happiness, which is based on her life. And actually was not my favorite short story in the collection that it’s in, but it, you know, she is such a compelling figure and another woman who was interested in math, you know, at a time when it was a lot harder for a woman to have an academic career in any field, and was interested in literature. Wrote, I think both memoirs and fiction?
CY: She also wrote a play.
EL: Oh, wow.
CY: Yeah. But it wasn't about math. But yeah, she was very much also in both of these worlds in, you know, sort of a more artistic, creative mindset as well as a mathematical one.
EL: Yeah. Fascinating person. So yeah, that's really interesting. And hopefully someday I'll get to see it.
CY: Yeah, I'm still performing. I didn't think I necessarily would be. But it's been since 2017. I've been performing it at different college campuses, and sometimes at conferences at different parts of the country. And I still get invited places. So as long as that keeps happening, I'll keep going.
EL: Yeah, when I was still in academia and doing a postdoc, I did, you know, I'd started doing writing. And sometimes I would get invited to do both like a research seminar talk and a public engagement kind of talk. And so that that might be in your future as well.
CY: Yeah, maybe.
KK: Yeah. Broader impacts.
EL: Wearing both hats on one trip.
CY: Yeah, I actually, I forgot I am doing that. I think this is the first time I'm doing it. At Duke in October, when one day I'll be giving a seminar talk, and then the next day, I'll be performing the play.
EL: Yeah, cool. Well, we invited you on here to talk about your plays, but also to talk about your favorite theorem. So what have you chosen?
CY: Yeah, so I've chosen Mantel’s theorem as my favorite theorem. So this is a theorem that is in the area called extremal combinatorics. And I'll explain what that means. But the statement of the theorem is pretty straightforward. It says that if you have a graph, which I’m a combinatorialist, so for me graphs mean, collections of vertices with edges connecting pairs of vertices. If you have a graph on N vertices, then the maximum number of edges you can have without forming any triangles — so just three edges and three vertices connected to each other — the maximum number of edges you can have with no triangles is N squared over four with appropriate floor.
KK: Yeah, sure.
CY: And this seems like, okay, this is this is just a statement, maximum number of edges. What's so cool about that? You actually, we actually also know where the N squared over four comes from. It’s, the extremal example is the complete bipartite graph on parts of size N over two. So what that means is, you split your vertices up into two sets, each of size half the total universe. And all of your edges go between the two parts. So from one part to the other, not inside the vertices of the parts. So complete means you have all the possible edges crossing between the parts, and then bipartite because you have the two parts of the vertices, and that has N squared over four edges. And it has no triangles in it.
KK: Not even any cycles.
CY: Yes. Yeah, no odd cycles. Yeah.
KK: Okay, all right.
CY: Yeah. So, one reason I really liked this is because when I first learned it, I didn't really think much of it, I learned it in an undergraduate class in combinatorics. And there are, like, three, maybe four proofs that we learned that were all pretty short and straightforward. One of the most basic proofs is just via induction on the number of vertices, and there's nothing, there's no really heavy machinery that's needed at all. And I didn't think much of it. And I didn't have any context as to like, why do we care about this sort of thing. But every year, I learn more and more things that make me appreciate this theory, more and more, because it really was the foundation for this whole field that we call extremal combinatorics, which is really centered on these questions of, like, what are the maxima and minima of certain things that we want to count when we put certain constraints on the problem? So this is an example we want the maximum number of edges. And our constraint is we have no triangles. And you can, there are a lot of different directions you can go with this sort of theorem. One of the most sort of classical foundational ones is just to replace triangle with a different type of graph. Like you could say, Okay, if I want the maximum number of edges with no cycle of length four, or cycle of length 10, right, what can I say? Or if I want the maximum number of edges with no complete graph of size five, where complete means you know, the vertices, you have every possible edge between every pair of vertices. And this type of problem, sort of replacing triangle with other things. It's called a Turán type problem, because there's Turán's theorem that generalizes mantle's theorem to complete graphs of higher orders. And we basically know the answer of what the extremal number is, and the extremal constructions for almost every graph, except for when you consider a bipartite graph as your, instead of triangles.
EL: As the thing you're trying to avoid?
CY: Exactly. And there's a reason for this, there's a theorem where it basically fails, or it's trivial in the case that your forbidden graph is bipartite. And so there's been a lot of study, it's still a very active area of research. And what people are doing is sort of taking different flavors of this Turán type problem that sort of started with Mantel’s theorem. And my first paper in graduate school was on a topological version of this theorem, where we were looking at these higher-dimensional structures called hyper-graphs, which you can think of as a higher dimensional version of a graph, and looking at a more geometric or topological viewpoint on these hyper-graphs by making them into simplicial, abstract simplicial complexes. So we don't have to go into the details of that. But I found it, you know, when I did that project, I found it very cool that that we could take this seemingly purely combinatorial, graph theoretic statement about just counting edges, and somehow turn it into something that requires a little bit more of a geometric or topological point of view, which is not something I had spent much time with before. And so that's sort of one direction at the beginning of my grad school career, where I felt like I had suddenly a much greater appreciation for this theorem. And on the other end, where I am now, it's also connecting very heavily to the research direction that I'm currently pursuing, which is in statistical physics, which is for me an entirely unexpected application of this sort of thing. But if you think about it, this sort of characterization of the extremal structure saying, okay, we can achieve the maximum with a complete bipartite graph, you can view this as sort of a ground state, if you will, if you want to think of the vertices as like particles in some sort of distribution, and you can take a probabilistic point of view on these sorts of counting problems. For example, it turns out that the triangle-free graphs and the bipartite graphs, if you think of these two collections, triangle-free graphs and bipartite graphs on N vertices, they're very closely related to one another. In fact, almost all triangle-free graphs are bipartite. This is a theorem by Erdős, Kleitman, and Rothschild. So you can sort of ask how far does that behavior persist if you add more constraints to your problem? And you can think about it as in a probabilistic sense of thinking, well, what if I have a probability distribution on my triangle-free graphs? And I have a probability distribution on my bipartite graphs? How are those distributions related to one another? And what is the counting statement, say, in terms of the probability distributions when we when we consider a randomness point of view on these things. And the sort of magical thing is that when you go to a probabilistic point of view, there are very natural ways that you can put it into a statistical physics context, where in statistical physics, you are thinking inherently about probability distributions on certain particles, on particles in space, or different configurations of particles in space, where there's maybe a physics motivation underlying the distribution you define. But ultimately, you can distill it down into something that is, that is simply triangle-free graphs, or different discrete structures. So one thing that I'm really interested in right now is just exploring more of this somewhat mysterious, but somewhat really amazing connection between questions that arise in graph theory and combinatorics that, you know, for a long time, we have just thought of in that context, in the graph theoretic context, and how, looking at them from a more statistical physics perspective, can help us gain new insight into how to tackle these problems.
KK: Yeah, and hopefully, it'll go in the other direction. I mean, I think we have this idea that because we learn calculus, and we think about physics being based on calculus, but inherently, right, the universe has to be kind of discrete, so you can't divide stuff forever. So I mean, it sort of makes sense that the underlying business, when you get down to it, might have to involve some kind of graph theory questions.
EL: Yeah, that is remarkable that there's this connection. So this is maybe a naive question about what you're talking about doing. Like probability distributions on graphs, are you saying things like, the likelihood that that two vertices have an edge between them? Or are we talking about some other kind of probability distribution?
CY: Yeah, so there, I purposely didn't include too many details, just because there are a lot of a lot of actually interesting and all valid ways that you can think about imposing probability, you know, into this world into these problems, these extremal combinatorics problems. So one flavor is what you said, we can think of what's called the random graph model. The most common one is the Erdős–Rényi random graph model, where you simply have your N vertices, and for each pair of vertices, you flip a coin, and it can be a P-biased coin, independently, to decide whether you put an edge there. And you can analyze what happens in that graph. What are the likely properties that this graph might have, if you, for example, change P. And what's really cool about studying this model is that there are, for a lot of graph properties, you can find these thresholds with respect to P. And this is like a huge, very active area of research right now, there have been a lot of really cool things proven just this year, in the past few years with regards to a lot of open questions here. But you can sort of if you let your P, your probability that you're adding an edge, be a function of N, the number of vertices, and you imagine N going to infinity, then you can actually sort of chart what happens if you're trying to count, let's say, the number of triangles in your graph, the expected number of triangles in your graph, or other properties. And you can see how changing P changes the value of the thing that you're trying to count. And for a lot of things, they exhibit these thresholds where the probability of finding a particular structure is close to zero. And then past a certain threshold, it jumps up to something close to one, and it happens with high probability. And this is also mimicking something in the statistical physics world where we have things like phase transitions.
KK: Right.
CY: If you think of in physics, just like water’s liquid-gas sort of phase transitions. Where we're also interested in studying what happens to certain properties of your statistical physics distribution when you change the temperature of your different parameters of your model. Can you find the sort of phase transition where the behavior changes quite drastically?
KK: Yeah.
CY: And then so GNP is, is one of these ways you can sort of input probability into — you know, take a sort of probabilistic perspective on these problems. Another is simply something a little bit more physics motivated, is by just imposing a uniform, or nonuniform, or a weighted distribution on the things that you're trying to count. For example, if you want to study triangle-free graphs, you could consider the uniform distribution on all triangle-free graphs on N vertices. And then think about the uniform distribution on bipartite graphs and ask, like, are these distributions close in total variation distance? And you can conclude things about that based on what you know about how close are triangle-free graphs and bipartite graphs to one another? Well, what does that say then about the distance between the nniform distributions that you impose on each set? And that sort of thing characterizes the different sort of distributions that come from the perspective of statistical physics. There are things called, like, the Ising model, and the Potts model and the hardcore model that were defined by physicists. And it turns out that they are simply weighted distributions on things like graph colorings, and independent sets of graphs. And so you can study them in these two different contexts, in the context of the hardcore model from the physics world, or in the context of a distribution on independent sets from the graph theory world.
KK: The hardcore model, I love that name. That’s good.
CY: Yeah.
KK: Well, we’ve gotten pretty far away from triangle free graphs can have at most N squared over four edges. So you mentioned that there were like three or four proofs of this. Do you have a favorite?
CY: I have to say my favorite is the very straightforward induction proof.
KK: Okay.
CY: And the reason I like this is because it's a proof that I've done with high school students at a summer math program I teach at called MathILy-Er. And I do it as an hour-long inquiry-based activity, where I simply pose to them this question. I let N be something like six or five, something that they could start drawing examples for them, then say, how many edges can you have before you start having to find triangles? And they often come up with the extremal construction, the complete bipartite construction first. And then I asked them how can we prove that this is actually true that this is the maximum. And they've learned induction at this point, when I do this activity. And so it's a nice lesson in induction, because it requires strong induction. And everybody wants to do weak induction, first of all, and they always want to what I call induct up instead of induct down. They always want to start with an extremal example with N vertices and try and build something with N+1 vertices. And it doesn't work.
KK: Right.
CY: And I always have to remind them, you have to start with something that has N+1 vertices, and remove something and see what happens. Yeah, yeah.
KK: And the base case of one vertex is super easy, right?
CY: And then there's also some argument about how many base cases we need and whether we need one or two or three, or where do we start? And so I think it's just a really nice exercise and practice. And it's simple, but I get to give a little, tiny spiel at the end, not nearly as much as I have said here in this podcast so far. But a tiny hint as to like, you know, what's cool about this theorem, and what more could you do? And some of the students have been interested enough to try and generalize to complete graphs or higher orders, you know, a complete graph on four vertices and try and mimic the same proof. And yeah, I think it's a really nice activity.
KK: Cool.
EL: Yeah. So a complete graph on four vertices includes a complete graph on three vertices so therefore you're trying to avoid something more, so like some of these ones that have triangles could still not have the four. Sorry I'm thinking out loud here because I have very little graph theory intuition. So okay, just like which direction are we going, and how many of these are we avoiding?
KK: You and I are probably the same, Evelyn. Like, we probably took one undergrad graph theory course and then yeah, and then then became topologists.
EL: Right. It’s kind of like it came up in, my introduction to proof class, but never a specific class dealing with graph theory things. Although the times that I've taught in high school programs or stuff, it is the kind of thing that can be quite accessible because the idea of drawing a graph, it's not hard to explain to anybody.
CY: Yeah, to answer your question. So there are actually lots of triangles in the extremal example for the complete graph on four vertices.
EL: Okay.
CY: Just to give you a sense of how it generalizes, the extremal example is the complete tripartite graph where you take three parts now sides and over three, and you have all the edges between the parts, so it looks like a giant triangle.
EL: Yeah. This kind of makes me want to go think about graphs a little bit. Yeah.
KK: Well, so the other part of this podcast is we ask our guests to pair their theorem with something. So what do you think pairs well, with with this theorem?
CY: So yeah, this this question was actually harder for me.
KK: It’s harder for everybody!
CY: I thought of something right away. And then I thought, no, I can't say that. I have to say something cool. And my pairing has to be something neat that makes me seem like a cool person. But I just couldn't think of anything better. So bear with me.
KK: Okay.
CY: My pairing is tofu. Okay. And here's why.
EL: Oh, tofu is great!
CY: Yeah. Okay, great. Great. So I thought of this because I think tofu is also somewhat of an underrated ingredient. But it is also so versatile, and you can use it in so many ways. So I grew up eating a lot of tofu because I grew up in a Filipino-Chinese household. And it was just sort of a staple of the things we were eating. But then I realized that not everybody knows or appreciates tofu. The first time I met someone who had never heard of tofu before, it just sort of shocked me, but then I realized it's not a common thing everywhere. But it's used in so many ways. And so I have been vegan since 2015. And also, every year I gain more and more appreciation of tofu as an ingredient. Like, you can use it in stir fries. There's now cheese that's made of tofu, you can make eggs using tofu. You can make a pie using tofu. There are so many ways you can use tofu. And there are so many more vegan options at restaurants and grocery stores and everywhere. So I feel like you know, for anyone who hasn't had tofu before, I would recommend at least giving it a shot.
EL: Yeah, yeah. And yeah, I mean, I grew up in a household that did not eat tofu much, my parents don't eat too much. But yeah, I'm not vegetarian or vegan, but like eat a lot — we have recently been enjoying this vegan Korean cookbook, I mean, it's called Vegan Korean. You might have seen it. [Editor’s note: It’s actually called The Korean Vegan.]
CY: Yeah. I have that!
EL: And just checked out this vegan Chinese cookbook that of course, it's like I think multiple sections are tofu because it's like the tofu tofu part and the tofu skin part, and all of this stuff.
KK: And, you know, do you use silken or what.
EL: But yeah, we’re a high-tofu household now.
CY: Nice. Yeah, there are so many different levels of tofu that you can have.
EL: Yeah, so many different textures, like, the Korean soft tofu is different from like the soft tofu in the cardboard package. Yeah, and so I finally found a Korean grocery store in Salt Lake that I could get to and got, like, the real stuff and oh man, great. That soft tofu soup, so good. And I can actually eat the kind I make because when I get it at a Korean restaurant, it's way too spicy. So I cut — in that cookbook, I think I cut at minimum, sorry, maximum spiciness is, like, a third of what the recipes start with, sometimes a sixth and see if I can work up.
KK: The correct answer level and there was you know, N squared over for, the floor.
EL: Yeah. I am impressed by the spice tolerance of Koreans.
KK: Asian cuisine in general, we once years ago, I was director of the University Honors Program, there was this place in town. It was an Asian place, and they have various stir fries. And you could ask for your spice level from zero up to no refunds, right? And so we had a student worker who was from Bangladesh, we went to lunch there one day, and he got the “no refunds.” And we were like, how is it? And he just went, eh. Like, it's just not very hot. And it's just an interesting cultural thing. Because, you know, I grew up in the Midwest, my mother's family was German, you know, we ate a lot of fried potatoes and sausage, like no flavor, you know? And it's just all what you get used to. Right?
CY: Yeah.
KK: All right. Well, this is we like to give our guests a chance to plug anything. Where can people find you online? Or you've talked about your plays, so that's good.
CY: Yeah. I mean, you can find my website. I recently updated it. And now it's got an all-purple background, which I'm very happy with. And it's corrineyap.com. That's Corrine with two R’s and one N, in case you forget. And, yeah, I continue to perform my plays. So if you're ever interested in bringing me out somewhere to perform, I am always happy to consider doing that. And I've done it at a lot of math departments. I did it at some conferences, but I don't have any conference performances coming up. So mainly like seminars and colloquia slots, things like that. So Evelyn, if you have any universities around you in Salt Lake City who might be interested in hosting a performance, you can let me know.
EL: Yeah. I'll make you vegan Korean food.
CY: Oh, amazing. But yeah, I mean, I just do this for fun. So it's not something that I'm trying to, I'm not trying to schedule, you know, 100 performances on my show this year. I just do it whenever someone is interested in having me there, but I'm always open to new inquiries. So yeah, that's, I guess, the one thing that I'll plug.
EL: Okay, great. Well, it was lovely to have you I'm so glad we finally got to at least meet online.
CY: Yeah, you as well. Thank you. Thank you so much for inviting me. This is a lot of fun.
KK: This was great.
[outro]

On this episode, we enjoyed talking with mathematician and playwright-performer Corrine Yap about Mantel's theorem in graph theory. Below are some related links you may find interesting.
Yap's website
MathILy-Er, a summer math program for high schoolers
Wikipedia on Turán's theorem, the generalization of Mantel's theorem
The Korean Vegan