On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices

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 paper, we consider the case where the graph $H$ is obtained by deleting a small number of vertices from a random Cayley graph $\tilde{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 $\tilde{H}$.

References in corpus (3)

• Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
• A Note on the Inducibility of 4-vertex Graphs
• A bound on the inducibility of cycles

Cited by in corpus (2)

• The inducibility of oriented stars
• Inducibility of 4-vertex tournaments