How Does Graph Theory Shape Our World?

Born in the 18th century when Leonhard Euler solved the puzzle of the seven bridges of Königsberg, graph theory has become a foundational tool in mathematics. It studies relationships through nodes (vertices) and the links (edges) that connect them, transforming the complexity of systems — from friendship networks to airline routes — into elegant abstractions that reveal underlying structure and interaction. Maria Chudnovsky from Princeton University is a leading mathematician in the field. In this episode of The Joy of Why, Chudnovsky talks with co-host Janna Levin about how she got into graph theory, solved the decades-old perfect graph problem, and used it to plan her wedding seating chart. Chudnovsky also reflects on her appearance in commercials as a “superstar mathematician,” and how her background primed her for a discipline that transcends language, culture and time.

• 0:00Speaker 00

  Hi, I'm Terry Tao. My new book, Six Math Essentials, explores six concepts that have guided mathematicians like me throughout history. With a simple introduction to numbers, algebra, geometry, probability, analysis, and dynamics, I share how these ideas helped me think mathematically and can help everyone better understand our complex world. Mathematics isn't magic. It's a way of thinking anyone can learn. Please visit quantobooks.org to learn more.

• 0:31Speaker 01

  I'm Janna Levin.

• 0:32Speaker 02

  And I'm Steve Strogatz.

• 0:33Speaker 01

  And this is The Joy of Why, a podcast from Quantum Magazine, exploring some of the biggest unanswered questions in math and science today.

• 0:47Speaker 01

  Steve, hi.

• 0:48Speaker 02

  Hi there. How are you doing, Jana?

• 0:50Speaker 01

  Good. It's good to see you again.

• 0:52Speaker 02

  Yeah, great to see you.

• 0:52Speaker 01

  I have a math problem for you.

• 0:53Speaker 02

  Oh, love it.

• 0:54Speaker 01

  So imagine you're visiting a city and has a river, maybe, let's say, maybe it's an island like Manhattan. And there's little islands like Randall's Island or Roosevelt Island, and they're connected by bridges.

• 1:05Speaker 02

  Uh huh.

• 1:05Speaker 01

  And you're a tourist. You want to cross every bridge, but you don't want to overexert yourself, so you're going to try to cross each bridge once.

• 1:12Speaker 02

  Mmm.

• 1:13Speaker 01

  Have you heard of this before as a mathematical problem?

• 1:16Speaker 02

  You know I have.

• 1:17Speaker 01

  Yeah. Seed planted.

• 1:20Speaker 02

  Yeah, yeah. No, it's a classic problem sometime in the 1700s. Leonard Euler was asked this question. You know, a funny thing about it that I only recently learned is that when the mayor of that town, Konigsburg, asked him to think about this question, Euler complained, what are you asking me for? This is not a math problem.

• 1:39Speaker 01

  Right.

• 1:40Speaker 02

  Isn't that interesting to him?

• 1:41Speaker 01

  Yeah.

• 1:41Speaker 02

  This was not math.

• 1:42Speaker 01

  That's really interesting.

• 1:43Speaker 02

  At the time. He founded a new branch of math in thinking about it, but he didn't see it as math at the time.

• 1:48Speaker 01

  So how did he get interested enough to mathematize the problem, which is really what we're doing a lot of the times?

• 1:54Speaker 02

  I think it's just that Euler felt that it was a curious question, worth thinking about, just because it involved, as he put it, reasoning.

• 2:02Speaker 01

  Mm-hmm. A puzzle.

• 2:03Speaker 02

  It was a puzzle.

• 2:03Speaker 01

  Yeah. Now, Konigsburg is now the Russian city of Kaliningrad, if I've got that right.

• 2:08Speaker 02

  Uh huh.

• 2:09Speaker 01

  So can a visitor there- Figure out how to go across. There's a river, there's a mainland, there's two islands and seven bridges.

• 2:16Speaker 02

  Yeah, that's right. And in that old problem, the townspeople used to go out on Sundays and take strolls. And it was an amusement to see if they could walk across each bridge exactly once. And no one could ever do it, but nobody could prove it was impossible. Until Euler, who did prove it was impossible.

