Maria Chudnovsky is a leading mathematician working in the field of graph theory.

She was born in St. Petersburg, Russia in 1977, and moved to Israel with her family at the age of thirteen. Maria studied mathematics at Technion in Haifa. She completed her PhD at Princeton University in 2003, supervised by Paul Seymour.

Maria has the most famous PhD dissertation in the recent history of graph theory. She helped prove the Strong Perfect Graph Theorem (SPGT), first posed by Claude Berge back in the 1960s. Research on SPGT and perfect graphs resulted in hundreds of papers and partial solutions before its resolution. There are about 700 citations on MathSciNet for the search “perfect graphs” up to 2006, when the proof was published in the Annals of Mathematics.

Chudnovsky, Seymour and their collaborators Neil Robertson and Robin Thomas found the proof of SPGT. The trio of Robertson, Seymour and Thomas are well-known to graph theorists for their epic catalogue of work, especially for their deep results on graph minors. The proof of the SPGT was a historic work that spanned 178 journal pages.

In 2002, they announced the solution of SPGT. I vividly remember the excitement surrounding the announcement, and how it sent ripples throughout our community.

After her doctorate, Maria was a post-doc at the Clay Institute of Mathematics, and then she moved to professorship at Columbia University. She is now a Professor in the Mathematics Department at Princeton University.

Maria is a giant in her field. For her work on SPGT, she won the Fulkerson prize in 2009. She holds a MacArthur Fellowship (or “Genius” grant; see the video below from 2012), and her research is funded by the National Science Foundation.

Maria is also unique among mathematicians I know of for appearing in not one, but two television commercials: one for TurboTax (check it out below) and one for Comfortpedic. I think these give wonderful exposure not only for her and her work, but also for the public to see examples of real mathematicians.

Enjoy!

 

AB: How did you first become interested in mathematics?

MC: I don’t remember a time when I wasn’t. Math was always easy and fun, and everything else was hard. It was a very natural thing for me. It was always my favorite subject.

I remember the pain of learning to read, and I don’t remember the pain of learning to count.

AB: Did anyone play a role in inspiring your interest in mathematics?

MC: My dad loved math. He was an engineer, but as a kid he loved mathematics. Probably he said enough things to get me interested.

I was lucky as I had very good teachers. I went to a special mathematics school in St. Petersburg, Russia. I was born in Russia, and my family moved to Israel when I was thirteen. I went to this school from the ages seven to thirteen, where math was the most important thing in the world, and the best thing you could be was to be good at math. I also had many good teachers who made things beautiful and made things interesting. From everything I heard in school, I never doubted there was anything more interesting than math.

AB: Can you tell us something about your experience at Technion? In particular, what was the environment like there, and how did it help lead you to Princeton?

MC: I started at Technion in the eleventh grade, where I began going to a Math Circle that was led by a Masters student in applied mathematics. It was a fun experience. He would solve Math Olympiad problems with us. If he attended an advanced mathematics lecture, he would tell us about it, making it digestible for us high school kids. It was also a social thing; it was where I met most of my friends. That was huge in my life. It was when I realized you could be a mathematician by profession.

Unlike in the United States, in Israel you have to declare your major right away. You don’t apply to a university, but instead you apply to a department. If I hadn’t gone to this Math Circle, then I wouldn’t have applied to the math department.

Both my parents were engineers, and it was always clear that I should go into engineering or computer science, as I was good in mathematics. This is ironic, as the math I do is on the border of computer science; many of my colleagues work in computer science departments.

I have to say, a lot of it was social. We were a group of friends, all very interested in math. We talked to each other about the things we learned, how pretty or nice something was. That reinforced my conviction that this is what I want to do in my life. If I could keep going like this, it would be great.

I applied only to three places for my doctorate. One didn’t accept me.

AB: They are probably regretting that decision now!

MC: It was clear that Princeton was the right choice for me.

AB: Why did you choose to study graph theory?

MC: I knew I was going to study discrete math, because as an undergraduate I thought it was a pretty area and I had a good intuition for it. When you like something, it is never clear if you first like it and become good at it, or you are first good at it and then like it. I certainly had this connection with discrete math.

At Technion I also did a Masters in discrete math. All the places I applied to had strong discrete math programs. At Princeton my research would have been graph theory, and in other places it would be other topics. I ended up at Princeton, so I became a graph theorist.

AB: How did you come to work on the Strong Perfect Graph Theorem (SPGT) in your doctoral work?

MC:  I showed up at Princeton, and I knew I wanted to work with Paul Seymour. That was the problem he was interested in the time. I was lucky at the time that I didn’t understand what was appropriate and what wasn’t. I came up to him and said “Can I work with you on this?” He said “sure.”

When he saw I was contributing, I became part of the group. I don’t know if when I first approached him he thought it was a little bit strange.

