Edge version of the inducibility via the entropy method

Abstract

The inducibility of a graph $H$ is about the maximum number of induced copies of $H$ in a graph on $n$ vertices. We consider its edge version, that is, the maximum number of induced copies of $H$ in a graph with $m$ edges. Let $c(G,H)$ be the number of induced copies of $H$ in $G$ and $\ddot{I}(H,m)=\max \{c(G,H)\mid |E(G)|=m\}$. For any graph $H$, we prove that $\ddot{I}(H,m)=\hat{I}˜(m^{\hat{I}{\pm }_f(H)})$ where $\hat{I}{\pm }_f(H)$ is the fractional independence number of $H$. Therefore, we now focus on the constant factor in front of $m^{\hat{I}{\pm }_f(H)}$. In this paper, we give some results of $\ddot{I}(H,m)$ when $H$ is a cycle or path. We conjecture that for any cycle $C_k$ with $k\ge 5$, $\ddot{I}(C_k,m)=(1+o(1)){\left(m/k\right)}^{k/2}$ and the bound achieves by the blow up of $C_k$. For even cycles, we establish an upper bound with an extra constant factor. For odd cycles, we can only establish an upper bound with an extra factor depending on $k$. We prove that $\ddot{I}(P_{2l},m)\le \frac{m^l}{2(l-1{)}^{l-1}}$ and $\ddot{I}(P_{2l+1},m)\le \frac{m^{l+1}}{4l^l}$, where $l\ge 2$. We also conjecture the asymptotic value of $\ddot{I}(P_k,m)$. The entropy method is mainly used to prove our results.