• 2:32Speaker 01

  And so how does he turn this into a math problem?

• 2:35Speaker 02

  Well, if you look at his original paper, what he does is use letters. Capital letters for the land masses and lowercase letters for the bridges. And then he plays around with the combinations of these uppercase and lowercase letters that would correspond to admissible walks.

• 2:51Speaker 01

  Oh, how interesting.

• 2:52Speaker 02

  Nowadays, we would use dots and lines. So of course, he found that he couldn't do it because some of the land masses had an odd number of bridges touching them.

• 3:00Speaker 01

  So once he solves that problem, he realizes, oh, immediately he can say, if this problem crops up again, you need an even number of bridges. So he's already.

• 3:07Speaker 02

  He's already generalizing.

• 3:08Speaker 01

  Making headway towards generalizing. And so you said it invented a whole new branch of mathematics. And what's that branch?

• 3:14Speaker 02

  Well, we call it graph theory. Or if we're in England, we would say Grof theory.

• 3:21Speaker 01

  Well, here, we were talking to Maria Chudniewski, who's a really interesting mathematician at Princeton. She works primarily on graph theory and managed to solve a very interesting, outstanding problem. It was nearly 50 years old about perfect graphs.

• 3:36Speaker 02

  That's a term I haven't heard before.

• 3:37Speaker 01

  I'll let her sort of tell the story. But it's really about color coding and visualizing and nodes and dots and connectors. So let's hear from Maria. You want to eavesdrop a little bit?

• 3:48Speaker 02

  I'm all ears.

• 3:49Speaker 01

  Great. Here's Maria Chudniewski from Princeton, talking about graph theory.

• 3:56Speaker 01

  Maria, welcome to the show. It's so nice to have you on. Thank you. I wish we could be in the same studio. We realized we're only a few blocks apart.

• 4:05Speaker 03

  Maybe next time.

• 4:06Speaker 01

  Maybe next time. I actually was amused to discover that you had been in a TurboTax commercial.

• 4:13Speaker 03

  That's right, that's my claim to fame. I also did a mattress commercial, did you know that?

• 4:17Speaker 01

  Yes, I saw you sleeping in a mattress commercial.

• 4:20Speaker 03

  Exactly, the smart begins with better sleep. There's no statement I believe in more.

• 4:24Speaker 01

  They're getting free advertisement with us here. I was amused to see that they listed you underneath your name in these commercials as superstar mathematician. And I wonder if you think the culture is changing in our attitude towards mathematicians?

• 4:39Speaker 03

  I think there's a lot more understanding now of how important math is. I used to tell people I'm a mathematician, they would say, oh, yeah, terrible in math, math is really boring. And now they say, oh, wow, that's really interesting what you do. I think, you know, with the advance of technology and the internet and, you know, obviously our life have changed a lot over the last 30 years or 100 years, depends how you want to think about it. And I really think math is kind of gaining popularity and gaining traction.

• 5:08Speaker 01

  It really is interesting that mathematical literacy or scientific literacy is considered important, more than it used to be at least.

• 5:16Speaker 03

  I'm so happy about that because, you know, it really it seemed to be an educated person, you need to read books, you need to know something about art. And I would never say that's not important. But now it seems that there's another component to it. And, you know, given that that's a huge part of my life, I'm very, very happy about that.

• 5:33Speaker 01

  There's also an old idea that mathematics is the language of the universe, which might actually be attributed to Galileo. What do you make of this quote? I mean, do you see it as a universal language of sorts?

• 5:45Speaker 03

  I certainly do in many ways, like you don't need to speak any particular language very well in order to be able to effectively communicate mathematics. If you have something interesting and important to say in math, you need to have some basic common language with the person you're speaking with. But you don't need to be eloquent, you don't need to be a great speaker. You can just write down what you have to say and say what you have to say, and it's been communicated. There is no kind of added layer of I need to say it in such a way that it convinces them. If you have a proof, it convinces them. It doesn't matter how you say it.

• 6:23Speaker 01

  And it's the same around the world.

• 6:25Speaker 03

  And it's the same around the world, yeah. There's really no differences. Another thing math brings to the table is clear thinking. That's maybe a little less of a language thing, but the way you understand things, the way you think about things, you try to break it into pieces and see what's important, what matters, what was incidental and coincidental and not important. If you're used to thinking in a mathematical way, that really puts you at an advantage.

