Parties, doughnuts and colouring: welcome to the world of graph theory

Ahead of her Hamilton Lecture in Dublin on October 16th, Prof Maria Chudnovsky of Princeton University connects the dots between the abstract and the real

Maria you are giving the annual Hamilton Lecture soon in Dublin, what will you talk about?

I will talk about simple problems or puzzles that relate to parties, doughnuts and colouring and explain how they grow into research directions in graph theory, and what kinds of problems researchers in graph theory work on today.

What do you mean by graph theory?

The graphs I talk about are not the ones with X and Y axes. In the field of graph theory, a graph is an abstract concept. Very simply, if you put some dots on a piece of paper and then connect some of the pairs of dots with lines, then you have a graph. It maps relationships between objects.

In your PhD at Princeton, you were part of a group that solved a big problem in graph theory. What was that?

In 1961, the French mathematician Claude Berge defined the notion of “perfect graphs” that behave particularly well with respect to a basic notion in graph theory called “colouring”. In 2003, four of us were able to prove a theorem that says a graph is perfect if and only if it doesn’t contain certain structural faults, thus verifying a conjecture that Berge made more than 40 years earlier.

And what are you researching now?

I work in a field called “structural graph theory”, where you start with a property and you want to understand the structure of all graphs that have this property. My doctoral thesis work was one example of this, but there are many more questions to ask there.

What is your advice for budding mathematicians?

Maths is beautiful and a great field to pursue. If you study maths and then decide not to go on and research it, you have a skill that you can bring to other activities in life. Or if you become a researcher in maths, then you have a lifetime of pleasure in working with its beauty.

You have appeared in a couple of ads over the years, how did that happen?

I was in an ad for an online service to help people do their tax returns and also an ad for a mattress. In both cases they wanted to feature someone smart and I guess they found me as I had been made a MacArthur Fellow in 2012 and there was some press coverage around that. I particularly liked doing the one for the mattress, because I am a big believer in getting lots of sleep.

And when you are not sleeping or solving maths problems, how do you spend your time?

We have a young son – who is now old enough to understand that I need lots of sleep – and I love art and theatre and good food. I also love music, but it is my husband who is the musician, he is a viola player. We have a good partnership where each admires what the other does, but doesn’t really understand how it is done. We simply support each other in it.

Prof Maria Chudnovsky delivers the Royal Irish Academy's 2019 Hamilton lecture "Parties, doughnuts and colouring: some problems in graph theory" at 18:30 on October 16th at the Edmund Burke Theatre (Arts Block), Trinity College (Nassau Street entrance), Dublin 2. To book tickets and for more information, go to