Nikolas Mählmann

I am a postdoctoral researcher working at the University of Warsaw in the ERC project BUKA led by Prof. Szymon Toruńczyk. Before, I worked at the University of Bremen in the DFG project FAST led by Prof. Sebastian Siebertz, where I did my PhD thesis.

My research interests lie in the intersection of structural graph theory, logic, and algorithms. Currently I am studying monadically stable and monadically dependent classes of graphs and structures. Originating in model theory, those classes generalize many algorithmically tractable graph classes. Together with my collaborators, in a series of papers [4-7], we developed a combinatorial structure theory for monadically stable graph classes and showed that the FO Model Checking problem is fixed parameter tractable on those classes. Given a first-order logic sentence φ and a graph G, the goal is to decide whether φ is true on G. Due to the flexibility of first-order logic, an efficient algorithm for this problem can be used to solve a multitude of graph problems. My next goal is to extend our results to monadically dependent graph classes.

Email: maehlmann ♥ mimuw ♦ edu ♦ pl