The starting point of this talk will be the sequence of de Bruijn graphs, which can be seen as finite-word automata which remember the n most recently read letters. We pose the following decidability problem: given as input an arbitrary finite graph, decide whether or not it is a homomorphic image of some de Bruijn graph. We reached this question as an equivalent formulation of a rather different-looking decidability problem in modal-temporal logic, called unifiability. In joint work with J. Marti and M. Sweering, we use de Bruijn graphs and finite word combinatorics to show that both problems are decidable. Some of these techniques might be of interest to graph theorists, independently from the original logic motivation. Finally, I will pose an analogous hypergraph version of the problem, which can be shown to be equivalent to a major open problem in modal logic.

Continuation of part I. I intend to cover

1. applications of WQOs in algorithmic graph theory,
2. a focus on classes of graphs that are well-quasi-ordered by the induced subgraph ordering, along with Pouzet’s Conjecture,
3. the generalisation to preservation properties in first-order logic.

This will be a gentle tutorial on mostly standard results about well-quasi-orders (wqo) in a context of graph theory and algorithmic meta-theorems. I intend to cover a few basics of wqo theory, their applications in algorithmic graph theory, a focus on classes of graphs that are well-quasi-ordered by the induced subgraph ordering, along with Pouzet's Conjecture, and finally the generalisation to preservation properties in first-order logic.

.

In this tutorial we present a landscape of extensions of first-order logic (on graphs) and we discuss their expressive power and algorithmic results related to them. These extensions involve either additional predicates expressing different types of connectivity or the quantification over vertex sets that are (in a sense) of simple structure.