• 6:50Speaker 01

  It's like a meta-language, like a way of understanding the world that transcends the grammatical structure.

• 6:58Speaker 03

  Right. There are all these studies that depending on what language you think it, you perceive the world a little differently, which I'm incredibly fond of.

• 7:05Speaker 01

  That's amazing. I was actually going to ask you about that hypothesis in linguistics, that language structures your thoughts.

• 7:11Speaker 03

  So I'm fluent in two languages and I understand three languages. And I know this about myself. Things change a little bit in the way I think when I'm dealing with a different language.

• 7:21Speaker 01

  Fascinating. I understand that you did have a personal experience with languages, with countries, with moving. You were born in Russia and moved to Israel as a teenager. So this played a personal role for you, this issue of language, transcending language and using math as a medium to express yourself.

• 7:38Speaker 03

  Absolutely. I'm sure of the fact that of all the subjects I could study, the one that required the least command of a language was math. Had a lot to do with my choice of field of study. As a mathematician and a scientist, if you're used to thinking mathematically, then you perceive the world in a certain way, which is a little bit like if you're used to thinking in a certain human language, then you perceive the world in a certain way.

• 8:01Speaker 01

  I don't want to completely leave this idea too quickly. I wonder how math can structure your thoughts, the particular field that you choose could structure your thoughts. You're in a branch of math known as graph theory. Can you give us just a quick explainer of graph theory to anchor us in your subject?

• 8:16Speaker 03

  Sure. Graph theory is a branch of math that studies pairwise relations. Let's start with something in the world. Suppose you have a system that consists of objects, and some pairs of objects are in a relation and some are not. Like, you can have a bunch of people, and some pairs of people are friends, and some pairs of people are not friends. Or you can start with buildings and roads between them. Or you can have a bunch of cities, and some pairs of cities have direct flights, and some pairs of cities don't have direct flights between them. So all these things are examples of graphs, where you can take objects and then say, this pair is in a relation, it goes together, and this pair doesn't go together. So now, forget all these examples and just stay with the abstraction,

• 8:59Speaker 03

  where you put a dot on your piece of paper for every object, and now you put a line between two dots, we call it an edge, if these two objects were in a relation. So now, you have an abstract mathematical object called graph. Apparently Euler came up with this idea in seventeen-something. And now, instead of studying a system of people's friendships, or a system of flights, or a system of roads, you can just study this abstraction of a graph. You're no longer a social scientist or a transportation expert. Now, suddenly, you're a graph theorist.

• 9:31Speaker 01

  Right, you're a mathematician. What drew you to this particular topic of graph theory? And also, do you really think you think more visually and differently because you're so embedded in graph theory? Or you think it was the other way around? You were inclined to visual thinking, and that drew you to graph theory?

• 9:46Speaker 03

  I think the answer is we'll never know. When I was applying for grad school, I knew I wanted to do discrete math, because when I was in college, these were the courses that somehow were easiest to me. I felt that I understood them. The best, like when you take a class, some classes you study, you prepare for the test, you get your grade and you're grateful it's done. Some classes really stay with you and you keep thinking about it. It's kind of just the tip of the iceberg and then you keep going deeper and deeper in your mind. And then when you show up for the test, you didn't even need to study because you understood it so much better than what they tried to teach you. And so classes in discrete math were like that for me.

• 10:24Speaker 01

  I personally love discrete math. I once had a friend who said, there are different kinds of math. Like, this is a surprise to people who don't live in this world, that there are different kinds of math. Can you help our audience with the difference between sort of continuous and discrete?

• 10:39Speaker 03

  Sure, right. Roughly, you can partition all of mathematics into two parts. One part is things where you can say, this one is the next one after that one. And then things where you can say that because between every two things, there's another one. So I'll give you an example though, because of course, if you didn't know what I meant before, you don't understand now either. Let's say I'm thinking about counting numbers, natural numbers. So immediately after one comes two. Immediately after two comes three. And that's discrete. There's no counting number between seven and eight. Now let's think about fractions. Between one and two, there's one and a half. Between one and one and a half, there's one and a quarter. Between one and one and a quarter, there's one and eight.

