Talk information

Date: Sunday, October 26, 2025
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Raphael Yuster (University of Haifa)
Title: Inducibility in $H$-free graphs and inducibility of Turán graphs

Abstract:

A special case of our main result determines the inducibility of all graphs with maximum degree 1 (equivalently, all complete graphs missing a matching).

This extends a result of Liu, Mubayi, and Reiher who settled the case for all graphs containing a single edge (equivalently, all complete graphs missing an edge). Our result is obtained by considering the limiting inducibilities of certain graphs $F$ in $H$-free graphs, as $H$ varies. More details follow:

For graphs $F$ and $H$, let $i(F)$ denote the inducibility of $F$ and let $i_H(F)$ denote the inducibility of $F$ over $H$-free graphs. We prove that for almost all graphs $F$ on a given number of vertices, $i_{K_k}(F)$ attains infinitely many values as $k$ varies. For complete partite graphs $F$ (and, more generally, for symmetrizable families of graphs $F$), we prove that $i_H(F)=i_{K_k}(F)$ where $k=\chi(H)$, and is attained by some complete $\ell$-partite graphon $W_{F,k}$, where $\ell<k$.

We determine the part sizes of $W_{F,k}$ for all $k$, whence determine $i(F)$, whenever $F$ is the Turán graph on $s$ vertices and $r$ parts, for all $s\le 3r+1$, which was recently proved by Liu, Mubayi, and Reiher for $s=r+1$. As a corollary, this determines the inducibility of all Turán graphs on at most 14 vertices. Furthermore, since inducibility is invariant under complement, this determines the inducibility of all matchings and, more generally, all graphs with maximum degree 1, of any size. Similarly, this determines the inducibility of all triangle factors, of any size.

For complete partite graphs $F$ with at most one singleton part, we prove that $i_{K_k}(F)$ only attains finitely many values as $k$ varies; in particular, there exists $t=t(F)$ such that $i(F)$ is attained by some complete $t$-partite graphon. This is best possible as it was shown by Liu, Pikhurko, Sharifzadeh, and Staden that this is not necessarily true if there are two singleton parts.