AB: Andrew Wiles famously spoke about a great eureka moment when he settled Fermat’s Last Theorem. Did you have a similar “aha” moment when settling SPGT with your collaborators?

MC:  I was working with Paul Seymour at 5:45 pm (we usually work until 6:30 pm). We knew we were near the end of the proof, and there was one last step left. And then we saw it. We saw why A implies B.

We looked at each other and said “That’s it. We are done, we can go home early.”

AB: When you settled something as important as SPGT, were you confident the proof was correct?

MC: With all proofs, there are many levels of confidence. At first, you see a solution, and that is very good. But it is a huge proof, so you may have overlooked something. Then you sit down and write notes. After you have done that, you are more confident. And then you sit down and write a paper, and you feel even more confident. And then you start giving talks and people think about what you said. And there is the refereeing process.

By now, we are pretty confident. With such a large proof, I don’t know how to tell one hundred percent that it is true. Probably someone by now would have found a mistake, as it is something that people care about.

AB: Structure plays a major role in the work you do, ranging from perfect graphs, to claw-free graphs, or analyzing other graph families. What do you think is the importance of structure in graph theory?

MC:  First, to me personally, structure is very satisfying. You are not just answering one question; you are really seeing some huge, global phenomenon going on.

This is how I like the world to be, where I can completely understand what is going on. So if I have a question, then I can go and look at this systematic picture that I have in mind, and I can find out the answer to this question. That is one kind of answer to your question.

Another answer is that it is surprising that some properties give you a kind of structure. There are many different properties of graphs you can think about. Some are little things: maybe they happen or maybe they don’t. Some have a huge influence on the graph.

In some sense, this is the strongest kind of theorem. You have some property, and it happens if and only if there is a certain structure.  Somehow, that tells you a lot.

Not all properties allow you to prove a beautiful structure theorem. Some are just yes or no questions. When I give talks, I sometimes distinguish between properties and structure. It is remarkable and satisfying that with the property of a graph being perfect, you can understand the structure.

AB: What inspires your mathematical ideas?

MC: Things that appeal to me aesthetically. It could be a problem that seems beautiful, or a concept that seems beautiful. Or it could be someone else’s proof that seems beautiful and I want to see what else I can do with it.

AB: The notion of beauty comes up often in our discipline. On that note, mathematics is sometimes called a science or art. What is your view?

MC: I think in the middle. Beauty is definitely the guiding motivation. There is math that is motivated by physics, chemistry, or engineering. That is somehow separate. In much of math, you are just looking for the most beautiful thing you can think of. And only that determines if something is interesting or not.

Beauty is also subjective. What I think of as beautiful someone else might think is ugly.

AB: What advice would you give to young people, especially young women, who want to study mathematics?

MC: I can give advice that is not exactly my own. When you start graduate school or anything big, you feel like that there is no way you are going to succeed. And there are setbacks: maybe you tried to solve a problem and you didn’t, or you get a bad grade on an exam, or you attend a class you didn’t understand.

You might then say to yourself that since I didn’t understand this, I should be doing something else. That’s not the right approach. What one shouldn’t do is quit. It’s not wrong to think about quitting, but I think one should take a very long time to consider the situation before quitting.

Don’t let your self-doubt scare you too much. Just accept that everyone has their moments when they feel like a complete misfit. Just keep pushing.

When you do something creative, 90% of the time, you fail. If you are failing much of the time, you are not going to feel good about yourself much of the time. But then you succeed, and it more than makes up for it! You have to accept that is part of the creative lifestyle.

AB: Besides mathematics, what are your interests or hobbies?

MC:  I like art. I don’t produce it, but I like seeing art.

I have a two-and-a-half year old, and he is a full-time hobby. I am not one of these people who does math and then has another thing that is close second. I would say my job is my hobby.

AB: Graph theory is a robust discipline with so many directions, such as structural graph theory, probabilistic graph theory, topological graph theory, and applications through network science. What do you think are the major directions in the field?

MC: That’s a very good question that I wish I knew the answer to, as I would work in that direction. I think applications are becoming huge. I think applications are slightly different from the things I do, since in applications the graph you are looking at is very large. The kind of things I do are deterministic things. What is needed in applications are more like if you assemble 10% of your information about the graph, then what can you say with high probability? I think there are many people doing beautiful theoretical research that’s vaguely or not vaguely motivated by that approach.

I would like to take the classical questions I’ve worked on and translate them into this language. We used to prove that every vertex of this set is adjacent to every vertex of another set. Instead, we can think about if many vertices of one set are adjacent to many vertices of another. I would look for an analogue or translation like that.

Yesterday I was on the train, and I saw someone with a t-shirt with a graph on it. And I thought, how nice. It was a Princeton Computer Science t-shirt!

Anthony Bonato