Characterizing graphs with high inducibility

For a positive integer $k$ and a graph $H$ on $k$ vertices, we are interested in the inducibility of $H$, denoted $\mathrm{i}\mathrm{n}\mathrm{d}(H)$, which is defined as the maximum possible probability that choosing $k$ vertices uniformly at random from a large graph $G$, they induce a copy of $H$. It follows from the resolved Edge-statistics conjecture that if $H\in ̸\{K_k,{\bar{K}}_k\}$, then $\mathrm{i}\mathrm{n}\mathrm{d}(H)\le 1\mathrm{/}e+o_k(1)$. Equality holds for the star graph $K_{1,k-1}$, the graph with a single edge on $k$ vertices and their complements. We prove that for all other graphs $H$, we have $\mathrm{i}\mathrm{n}\mathrm{d}(H)\le c+o_k(1)$ for an absolute constant $c<1\mathrm{/}e$. Moreover, we explicitly characterize all graphs with inducibility bounded away from zero. Namely, we show that this is the class of graphs $H$ for which there is a set $V_0\subseteq V(H)$ of bounded size with the property that all permutations of $V(H)\mathrm{\backslash }{V}_0$ extend to an automorphism of $H$.