In computable structure theory, countable graphs are prized as algorithmically universal structures: any computability-theoretic property found in an arbitrary structure can likely be mirrored within a graph. While the general computability of these structures is well-understood, much less is known about specific subclasses. Given a finite graph \(\mathcal{F}\), we consider the class \(\mathsf{Free}(\mathcal{F})\) of graphs that do not contain \(\mathcal{F}\) as an induced subgraph. In this talk, we will first survey what is known about the computability properties of graphs in general, and then proceed to the restricted case of these \(\mathsf{Free}(\mathcal{F})\) classes.

For finite graphs, this restriction yields a well-known structural dichotomy centered entirely around \(\mathcal{P}_4\), the path on four vertices. We expand this line of research to infinite countable graphs using the tools of computable structure theory and descriptive set theory. In the infinite setting, \(\mathcal{P}_4\) remains the central character of structural dichotomies for classes of the form \(\mathsf{Free}(\mathcal{F})\). Specifically, \(\mathsf{Free}(\mathcal{F})\) is \(\Sigma\)-small, satisfies the computable embeddability condition, and is not on top for bi-interpretability if and only if \(\mathsf{Free}(\mathcal{F})\) is a subclass of \(\mathsf{Free}(\mathcal{P}_4)\). Furthermore, we introduce a new phenomenon unique to the infinite case: \(\mathsf{Free}(\mathcal{P}_4)\) is on top for Borel reducibility but not for effective bi-interpretability, making it the unique class among all choices of \(\mathcal{F}\) to occupy this position.

This is joint work with Vittorio Cipriani, Matthew Harrison-Trainor, Liling Ko, and Dino Rossegger.