On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices. Issue 4 (23rd April 2021) - Fox, Jacob; Sauermann, Lisa; Wei, Fan
Abstract: 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 H ˜ 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 H ˜ .