Some Exact Inducibility-type Results for Graphs via Flag Algebras

Abstract

The $(\kappa,\ell)$-edge-inducibility problem asks for the maximum number of $\kappa$-subsets inducing exactly $\ell$ edges that a graph of given order $n$ can have. Using flag algebras and stability approach, we resolve this problem for all sufficiently large $n$ (including a description of all extremal and almost extremal graphs) in eleven new non-trivial cases when $\kappa\le 7$.

We also compute the $F$-inducibility constant (the asymptotically maximum density of induced copies of $F$ in a graph of given order $n$) and obtain some corresponding structure results for three new graphs $F$ with $5$ vertices: the 3-edge star plus an isolated vertex, the 4-cycle plus an isolated vertex, and the 4-cycle with a pendant edge.