AGH University mathematician: I look for beauty in graphs

Dr Marcin Stawiski from the Faculty of Applied Mathematics talked to us about his research on graph colouring, aesthetic categories in mathematics, and a way of thinking characteristic of the adepts of the queen of sciences, something that distinguishes them from representatives of other fields of knowledge.

Piotr Włodarczyk (AGH University Centre for Communication and Marketing): You specialise in an area of graph theory which has started being explored relatively recently, namely distinguishing colourings.

Dr Marcin Stawiski: It is not as new as one may think, as the first paper on the topic was published by Babai in 1977. Nevertheless, it has not seen much success among mathematicians and in some way it has been “forgotten” for a long period of time. Only in 1996, were distinguishing colourings introduced independently by Alberstone and Collins and passed into mathematical mainstream.

For mathematics, this is quite a short history.

Indeed, there are plenty of older issues. This one, however, it not the latest. There have already been a few hundred papers on the topic.

Let’s talk about the core of the problem.

Let’s start with the definition of a graph. It is an object consisting of a few points called vertices, where each pair of such points may be connected by an edge or not. Colouring graphs is simply assigning vertices or edges the right colour, so a certain label that we call a colour. In distinguishing colourings, we aim for the graph to be coloured in such a way that each symmetry results in a different colouring.  We may consider a distinguishing colouring with two connected vertices being the same colour as well as a colouring in which they cannot be the same, like in proper colouring.

What constitutes the main difficulty here?

In graph colouring, not only in the distinguishing type, it is usually about finding the smallest possible number of colours needed for colouring a given graph in a certain manner. Then, we must prove two things: firstly, that it is impossible to colour the graph with a smaller number of colours, and secondly, that we can always colour with the number of colours we indicate.

Please describe how such a process occurs.

In terms of colouring graphs, we always choose a given class of graphs, i.e. a set of graphs with specific properties. It may be linked to the number of vertices and edges. Usually, we strive for such a class to be the broadest possible, then we try to limit the number of colours essential for the class as much as we can or we take a narrower class but we try to find farther-reaching restrictions than in case of broader classes. The proofs we provide directly may sometimes take the form of an algorithm for a given colouring or they may show that a given colouring is possible but without indicating how it could look like.

As concerns algorithms, what is also often relevant is their practical use, as it is not enough for the graph to be coloured in a specific way, we should be able to do it quickly using our computers. Obtaining an optimal colouring, one that would be doable within an acceptable time, often turns out to be truly difficult. That is why we use approximation algorithms which may not always allow for colouring with the smallest number of colours, but they allow to do it quickly.

What class of graphs interests you the most?

In the majority of my studies I deal with infinite graphs, i.e. graphs which have an infinite number of vertices. What is relevant for me is whether a given class of graphs is intriguing. You may consider it in practical terms, so as regards its possible applications in mathematics, but also in other fields or in aesthetic terms.

Aesthetic, why?

It is about a certain kind of beauty which each mathematician understands differently. It may lie within the result obtained as well as in the reasoning behind it.

And what is it to you?

Obtaining the most optimal results for an interesting class of graphs. The beauty reveals itself in proofs, but also when we apply methods which have never been used before for obtaining a given result. Sometimes such a method is suitable only for a single proof, whereas another time it may prove to be useful in solving other problems.

What have your current considerations brought into the field?

I collaborated with Dr Florian Lehner from the University of Auckland (New Zealand), Professor Wilfried Imrich from the University of Graz (Austria), Dr Trevor Wilson from Miami University (USA), and mathematicians from the AGH University: Dr Jakub Kwaśny, Associate Professor Minika Pilśniak, and Associate Professor Rafał Kalinowski. With Monika Pilśniak, I managed to present an optimal restriction for a number of colours used in distinguishing colourings of infinite graphs due to the maximum degree of vertices, namely the number of other vertices a given vertex is connected with. A similar restriction, also an optimal one, was obtained for vertex colourings with Monika Pilśniak and Florian Lehner. I worked with Florian Lehner, Jakub Kwaśny, Monika Pilśniak, and Trevor Wilson on edge colourings of regular graphs, in which each vertex has the same degree. At the end, we managed to obtain an optimal restriction both for finite and infinite graphs.

However, recently, I have engaged in list colourings together with Jakub Kwaśny. These are the type of colourings with each vertex or an edge restricted to a particular list of allowed colours, and they may be coloured only with a colour from its own list. Actually, each type of colouring may also be done this way.

How does the work of a mathematician look like today? Is it more computer-related or pen-and-paper style?

The most of my work takes place in my head. Only when I manage to come across a more distinct, specific outline of reasoning do I turn to a piece of paper of a computer. It differs when I collaborate with other mathematicians, then we mostly discuss and use a board.

What attracted you to the university?

I was interested in mathematics as early as the primary school. My brother was particularly impactful in this regard because he made me realise that it is a significant and a fascinating field of knowledge. For some time, both physics and chemistry absorbed me, but when it came down to choosing my path at university I have decided to study mathematics at the AGH University and I have never looked back. At the second-cycle programme, I was occupied with mathematics in finance and insurance. Back then, I was most enthusiastic about probability calculus and statistics to which I dedicated my master’s thesis. Only during my last year of the programme have I decided to deal with the theory of graphs. I noticed that I associated plenty of curious, unsolved problems with it, so I have thought I could see to them. I do not regret this decision.

How would you encourage others to study mathematics?

Above all, studying mathematics develops a particular, analytical and formal way of thinking which is not emphasised enough in other fields of study, for example in engineering.

What do you mean by the formal way of thinking? Why can’t a mathematician be free in their deliberations?

A mathematician must be meticulous and precise. It happens a lot in other fields, but in this case, inaccuracy in thinking is out of question.

I thought only humanists have their heads in the clouds.

Wrong. Even theoretical physicists frequently use methods which are not explicitly mathematical, the ones that would be considered unacceptable among mathematicians.