• 11:23Speaker 03

  I'm not going to continue, but I think we get the gist. The first example was a discrete example. The second example is a continuous example. Courses in discrete math were somehow better for me. I always enjoyed them better, I understood them better. And so when I was applying to grad school, it was clear to me that I was going to do some kind of discrete math. Then I got into Princeton, where the kind of discrete math they were doing was graph theory. And I became a graph theorist. Had I gone to a different university, I would have probably done something else. And maybe I would have been good at that or maybe I would have had a different career.

• 11:57Speaker 01

  You might not have made it into a mattress commercial.

• 11:59Speaker 03

  Exactly.

• 12:00Speaker 01

  One of the aspects you mentioned, just as an aside, I think is so fascinating about the continuum between two integers. You can remove an infinite number of rationals and still have an infinite set left over. I mean, the beauty of discrete math is really mind blowing. On another note, I think it's interesting for people that graph theory is a very visual subject. I often see that you're drawing pictures on the board and making connections. You're doing them very fast because you're so used to it. But how strong is the visual aspect for you in your actual work? How much are you actually using a kind of visual mapping, do you think?

• 12:42Speaker 03

  All the time. I only think in pictures. Eventually, I have to sit down and write it because otherwise you miss things and you make mistakes. But all the development of ideas is visual.

• 12:52Speaker 01

  And it's quite beautiful to watch. Now, a lot of people also wonder what mathematicians are doing all the time.

• 13:00Speaker 03

  Doodling.

• 13:01Speaker 01

  What's at stake for the mathematician? Why are these problems important? There's this sort of tension between the very abstract mathematics, which I believe you very much love, and real world application. But what is that balance like for you? What's really at stake for you as a mathematician?

• 13:18Speaker 03

  I mean, I do abstract math. I'll be very happy if somebody someday finds applications for what I do. You know, sometimes people come to me and they have a question I can help them with, and it has something to do with the real world. That's exciting. That's fun. I like it. But my world is completely abstract.

• 13:35Speaker 01

  Do you ever have to use graph theory to solve your own real world problems?

• 13:40Speaker 03

  So when I was getting married to my husband, we had to design a seating chart, and we were nervous about it. And I said to him, let me try to do it. You can't be too picky about it. But I took our list of guests, which, by the way, the vast majority of guests at our wedding were people I didn't really know from my husband's side. I only knew kind of some stories about them. But it's a graph theory problem. What you do is you make a graph where the vertices, the dots, are the people. And now you put an edge between two vertices. These two people are such enemies that you can't put them at the same table.

• 14:21Speaker 03

  And now what you need to do is take your graph and partition its vertices into subsets, so that in each subset, you don't have two people assigned to the same table that can't sit together. You don't have two vertices joined by an edge. And if there are a lot of edges in your graph, that's a hard problem. But if there are few edges in your graph, namely, most of your friends and family get along, then it's actually easy that you can use something called the greedy algorithm and it just works. You know, our friends and family are reasonable people. There are not so many edges in this graph. So I do this list and a few minutes later, I had, it's called the coloring of the graph, the sitting arrangement, tables of ten to twelve, and it was basically completely acceptable. My husband was very surprised by that.

• 15:06Speaker 01

  Your wedding went without incident.

• 15:08Speaker 03

  No, no, no incident.

• 15:11Speaker 01

  Now, you've just been describing graph coloring, right? Your color coding, this is the group and here is a different group. As soon as you get to a point where, oh, this person can't sit next to this person, you need to assign a new color. Now, this graph coloring, is this a very old human problem?

• 15:27Speaker 03

  It absolutely is. There's probably the most famous problem in graph theory, the four-color theorem, which was actually posed by a cartographer, you know, two hundred years ago. And what he posed is that for any map on Earth, you can color in such a way that two countries that share a border get different colors, right? So you can do that by using at most four colors. No matter how the world is partitioned into countries, you can color it with four colors in such a way that countries that share borders get different colors.

• 15:57Speaker 01

  It's not obvious.

