A large part of research in algorithmic finite model theory focuses on Monadic Second-Order logic MSO and First-Order logic FO. At this point it is fairly well understood that MSO is tamed exactly on tree-like graphs, while delimiting the region of tameness of FO is the subject of a large on-going project, with the suspected dividing line provided by the notion of monadic dependence. However, between FO and MSO there is a large space for logics with intermediate expressive power, and correspondingly there is continuum of concepts in structural graph theory that are less restrictive than tree-likeness, but more restrictive than monadic dependence. During the talk we will discuss how this correspondence can be understood through the concept of monadic dependence with respect to a particular logic in question. We will also present the recent results and open questions related to logic FO+conn and its dense counterpart low rank MSO.

The Weisfeiler–Leman (WL) algorithm was initially designed as an incomplete approach to the graph isomorphism problem. In fact, it is a family of algorithms that together constitute a general combinatorial approach to identifying graphs and determining vertex properties. Indeed, WL subsumes many other ideas that researchers have explored over time. For example, despite being purely combinatorial, WL implicitly computes the eigenvalues of graphs. WL also features in Babai’s quasi-polynomial-time algorithm for computing isomorphisms.
Over time, it has become apparent that WL has a surprisingly wide range of application areas outside graph isomorphism testing. These include descriptive complexity theory (within finite model theory), the rapidly developing area of homomorphism counts, proof complexity, computational linear algebra, and, more recently, machine learning on graphs.
In this talk, I will give a gentle introduction to the algorithm and draw connections to its various application areas. I will then provide an overview of recent developments and showcase some results at the research frontier.

We introduce merge-width, a family of graph parameters that unifies several structural graph measures, including treewidth, degeneracy, twin-width, clique-width, and generalized coloring numbers. Graph classes of bounded merge-width include all classes of bounded expansion or of bounded twin-width – two central notions from the Sparsity and Twin-width frameworks. They are furthermore preserved under first-order transductions, which attests to their robustness. We conjecture that classes of bounded merge-width are equivalent to the previously introduced classes of bounded flip-width.
As our main result, we show that the model checking problem for first-order logic is fixed-parameter tractable on graph classes of bounded merge-width, assuming the input includes a witnessing construction sequence. This unites and extends two previous model checking results: the result of Dvořák, Kráľ, and Thomas for classes of bounded expansion, and the result of Bonnet, Kim, Thomassé, and Watrigant for classes of bounded twin-width. Finally, we discuss future research directions in structural and algorithmic graph theory, in particular in the study of monadically dependent graph classes, which we conjecture to coincide with classes of almost bounded merge-width. Joint work with Jan Dreier.