Doctoral colloquium - Pavol Kollár (26.10.2026)
Monday 26.10.2026 at 13:10, Lecture room I 9
Pavol Kollár:
How do computers assist in Graph Theory?
Abstract:
Graph theory and graphs specifically pop up all over the place in the world; from road and social networks, scheduling problems, all the way to dependency structures. Recently, with all the incredible new results and supposed results from AI - i.e. computers - computer-assisted graph theory becomes more relevant than ever. For example, during the summer of 2026 the long standing and famous "Petersen colouring conjecture" has been disproven by an example conjured up by AI, which was the catalyst for proper examination and lead to an improved and fully proved result.
In this talk, we will report on our previous progress and show two graph theory problems that can be computer-assisted in the more "classical" sense - using algorithms to compute properties about specified graphs and exhaustively enumerate all graphs of a specified type. Of course, using just any algorithm is bound to fail, because the space of possibilities in these problems is too vast. And when simple ideas and brute force fail, clever ideas come out of hiding.