Given a k-vertex graph H and an integer n, what are the n-vertex graphs with the maximum number of induced copies of H? This question is closely related to the inducibility problem introduced by Pippenger and Golumbic in 1975, which asks for the maximum possible fraction of k-vertex subsets of an n-vertex graph that induce a copy of H. Huang, Lee, and the first author proved that for a random k-vertex graph H, almost surely the n-vertex graphs maximizing the number of induced copies of H are the balanced iterated blow-ups of H. In this article, we consider the case where the graph H is obtained by deleting a small number of vertices from a random Cayley graph (Formula presented.) of an abelian group. We prove that in this case, almost surely all n-vertex graphs maximizing the number of induced copies of H are balanced iterated blow-ups of (Formula presented.).
All Science Journal Classification (ASJC) codes
- Computer Graphics and Computer-Aided Design
- Applied Mathematics
- Cayley graph
- random graph