• 15:59Speaker 03

  It is very, very far from obvious. It inspired a lot of mathematical research for dozens of years. It's very far from being trivial. But let me just say a few things. One is when you say two countries share a border, they really need to share a little interval of a border sharing. Just one point doesn't count. Think two, this is only true if the countries are connected. If you have a country with islands, that's false. And the third thing is, you know, I said every map on Earth. I amuse myself with that. That's not just an expression. If your map is not on Earth, if your map is on a planet that has high genus, like a donut or a pretzel, then it's not true.

• 16:35Speaker 01

  Hmm, so if it's multiply connected in some way.

• 16:38Speaker 03

  Right, not simply connected.

• 16:40Speaker 01

  So how fascinating. So there is a right there, a real world application, which is trying to understand maps and borders. Maps in the 19th century were very important in terms of beginning to understand and think spatially. You've had a very big impact in an area that describes perfect graphs. Can you explain to me what makes a graph perfect in terms of coloring?

• 17:04Speaker 03

  I'm so glad we started this by talking about graph coloring, because this this sets the stage perfectly for talking about perfect graphs. So you have a graph, it has vertices and edges, and now you would like to color it. So you want to partition the vertices into sets so that there's no edge inside a set, right? Another way to say it is you color the vertices with different colors, and the rule is vertices of the same color are not joined by an edge. If two vertices are joined by an edge, they get different colors. Okay, so far so good. But here is a coloring, color every vertex with a different color. That is not a very interesting concept. To make it a less abstract, imagine, you know, you have to pay per color, and you don't want to buy more paints than you need.

• 17:48Speaker 03

  Okay, so now the question becomes, if I give you a graph, how many colors do you need in order to be able to color it? That's called the chromatic number of a graph. First of all, algorithmically, it's very hard. If I give you a graph and ask you, how many colors do you need? What's the smallest number of colors with which you can color this graph? You in general can't give an answer in a reasonable amount of time. Okay, but another thing is maybe I can look at a graph and start connecting how many colors I need to other properties of this graph. Maybe I still won't be able to give you an answer, but here's an obvious lower bound on the number of colors you need. If I have a graph and in it, there is 100 vertices all pairwise adjacent, I need at least 100 colors in order to color this graph. Now, there are graphs with no three pairwise adjacent vertices that need

• 18:33Speaker 03

  1,000 colors, and there are graphs with no three pairwise adjacent vertices that need 1,000,000 colors. Now, on the other hand, there are graphs where that doesn't happen. There are graphs where this obvious lower bound of how many pairwise adjacent vertices you have.

• 18:48Speaker 03

  Is actually the right answer. And these are called perfect graphs.

• 18:52Speaker 01

  I get the gist of it, and let me just try to help for our audience to to bridge a little gap. It's my understanding that when you have these, you're calling them pairwise-adjacent vertices, we could call those a clique.

• 19:03Speaker 03

  Yes, clique is the right word for it.

• 19:05Speaker 01

  I'm just imagining that socially, people understand when you're trying to do a wedding graph or a dinner party graph, that there's a little clique. And in that clique, if that number of vertices equals the number of colors you need to use through chromatic number, then you're on your way to a perfect graph.

• 19:22Speaker 03

  So a graph is perfect if its chromatic number equals to the largest size of a clique in it.

• 19:27Speaker 01

  Oh, excellent. Exactly. So the largest clique, yes. Now, in the 1960s, a French mathematician, Claude Béch, began to think more about coloring and perfect graphs. He formulated this conjecture known as the Strong Perfect Graph Conjecture. Now, this has loomed large in your work. How does your work tie in with this famous conjecture, long-lasting conjecture over 50 years?

• 19:50Speaker 03

  So when I came to Princeton as a graduate student, I came to the office of Paul Seymour, and he was working on the Strong Perfect Graph Conjecture at the time. And I knocked on his door and I said, can I work on this with you? And I think he was a little surprised. It's not a question people often ask, but he didn't know what to say, so he said yes. And then a couple of years later, four of us solved this problem. It wasn't my first theorem, but it was the first theorem I proved as a PhD student. And, you know, it's a good way to start a career.

