Julia Böttcher is a Professor in the Department of Mathematics, having joined LSE in 2012. She works in discrete mathematics, and completed her undergraduate and master’s in Computer Science in Berlin, before completing a PhD in Munich. Prior to LSE, she was in São Paulo (Brazil) for a postdoc.
In this post, Bento Natura finds out about Julia’s research area and its complexities, as well as her perspective as a PhD supervisor in the Department.
What would be the biggest open problem that can be explained to a layman in your area?
There are many important open problems in my area (extremal combinatorics) that I like. Some, of course, are easier to describe than others. Let me choose a conjecture that is close to my own research, easy to describe, and still open: A lot of my work is in graph theory, the mathematical theory of networks. A graph consists of a collection of vertices and a collection of edges between these vertices. The vertices represent entities in the network, and between any pair of such entities one may or may not have an edge, representing a relation between these two entities. The conjecture I am going to explain, which is called the graceful labelling conjecture, concerns graphs of a special form, which we call trees. A tree is a graph such that there is a unique path between any two vertices (this is the same as saying that you can walk from any vertex to any other by a sequence of edges and that there is no cycle).
Now, given any tree with n vertices, our goal is to assign to each vertex a different number between 1 and n such that the following is true. If you look at any edge, its two endpoints were given two labels, and we now assign the difference of these labels in absolute value as label to the edge. So the labels of the edges are determined by the labels given to the vertices, and what we want to achieve is that every edge has a different label.
The graceful labelling conjecture states that this is possible for every tree. For a star (a centre vertex with edges to all the other vertices), for example, this is very easy: Assign 1 to the centre vertex and the other numbers to the other vertices. For other trees it gets more difficult, and so far we do not know how to do this for every tree, even though the conjecture has received quite some attention in the research community.
This conjecture falls into the field of graph labelling questions, of which there are many others, and it is also connected to so-called graph packing problems, which is something I have worked on quite a bit.
Can computers assist in proof attempts?
Yes, that is one direction to go: Write a computer program to show that the conjecture holds for all trees up to a certain size. Different researchers have looked into this. The limitation is that even with clever ideas one does not get very far – computer search can so far only handle all trees with up to 35 vertices (because the number of different trees on 35 vertices is huge). But it is a promising sign that we did not find any counterexamples with up to 35 vertices.
Another direction people have investigated is restricting the focus to special types of trees, but again only with limited success. In general, the problem seems to be hard, although there recently have been some exciting new developments. One of my colleagues at LSE, Peter Allen, was involved in these and he and his co-authors managed to show that the conjecture “almost” holds. Here, “almost” means that you are allowed to use slightly larger labels and consider only trees that do not contain large stars. Their proof uses so-called probabilistic methods, which is a set of powerful modern tools in combinatorics. The graceful labelling conjecture has been around since the 1960’s, but only now do we see some serious progress on it.
Does the “almost” proof also give you a labelling or does it just prove the existence of a labelling?
The proof is constructive and because of the probabilistic methods gives a randomised algorithm for labelling a tree. That means you assign the labels randomly in a clever way. This description is oversimplifying as quite some work and adjustment is needed on top of this. But it is interesting that choosing labels in a randomised fashion is the key to succeeding here. This is something that we see in my research area a lot in recent years: randomised methods often help in solving long-standing problems.
Are people in extremal combinatorics also interested in recent computational progress (quantum computing, machine learning…) or is there an intersection where people are interested in both? Can these tools be helpful in proving or disproving conjectures?
I am not so sure about quantum computing. There are certainly connections, for example between quantum information theory and algebraic graph theory. But this is something that is not really my expertise.
As far as machine learning is concerned, this is something we are beginning to see now. Some groups of researchers are starting to investigate how machine learning algorithms can be used to find constructions of graphs with certain properties, with the goal of refuting certain conjectures or obtaining certain lower bound examples. One area where I could imagine this having real influence is that of Ramsey numbers, which we do not know precisely even for many small graphs.
If you would make a forecast: Will these emerging computational methods become relevant in your field in the next 10 years?
In the sense I described above they are likely to, I think (but how much remains to be seen). They are unlikely to help, for example, with proving the graceful labelling conjecture (if it is true) as this concerns trees that can be arbitrarily large.
One problem with the probabilistic techniques I mentioned earlier is that these only work once the graphs we are looking at are very large. And this is not just true for these techniques. Other methods that I use in my work, such as the famous so called regularity method, pioneered by the Abel prize winner Endre Szemerédi, only apply to graphs which have more vertices than the number of atoms in the universe.
So new computational methods could help in closing the gap that is left by applying these methods which only give results for gigantic graphs. On the other hand, for many such gaps it is unlikely that they can entirely be filled purely by computational methods, simply because they are so enormous.
Our department has a PhD to faculty ratio which is very different to most universities, in that the number of professors is much larger than the number of PhD students. What does that mean for the supervision of students in our department?
Hopefully the style of supervision compared to mathematics departments at other universities is not that different! In my experience it is the norm that mathematicians of my area work very closely with their PhD students. This would usually mean meeting each PhD student about once a week, having some projects together with them, but also supporting them in their own projects or projects with other collaborators. This is certainly how we like to handle PhD supervision here.
As you said, the number of PhD candidates in our department is comparatively small. The reason for this is mainly limitation in funding: We get lots of outstanding applicants each year, but can only offer funded positions to few of them. I like to think that as a result we have a very nice and friendly little group of PhD students. But it is certainly important that we encourage them to take opportunities to meet other PhD students or postdocs at conferences, and possibly also collaborate with them.
To students thinking about applying for a PhD position in mathematics I would say: Great that you are interested in mathematical research. For choosing the right place for doing your PhD, find out which direction and university really interests you, but also, if you can, try to get an insight in how supervision works in a chosen group. This is a very natural question to ask in an interview (sometimes it is even possible to talk to some current PhD students). And I believe it is a very important question for this decision.