Model theory, structural combinatorics, and algorithms

JUNIOR STAR - GACR GM24-12591M [Registered results] 2024 - 2028

Principal Investigator: Samuel Walker Braunfeld, Ph.D.

Our research will study the emerging connections between model theory and structural graph theory. Model theory provides a collection of concepts and tools for analyzing the complexity of infinite structures, and these are mirrored in the analysis of finite structures. For some time, this similarity seemed only analogical, but recent results have shown that the model-theoretic machinery can be finitized, and doing so recovers key definitions from structural graph theory and provides new and unified tools for proving results about them.

The main conjecture that serves to focus our efforts is algorithmic in nature: it identifies a certain model-theoretic property as characterizing the graph classes on which a wide swath of algorithmic problems (namely, those expressible in first-order logic) can be efficiently solved.

While most researchers active in the area approach from the combinatorial viewpoint, we plan to use our expertise to take a model-theoretic approach to this problem, and also to see how the combinatorial concepts can feed back into model theory.

Project Aim

  1. We plan to develop the interaction between model theory and structural graph theory, and in particular to (try to) solve a conjecture about graph classes that admit efficient algorithms.