• 20:19Speaker 01

  That must have had an enormous impact. A half-century-old conjecture, many people working on this important problem. How did you approach this, you and your collaborators, so that you were able to make progress where others were stymied?

• 20:34Speaker 03

  That problem was open for 40 years at the time, and people worked on it. Béch's conjecture was, every graph with this and that structural property is perfect. And it was clear that if and only if a graph is perfect, then it must have those structural properties. You know, when you just say a sentence like that, you have no idea where to start. How would you prove that everything with those three properties have that first property? But what you could try to do is try and understand what all graphs with these first three properties look like. And then take that and deduce from that the fourth property direction interested. And because people have been thinking about this problem for 40 years, there were a lot of ideas

• 21:19Speaker 03

  of how this gap may be bridged. None of them were exactly correct. And then we had to come up with our own correct intermediate statement. But there was enough thoughts in the world that at least we knew in which direction we should start going. And then, you know, we worked really hard, we got lucky, we are smart, all kinds of things.

• 21:45Speaker 01

  So I love how that refers to a larger global collaboration, which I think relates to something we were talking about in the beginning about the transcendence of mathematical language, that this is an international collaboration, even if not in an individual paper, in the larger scheme of things.

• 22:03Speaker 03

  Very much so. I mean, I work with people from all over the world. I travel a lot. And because math is math and truth is truth, you can disagree on everything, but you will agree that the proof is correct, or you will agree that the proof is not correct. And your other opinions don't play into it at all.

• 22:24Speaker 02

  I love how she says it, math is math and truth is truth. But it makes me wonder if this kind of training that we get pairs us ill for the real world.

• 22:34Speaker 01

  Maybe you could say the real world is overrated.

• 22:37Speaker 02

  You know, that's what some of us think in math, because how many other places can you say something like that, math is math and truth is truth? I mean, this is an oasis. It's such a pretty place to live.

• 22:48Speaker 01

  It's such a pretty place to live. And we talk about this a lot on the show, just how transcendent the ideas are. They're true for all of us. And that's really special and really unusual.

• 22:59Speaker 02

  It's also a gift that we get to talk to each other across the centuries. You know, like we mentioned Leonard Euler, and you can have in your mind at least a conversation with someone from hundreds of years ago. There are some differences, but there's a lot that we have in common.

• 23:12Speaker 01

  Absolutely. I love that idea that we're having a dialogue across time. I mean, not only across cultures.

• 23:17Speaker 02

  Right.

• 23:18Speaker 01

  Not only across the globe, but we can actually go across time. I mean, this is when we talk about sending messages out into the universe, the most reasonable messages to send are ones that have to do with math. Let's go back to our guest. Let's hear more from Maria right after this break.

• 23:54Speaker 01

  Welcome back to The Joy of Why. We've been speaking with graph theorist Maria Chudniewski on how she proved the strong perfect graph theorem, something that was proposed by Claude Berge back in the 1960s.

• 24:07Speaker 01

  Math can be very frustrating, and it can take a very long time. You have this enormous breakthrough, but it's not a single moment. For you, how does this unfold and come clear to you that you were really on to something?

• 24:21Speaker 03

  You know, you never know until you know. You really think you're making progress, you set your next goal and you proved it, and now you think, okay, well, great, this was a big hurdle. Now it's a straight line from here, and then suddenly it's not a straight line. It's a nerve-wracking process. But on the plus side, there are a lot of little celebrations. Just because it's not the last hurdle doesn't mean it wasn't an important one. Every step is a eureka moment. I think now every proof is very complex. There's not one eureka moment. But there are a lot of victories, a lot of celebrations. Ingrid Dobyshe in some interview once said, "There isn't where you messes because we're addicted to the high." And it's completely true.

• 25:01Speaker 01

  That's a T-shirt. I don't know if the story is true or if it's apocryphal, but I heard that Berge was read the news of the impending proof while he was in the hospital. Is that a true story?

• 25:09Speaker 03

  You know, he was in the hospital, that's true. He was told the news in his last days when we found the proof. He was told about the proof.

• 25:18Speaker 01

  It's a nice dimension. Of course, mathematics is ultimately a human pursuit. I wanted to ask a little bit about applications that have branched off of this discovery. Are there, to your knowledge, examples in which people are using this in other fields?

