The Inducibility of Graphs on Four Vertices

We consider the problem of determining the maximum induced density of a graph H in any graph on n vertices. The limit of this density as n tends to infinity is called the inducibility of H . The exact value of this quantity is known only for a handful of small graphs and a specific set of complete multipartite graphs. Answering questions of Brown–Sidorenko and Exoo, we determine the inducibility of K 1, 1, 2 and the paw graph. The proof is obtained using semidefinite programming techniques based on a modern language of extremal graph theory, which we describe in full detail in an accessible setting.