Inducibility of the Net Graph

Abstract

A graph $F$ is called a fractalizer if for all $n$ the only graphs which maximize the number of induced copies of $F$ on $n$ vertices are the balanced iterated blow ups of $F$. While the net graph is not a fractalizer, we show that the net is nearly a fractalizer. Let $N(n)$ be the maximum number of induced copies of the net graph among all graphs on $n$ vertices. For sufficiently large $n$ we show that, $N(n)=x_1\cdot x_2\cdot x_3\cdot x_4\cdot x_5\cdot x_6+N(x_1)+N(x_2)+N(x_3)+N(x_4)+N(x_5)+N(x_6)$ where $\sigma x_i=n$ and all $x_i$ are as equal as possible. Furthermore, we show that the unique graph which maximizes $N(6^k)$ is the balanced iterated blow up of the net for $k$ sufficiently large. We expand on the standard flag algebra and stability techniques through more careful counting and numerical optimization techniques.

References in corpus (1)

• The inducibility of oriented stars