• 25:36Speaker 03

  Right. So that is, I don't know. There is a paper about perfect graphs and coverage collection in Brooklyn.

• 25:42Speaker 01

  How grateful I shall be to you if that problem is solved.

• 25:45Speaker 03

  There we go, exactly. But it's not me. It's before my time.

• 25:48Speaker 01

  I definitely do not need for there to be a practical application to value mathematics. And I love that we're asking people to appreciate that the stakes are high, even for very abstract mathematics. I know that we have sirens in the back, so there's probably some graph theory problem for solving the route that an ambulance or cop car has to take through Manhattan.

• 26:11Speaker 03

  You know, designing optimal routes is definitely a graph theory problem, right? You have junctions and roads between them, and that's a graph. And now you're trying to find the best way to navigate that graph.

• 26:21Speaker 01

  So let's take this back to the way you approached your solution. The problem that you approached, how long, for instance, is the paper that you wrote?

• 26:30Speaker 03

  About 150 pages long.

• 26:32Speaker 01

  Okay, so this is very long.

• 26:33Speaker 03

  This is very long. This is hard. This has nothing to do with complexity hierarchy. This is just hard.

• 26:38Speaker 01

  This is just colloquially hard.

• 26:39Speaker 03

  That's right.

• 26:40Speaker 01

  How did you simplify the problem? There seemed to have been a strategy where you broke the graphs into pieces in a systematic way to allow you access to this proof.

• 26:54Speaker 03

  Right, so there's a lot of breakage going on. So the goal was to prove if you have two properties, then you're perfect. So what we did was we showed that if you have these two properties, then either use some graph we can describe, or what's called an explicit construction, or you can break your graph apart in such a way that showing that this half is perfect and showing that this half is perfect is enough. So that was the theorem we proved. This is a theorem with a lot of outcomes. We have five explicit constructions, three kinds of decompositions, three kinds of ways to break a graph. So what you're proving is if problem is one and two whole, then one of those eight things happen.

• 27:38Speaker 03

  Now, in general, that's a theorem that's very hard to prove because you don't know which way to push.

• 27:43Speaker 03

  Are you trying to prove that the graph behaves like this? Or are you trying to prove that it behaves like that? So what's helpful is to break the world into pieces, where in this part of the world, it's always like this. In this part of the world, it's always like that. And in a way, that's a key to almost every mathematical proof. You have some huge overwhelming thing, but you're simplified it into a scenario where it's always like this, and a scenario where it's always like this, and a scenario where it's always like that. And if you can distinguish between your scenarios, then usually that leads you to a proof. And so that was kind of a very important insight, a very important thing to do in this proof to understand how to approach the world in this stratified way.

• 28:27Speaker 01

  It's a strategy.

• 28:27Speaker 03

  Right, right.

• 28:28Speaker 01

  So it's fascinating. Maria, I wonder, how do you know when you're approaching a problem, how hard it is? Is the next problem you brave going to be necessarily even harder one? Or are the challenges unpredictable?

• 28:42Speaker 03

  I don't think problems are linearly ordered by difficulty. I think every problem is hard until you solve it, and then you have a solution. The reason to choose a problem is not because it's harder than the previous problem you solved. The reason to choose a problem is because there's a phenomenon you want to understand. And in order to understand it, you need to answer this question. If the question is appealing to me, it's an aesthetic choice. You know, it's a little bit of a practical choice if I think I have a chance of contributing. But it's also like, does this question interest me?

• 29:12Speaker 01

  And so what is that intuition? What drives your choices in big problems?

• 29:17Speaker 03

  I think, and this is speculation, questions that interest us are related to questions we've already thought about. It's very rare that somebody, you know, comes into the room and says, here is a question you must be really interested in. If I've never thought about it, what does that have to do with me? So I think there's like some kind of world you're building throughout your lifetime. And every next question interests you because it relates to the world you've built so far. But I think it's probably only clear to you from the outside. I think it's a little less obvious.

• 29:55Speaker 01

  I wanted to ask you one last question, and that is what brings you joy in your research?

• 30:03Speaker 03

  Seeing order in a new place, understanding that something is actually built in a way I can describe, even though until recently it was just a mess. I guess bringing order to the mess.

