Episode 67 - Liz Munch

My Favorite Theorem

Kevin Knudson: Welcome to My Favorite Theorem, a math podcast with no quiz at the end. I'm Kevin Knutson, professor of mathematics at the University of Florida. I am joined today by your fabulous and glorious other host.
Evelyn Lamb: Hi, I'm Evelyn Lamb, a freelance math and science writer in Salt Lake City, Utah. And I assume the “fabulous and glorious” means my new haircut, which I actually got professionally cut for the first time in quite a while recently.
KK: Good for you.
EL: I had been playing around with, you know, scissors — not official hair cutting scissors, just you know, the scissors that are lying in the kitchen drawer — and, like, my clippers and stuff for a while, but I went in and I look very sleek and chic right now.
KK: You do. You look very sleek. I’m getting a haircut tomorrow, I look less sleek.
EL: Not too bad, though.
KK: You know, I still have the plague beard though. I don't know, I can't decide what to do about that. And my hair has gotten longer, but you know, thinning, and I don't know what to do anymore.
EL: My husband actually decided to try for the ponytail. So he had been very excited about, like, two weeks after the second shot going and like getting a real haircut for the first time in a while. And then by that time, it was long enough that it's almost ponytailable. So he's like, “I've never had a ponytail. I think I want to try this.” So so now we're like at opposite, you know, going in opposite directions.
KK: I have a ponytail and my wedding pictures and then that’s the last time.
EL: Okay.
KK: Anyway, today we are pleased to welcome our good friend Liz Munch. Liz, you want introduce yourself?
Liz Munch: Hi. Yep, so I'm Liz Munch. So I am an assistant professor at Michigan State University. I'm in the departments of Computational Mathematics, Science, and Engineering, which is a mouthful, but we just say CMSE. And I'm also in the Department of Mathematics.
EL: All right, and what is your recent hair story?
LM: It’s the kind of, like, what can I do rolling out of the shower to like, make it do anything? And it's kind of like, wherever it lands. I did get a haircut, though, recently. It was very exciting. I had — it was getting so long that it was going out of control. And usually what happens is I I go get a haircut and I do like extreme versions. I'm like, “I hate my hair!” And then I chop it off to my ears. And then I grow it out again. And then “I hate my hair!” and I chop it off to my ears. This time, she convinced me not to chop it off all the way, but I'm due for one. So we're gonna work on getting that one soon.
KK: Looks good. Looks good. Yeah. So CMSE, that's interesting. You have this joint appointment. How's that? Yeah.
LM: I like it. It's different. So at least for me. So I do very interdisciplinary math, very applied math, but not your usual applied math. And so for me, it's a it's a really nice setting to be in. So CMSE is — so the faculty in CMSE are all sorts of different backgrounds. So there are mathematicians, but there are also statisticians and biostatisticians and biologists and plant biologists and geologists and physicists and engineers, and I'm sure I'm forgetting people. But it's basically rigged to be interdisciplinary. And so it's made a lot of fun, because you can find these interesting projects that are sort of in the intersection of complicated math and interesting stuff to do there with applied projects I would never have thought of before. So at least for me, that's been a really good fit for trying to do interesting applied math research explicitly outside of the usual academic silos.
KK: Yeah. Well, that's nice, because I think a lot of us in math departments often want to engage in these activities, but you know, the physics department’s in another building, and it's more effort, right? You know, it's true, there’s this idea of these collision spaces. So you know, if you have colleagues in all these different disciplines just right down the hall, it might lead to more interesting stuff. So that's a nice model. I wish we could do more of that. Anyway. So you have a favorite theorem, I hear.
LM: I do have a favorite theorem.
KK: You going to tell us what it is?
LM: I was going to talk about max flow min cut.
KK: Okay.
LM: Which is sort of my, I don't know — so the reason I like max flow min cut, is partially because, again, I do interdisciplinary applied mathematics, and I tend to fall into the theoretical computer science land a lot, just based on a lot of things we want to do. Because I work in TDA, topological data analysis research, and so a lot of things come down to here's a complicated thing I want to compute, and I’ve got to go figure out how to do it in a computer in a reasonable amount of time. So this is an example of that.
So max flow min cut. So here's the game. So you get yourself a directed graph. And this graph has a source and a sink. So you've got your S vertex source and your T vertex sink. And you essentially have capacities on each of the edges. So my directed edges, I now have an amount of stuff I can push across the edge. So I like to think about this with, like, water tube flows kind of thing, right? So I've got how much capacity each of the edges can take. And so the game is, try to see how much stuff you can push along from the source to the sink, basically playing nice with those capacities, so flowing from one side to the other. So if you're at any vertex, all of your inward flow amounts should be equal to all of your outward flow amounts, because you can't have anything hanging out at the vertex. And so your other restriction is your flow values — this is essentially like a second choice of weighting on all your edges — your flow values have to be less than your capacity values, right? So you can't flow more across an edge than the capacity allows.
KK: Sure.
LM: And so the trick is, what's the most amount of flow you can get across? I hand you one of these graph setup problems, what's the most flow you can get across these things? So the max flow min cut, as the title would suggest, is that you also need to know something about the minimum cut. So what's what's a minimum cut? So same starting input information. What you can do is you can try to divide your collection of vertices into two piles. And the rule is that you have to have your source in your sink in different piles. And the cost of whatever choice of piles has to do with, essentially the cost of the capacities that go from one pile to the other, right? So you sort of add up those values, there's some negatives if things are backwards, etc. But that's the cost of a cut.
KK: Okay.
LM: And so the game with that part of the problem is you want to make that as small as possible, right? Can I reorganize these vertices in such a way to make that cut cost low? And so the max flow min cut theorem says the capacity of the highest possible flow value is equal to the cut, the minimum possible cut value you could get. And so this is cool, because this means that you could answer your problem either by going and hunting for a maximum flow value or by hunting for a minimum cut value. And so it gives you two very different ways of looking at this problem to try to solve something. And these show up in all sorts of different application settings, right? So you can imagine, like, railway networks, where you're trying to move stuff around, you could try to do things with electric grids, and you can do things with water flow. There are lots of places where this thing would show up. And so having access to two different ways of looking at the problem is super useful.
EL: Yeah. So I have never thought about this before. So I'll just kind of — I’m not even sure if I can formulate the right question. But I'm trying to think, my mind immediately goes to extremes. So like, if you put everything except your source in one pile, or everything except your sink in one pile, is it obvious that usually that's not going to be good?
LM: I guess it kind of depends on the sort of setup you have, right? So I guess the simplest version would be like, okay, let's start with a graph that's just a path, right? And so in that case, I can stick a bunch of random numbers as capacities on my path, and so the maximum flow I can get across this path is going to be something like the minimum weight capacity that I've got, right?
KK: Yes.
LM: That minimum weight capacity is also going to be if I chop my path graph in half at that particular edge, that's as low as my cost for my path can go.
EL: Sorry, just to slow down a little bit for me. So that capacity is like, this one edge can only hold, you know, whatever amount of whatever stuff?
LM: Yeah.
EL: Okay. Great.
LM: This is kind of like the bottleneck in the system, right? Like I could have pushed, like, 30 gallons back here. But if this particular tube only allows for five gallons, it doesn't matter how much I can push in the backend, right? It's got to be, it's limited by this one, right?
EL: Yeah.
LM: And so then you basically take that, that path problem and scale it up. So then you've got all these other possible paths where you could push stuff through. You could imagine a vertex where you have, like, a capacity of 10 coming in, and maybe five edges coming out. And so your flow could be 10 in and then it got split up and there's all sorts of things. And so the way you prove this, so this is the Ford–Fulkerson algorithm from the 1950s, I think? It basically comes from looking for paths like that. So the whole problem comes down to basically that path example I was giving you. So you essentially rig up this modified version of your graph, and then look for paths from your start to your sink, where you try to see places where I could push some amount of flow across that line, across that path. And what you do is you essentially update some sort of flow that you're trying to build as big as possible. So if I've got a path where the bottleneck value was five, I now push value of five across each of the edges in that path. And then I update this other graph I can use to keep track of things. This is called a residual graph. Basically, then I update this flow, and then I go look for a new path. And then I update this flow, and then I look for a new path. And it all comes down to just finding these paths that have some sort of bottleneck in them and updating accordingly.
KK: That seems slow.
LM: Oh, yeah. Oh, yeah. This is not nice.
KK: So there must be better algorithms for doing this. But that’s the easiest to explain algorithm?
LM: Yeah, right, easiest to explain, and the one you get the proof off of. So that's the the Ford–Fulkerson one. And of course, I did not check this beforehand, but I believe the running time has something to do with the value of your maximum flow. And there are some caveats in here. So if you have integer-valued flows, so I'm only allowed to put integers on each of my edges, that process will terminate, which is a good sign, right? It will terminate at the best possible flow, which is a good thing, right? And worst-case scenario, you basically updated by one every time, and so the the order of the number of times you have to do that update procedure has to do with essentially the maximum flow value.
KK: Okay.
LM: So yeah, it's not pretty, but it works. This is another one of these examples where in practice, it tends to not be that bad. But of course, you can construct the nasty examples.
KK: Sure. Right. So yeah, the theory is bad, but the practice is good. So that's fine.
LM: Yeah.
KK: So do you use this much? Does it come up for you?
LM: I haven’t in a long time. The reason I was thinking of this was a while ago, I was teaching this summer program for bright high school kids, where we were doing a topology class for high school kids that basically have seen calculus. And so one of the reasons I like this was I was remembering I had rigged up this thing where I created a graph on the ground. And I put capacities on it involved in the — sort of like, I don't know, I think it was squares of paper or something like that — and messing around with getting them to actually manually push stuff around on this graph and start thinking about flows and how you can update information. Yeah, it hasn't come up in my research recently. But I think in general, just the messing around with problems where you can have multiple ways to find a solution, that's been really interesting lately, because trying to rig, trying to look at a problem from a different angle where you might have an easier ability to go solve something than something else, right? So like, if you told me go find the minimum cut in this particular graph, the knee jerk reaction is like, “Okay, let's test all possible ways of splitting the two piles!” which you really don't want to do, right? Bad idea. Never do that, right? And I don't have any good intuition for how — if you had to be that problem, I would start going at any sort of algorithm that would get me anywhere. But because we've got this duality idea, right, I can go back and do this pushing flows through a network thing that gives you access to a way to solve a problem that wasn't there before.
EL: Nice. And so do you remember, like really loving this theorem when you first saw it? Or is it something where your appreciation has grown over time?
LM: Ah, there's probably — now I;ve got to remember where I saw it. I'm going to guess I saw it in an algorithms class in my PhD. Yeah, I don't know. I don't know that I appreciated it at the time. I feel like a lot of the beginning of my math career was like, “Okay, this theorem exists, but I'm not sure why I care.” Right? It's taken me much longer to start getting to the like, “Oh, the point is the duality. The point is accessing a problem from different sorts of viewpoints.” And having the ability to sort of question the vantage that you're looking at something from because there might be a better way of doing something. And “better” here is now a subjective term, right? Like, mathematically, the theorem says, I don't care. But practically, right, there is a better and a worse way of doing something. And so you're going to end up having choices, as you go about doing math research, that are going to be better or worse in a practical sense,
KK: So it's clear listening to you that you work in an interdisciplinary environment, right? Because, you know, the mathematician loves the duality, but you know, practically, the engineer wants to find the most efficient way to do it. Yeah, very cool.
EL: So I wanted to come back to something you said a little while ago, and I think it just percolated through my brain. So you said that, like, if your your capacities on these are all integers, then the process terminates. And the fact that you needed that “if” actually just made me really nervous. So is it the case that if you don't have integers, and possibly even rational numbers or something like this? So like, maybe if you had like a bunch of irrational or transcendental values on these, that it might not terminate? And then you’d be sad.
LM: Yep, yep, yep. Yeah, then you'd be sad.
EL: Or maybe you would be sad. I don't know.
LM: Well, yeah. Okay. So I actually, I'm not sure of the answer if it's rational. I know that if you allow irrational values on the edges, you can definitely have examples that don't terminate. And basically what ends up happening — okay, so the way it is pushing the flow through your residual graph, there's a setup that allows you to essentially undo pushing through edges. So these residual graphs get this sort of backwards edge that's added to them. There’s the flow that you've already pushed through that you could undo and the flow that's available, which is the capacity minus the flow that you've done to this point. And so finding a path in this graph could push new stuff through, or essentially undo pushing things through and move it to some other path in your graph. So what ends up happening if you — again, if you create incredibly contrived examples — is that finding these paths in this graph can keep updating and then undoing the update. And you end up with this vicious cycle where you kind of like spin stuff around in circles, and you just never get there. And it's got all sorts of weird behavior, like not only it, like, doesn't decrease, it doesn't convert, like, it's, it's all kinds of nasty.
KK: Right? I would imagine with rational, though, you can do the standard trick of just scaling everything to be an integer. Like, that's probably okay.
LM: Oh, yeah. Because especially if you've got a finite starting graph, yeah. Yeah. Right.
EL: Oh, “if you've got a finite…” you're putting all these “ifs” that I wouldn’t even think you’d need!
LM: Let's have everybody be finite before I say something false.
EL: That’s fine with me.
LM: I am going to bet somebody thought about that.
EL: Oh, I'm sure. But, you know, since you started saying this with water pipes, I just immediately thought of, like, okay, a city water system. And I just know that that is finite. So yeah, in my mind, this is always going to be finite.
KK Right. And you'd sort of create one source by having it all come in your case, Evelyn from the Wasatch, right?
EL: Nice job.
KK: And then it all goes to the water treatment plant. That's it. That's your whole, you’ve got this crazy network.
EL: Or that eventually to the the Great — the Lessening — Salt Lake as it dries out.
KK: Yeah. All right. So also on this podcast is, we ask our guests to pair their theorem with something. And you mentioned what it was going to be ahead of time and I'm really intrigued. So let's look. What pairs well with max flow, min cut?
LM: Okay, so we're gonna pair this with the cross-strung harp, which I promise is going to make sense. So give me a moment. So just for some backstory, so my undergraduate, I was actually a harp performance major. That was my previous life. And I sort of backdoored my way into the math department.
EL: So I have to interrupt say that my sister is a harpist, was a harp performance major, is now working on a PhD in music theory, but teaches harp and has a harp studio and yeah, that’s such a cool coincidence.
LM: You probably might already know some of the stuff I'm about to say. So that's super exciting. Because, yeah, most people you talk to have no idea what I'm talking about. This is great. Yeah. So I spent the first part of my professional life, I was going to be a professional harpist. I got about halfway through and was like, “No, that's not for me.” I got into, started taking math classes. Ended up in a math PhD program, unbeknownst to me. And here we all are, right? Yeah, so the thing with harps is if you look at a regular harp, what you're actually looking at are, like, the white keys on the piano. So no chromatics, no sharps and flats. It's basically in one key, right? So there was an issue in, sometime around the 1800s, where they were trying to figure out how to make a chromatic scale possible on a harp. So prior to that, there was sort of a trick where you could put things like levers on each of the strings and they would shorten each string by a little bit. And so you could basically get, if you tuned your string in natural, you could get the sharp. If you tuned your string flat, you could get the natural, but that was it. So you could do the key of B — the key of F and the key of D, and then things got hard. And so in the 1800s, they were trying to figure out how to deal with this problem, and so there were two solutions that showed up at about the same time. So there was the cross-strung harp, which is not what you've seen before, and the double-strung harp which is what you've probably seen before. So if you go to an orchestra concert, somebody most likely has the cross-strong harp, or sorry, a double action harp, which is, you have two sets of essentially these twisty peg things that go on top of the string. And so now you engage a pedal, and the pedal, if you push it down once it engages one of these twisty bits, and if you engage it a second time, you get two of them. And so now you have three notes on every string. And so you tune it in such a way that now you've got flat, natural and sharp on every string.
EL: And there was much rejoicing.
LM: And there was much rejoicing, right. So this was invented by a watchmaker who was trying to solve this problem, because the mechanics of this are absolutely nuts. Like, I don't even know how the inside of my harp works. At the same time, so there was another option that was starting to show up, which was the the cross-strung harp, which was literally — you're going to have to Google this later — but it looks like two harps with two sets of strings that meet at an X in the middle sort of interlaced.
EL: Whoa!
LM: Yeah. I've seen these things. My brain goes fuzzy. Like, you can't focus on any of the strings, right? But the idea is that now you can move your fingers up or down to get sharps and flats. And so now you have access to all the strings. And it involves different techniques and things like that. And so there were these two companies. So it was Erard at the Erard company. So Erard was the watchmaker that invented the double action harp. And the Pleyel company had invented the cross-strung harp, and they were fighting about who was basically going to win the business.
KK: Harp domination.
LM: Yeah. There's some there's some catty stuff in the harp world, let me tell you. And so each of the companies, so there are actually two very famous pieces for harp that were commissioned by each company to prove that their harp was better. And so the Pleyel company, commissioned the Debussy dances, and the Erard company commissioned the Ravel Introduction and Allegro. And these two pieces are basically made to be — I'm not going to say easy, but like, manageable on your harp and not good on the other one, right? Right, so fast-forward 100 years, and the double-action clearly won out, right? So that's what everybody has now. But we still play both pieces. So if you go to college for harp performance, you're going to play both. And so the Ravel isn't, you know, again, it's not easy, but it is manageable, because you are playing it on the instrument it was written for. And then you get to the dances. And it is a combinatorial nightmare, because basically, what you're trying to do is figure out these fingerings, and how to play these different chromatic notes at the same time, when you don't have access to the other set of strings. You are now limited to trying to play the note on another string that you might have needed a half a second ago to do whatever.
So I promised that this was going to come back to something that made sense. So the whole point of this is that I was thinking of the cross-strung harp because it's one of these two solutions for the same problem. And not necessarily that one of them is better than the other, but in certain cases, there is definitely a priority. One of them really, truly did better.
EL: Yeah. That's so cool. And I have to ask one more question about the cross-strung harp. I don't want to totally derail this, but I'm going to slightly. So you know, when I watch my sister play like her right hand, you know, as on one side of the strings that are left hand is on the other. So with the cross-strung harp, then, your right hand and left hand — if you were playing, like on the diatonic, would have one would have to be up and one would have to be down, right? Because the strings go…
LM: Yeah. I will admit I've never played one.
KK: You’d switch them, right?
EL: Yeah, like if you move to flats, you move like this.
LM: You kind of want to be able to do both at once. So your technique would change entirely. I don't actually know how you would deal with this. If you want to Google even more things, there’s also a thing called a Welsh triple, and the triple — so what this is is now, this will make your brain hurt if you try to look at this thing — it’s now three rows of perpendicular vertical strings. So instead of being crossed through the middle, they’re, like, up, straight up. And so now you've got white notes on the outside, that are spaced wider than a normal harp, with sharps and flats down the middle. And so now you have to reach through the strings to try to grab.
EL: That seems bad.
LM: Oh, and I’ve played one of those too. And it's like your eyes just can't focus. Like I can't decide which layer of strings to be looking at. It was it was rough,
KK: But I'm sure that's mostly a function of having grown up playing the one that you play.
LM: That’s true.
KK: If you grew up playing the cross-strung or the West triple, that would just feel absolutely, totally natural.
EL: Yeah, but I guess you'd have to do something for visual markers, like so the harp has, is it the F and C strings are a different color to help you? Because on the piano, you can look at where the black keys are, and that tells you what notes you're playing. On the harp if they're all the same color, it's just a nightmare. And I guess on the Welsh triple, maybe you'd have to…
LM: I don’t remember what the coloring was on the Welsh triple. Yeah, on a modern harp, C’s are red and F’s are black. And then if you get older strung harps, they used to be switched, and that also makes my brain hurt.
EL: Oh no!
LM: It’s very much what you're used to.
EL: Yeah. Well, that's so cool. And what a funny coincidence that you’re harpist, just like my wonderful sister.
LM: Hi to your sister.
EL: Hi, Rachel!
KK: Do you still play much?
LM: Oh, not much anymore, unfortunately. I've moved my harp around to multiple cities and houses. Yeah, so I basically, I kind of put myself through grad school playing weddings. So that was nice. And then after, you know, kids and everything else, it's just kind of turned into less so.
KK: Well, you’ll come back.
LM: It might come back.
KK: Yeah. As someone who's now an empty-nester, I can tell you it does happen. So the other thing is, you know, my kid’s about to go off to grad school for music composition. So apparently just like Evelyn’s sister, he’s going to go be a theoretical musician, I guess. He's a percussionist, though, you know, and I can't understand how he plays drumset right. That’s, like, two arms and two legs, doing four different things. But harp sounds pretty bad too.
LM: Yeah, I thought I had to move around a bunch of stuff. They are so much worse. They got, yeah, that was that was always the trick. So when I was in college, the harpists saw got our own practice rooms, so we didn't have to move the harps around. Everybody else had to, like, fight for it. But the the percussionists also got their own practice rooms where they got, like, nobody wants to move around, you know, the xylophone.
KK: Yeah, although I've certainly moved Gus’s drum kit plenty of times.
LM: Oh, yeah. No, if you've gotten to the point that you've bought vehicles based on your instrument…
EL: Yep. I was going to say that's Rachel’s, I think Rachel has taken a harp to a car place to, like, test in the lot to see how easy it is to load.
LM: I have done that. I've purchased vehicles entirely because it could fit my harp in the back and I've confused — oh my goodness, I love showing up to car dealerships like this. It's my new favorite thing.
EL: Yeah. So before we end this episode, I just had — I didn't get a chance to say this earlier. But Max and Min can both be names, and I just feel like max flow and min cut just sound really snappy and sound like either a superhero duo or maybe, like, superhero antagonists or something. I’ve just got to put this idea out there for like, you know, a graphic novel about Max Flo and Min Cut.
LM: I want to read that book. Absolutely.
KK: Or Max Flow sounds like a news reporter from the ‘20s. You know, like His Girl Friday, right? You know, Cary Grant and Rosalind Russell or Max Flow and Min Cut in there. Yeah. So we also give our guests a chance to plug anything, or where can we find you on the line or …
LM: Oh, I definitely should have thought of that in advance. I don't know. Come see MSU. I like her. I like our new department. That's probably the first thing I should plug. I'm on Twitter more than I really should be. So you can always find me there. [Her handle: @elizabethmunch] That's — Yeah. I love Math Twitter. It's a happy place.
KK: Mostly.
LM: Yeah, I think that's mostly it. The other thing I guess I should plug is, so I'm very involved in the women in computational topology network. So if anybody is interested in anything in that general direction, so this is a group for not just women. So we're aiming for a broader community of gender minorities and a place for people to do math in a supportive environment because that, in my opinion, is the reason I am still here, and so I want to create that for other people.
EL: Cool, yeah.
KK: I can verify Liz is well-known for her no assholes rule.
LM: I yes — oh good, we can swear on this podcast.
KK: Sure. Why not?
LM: You just did. I do have a tendency to curse like a sailor, and so my husband before I started this was like, “Remember, Liz, you need to not swear on that.” I was like, “Okay.” I have a very strict “does not collaborate with assholes” rule. And it is gotten me very far in life and made for much better research.
KK: Life’s too short not to have that.
LM: Exactly. Yeah, exactly.
EL: So now are we going to go back and rerecord, like, the swear version of max flow min cut? Just kidding.
LM: Now that I'm allowed to curse for the whole thing?
KK: It’s pretty light swearing.
LM: You’ve got your R rating, don’t worry.
KK: No, no, no, R rating requires f bombs.
LM: See? We’re doing okay.
KK: So PG— so movie ratings for PG-13, you’re allowed one f-bomb. If there's more than one it gets an automatic R.
LM: Good to know. So we’ll hold off on the f-bombs, just in case this turns into a movie.
KK: That’s why you don't hear it as much in PG-13 movies because they they deliberately leave them out to get a PG-13 rating so the teenagers can come. But you can use any other swear you want. Anything. But just one f-bomb.
EL: All right. Well, with that important knowledge…
LM: We’ve gone on so many tangents at this point. I probably got math in here somewhere, right? Somebody did math.
EL: Yes. Our math, hair, harp, and movie ratings podcast can now conclude.
KK: That’s right.
EL: Great to have you, Liz.
LM: Thank you. Thank you both for having me. I really appreciate it.
KK: Take care.
[outro]
On this episode, we were happy to talk with Liz Munch, an applied mathematician at Michigan State University, about the max flow, min cut theorem. Here are some links you might enjoy after you listen to the episode.
Munch's website and Twitter account
The Women in Computational Topology Network
The Max-flow Min-cut theorem at Brilliant.org
The Ford-Fulkerson algorithm on Wikipedia
The cross-strung harp on Wikipedia
Harp.com's history of the harp