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 ind(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 ∈ ₖ, Kₖ\, then ind(H) ≤ 1 / e + oₖ(1). Equality holds for the star graph K1, k-1, the graph with a single edge on k vertices and their complements. We prove that for all other graphs H, we have ind(H) ≤ c + oₖ(1) for an absolute constant $c < 1 / 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₀ ⊆ V(H) of bounded size with the property that all permutations of V(H) V₀ extend to an automorphism of H.