• 30:20Speaker 01

  Beautiful. Maria, thank you so much for joining us. There's such a depth here, I could talk to you for hours.

• 30:27Speaker 03

  Thank you very much for having me. I really enjoyed this.

• 30:33Speaker 02

  I'm struck by how personal the experience of being a mathematician is because when she says that what interests her is not necessarily how difficult a problem is, but whether it connects to things that she's thought about before. I feel like that's not a universal phenomenon. That's something that some of us would use. But I'm thinking, let's say, of John Nash, the great mathematician profiled in Beautiful Mind, who would change fields just looking for the hardest unsolved problem? It was a macho thing for him. I think he was interested in everything as long as it was hard.

• 31:10Speaker 01

  I mean, isn't that also the testament that it takes all kinds of personalities and ways of thinking to make an entire discipline?

• 31:16Speaker 02

  Uh huh.

• 31:17Speaker 01

  Right, a healthy discipline.

• 31:18Speaker 02

  Exactly. And as Maria says, it's an aesthetic choice for her. Some people are driven by aesthetics, but I think some are driven by. I want to use my craft. You know, I have this powerful technique and I'm just looking for something I can use it on.

• 31:34Speaker 01

  Yeah. Do you feel that challenge and difficulty intrigues you when trying to solve something?

• 31:39Speaker 02

  No.

• 31:40Speaker 01

  No, interesting.

• 31:41Speaker 02

  No, I really resonated with what she said about phenomena. It really hit me that she uses the word that a scientist would use, not a mathematician, that she sees phenomena and it's phenomena that appeal to her and she wants to think about things that seem curious and baffling, but that are close enough that she thinks she could contribute. So I love that view of it. That's much closer to my own. I mean, actually, what personally drives me has always been paradox.

• 32:09Speaker 01

  Oh, intriguing.

• 32:10Speaker 02

  I really like it when something seems wrong, when something is off. That shouldn't be the way this works. That's the kind of question I always like.

• 32:18Speaker 01

  Right. And then you can't, you can't not follow it. You know, I think sometimes I like these kind of big visual problems with a lot of math, right? A lot of geometry, a lot of big spatial moves, big brush strokes that move things around.

• 32:35Speaker 02

  I'm taken with your analogy to painting. Do you actually paint?

• 32:39Speaker 01

  Oh, gosh. I mean, a long time ago, but I don't advertise myself as a painter. But it's true, there's a method, right? You go up and you do big brush strokes and then you do, you get ever finer. Eventually, you're on your two hair brush.

• 32:49Speaker 02

  Well, it's really great talking to you about all this.

• 32:52Speaker 01

  Yeah, great talking to you, Steve. Till next time.

• 32:54Speaker 02

  Okay. Bye bye.

• 32:59Speaker 02

  If you're enjoying The Joy of Why and you're not already subscribed, hit the subscribe or follow button where you're listening. You can also leave a review for the show. It helps people find this podcast, find articles, newsletters, videos, and more at quantamagazine.org.

• 33:15Speaker 01

  The Joy of Why is a podcast from Quanta Magazine, an editorially independent publication supported by the Simons Foundation. Funding decisions by the Simons Foundation have no influence on the selection of topics, guests, or other editorial decisions in this podcast or in Quanta Magazine. The Joy of Why is produced by PRX Productions. The production team is Caitlin Folds, Levin Brock, Genevieve Sponsler, and Merritt Jacob. The executive producer of PRX Productions is Jocelyn Gonzalez. Edwin Ochoa is our project manager. From Quanta Magazine, Simon France and Sameer Patel provide editorial guidance with support from Matt Carlstrom,

• 33:58Speaker 01

  Samuel Valesco, Simone Barr, and Michael Kanugolo. Sameer Patel is Quanta's editor in chief. Our theme music is from APM Music. The episode art is by Peter Greenwood and our logo is by Jackie King and Christina Armitage. Special thanks to the Columbia Journalism School and the Cornell Broadcast Studios. I'm your host, Janna Levin. If you have any questions or comments for us, please email us at [email protected]. Thanks for listening.

• 34:42Speaker 01

  From PRX.