Counting induced subgraphs with given intersection sizes

Abstract

Let $F$ be a graph of order $r$. In this paper, we study the maximum number of induced copies of $F$ with restricted intersections, which highlights the motivation from extremal set theory. Let $L=\{{\ell }_1,\dots ,{\ell }_s\}\subseteq [0,r-1]$ be an integer set with $s\notin \{1,r\}$. Let $\hat{I}{¨}_r(n,F,L)$ be the maximum number of induced copies of $F$ in an $n$-vertex graph, where the induced copies of $F$ are $L$-intersecting as a family of $r$-subsets, i.e., for any two induced copies of $F$, the size of their intersection is in $L$. Helliar and Liu initiated a study of the function $\hat{I}{¨}_r(n,K_r,L)$. Very recently, Zhao and Zhang improved their result and showed that $\hat{I}{¨}_r(n,K_r,L)=\hat{I}{˜}_{r,L}(n^s)$ if and only if ${\ell }_1,\dots ,{\ell }_s,r$ form an arithmetic progression. In this paper, we show that $\hat{I}{¨}_r(n,F,L)=o_{r,L}(n^s)$ when ${\ell }_1,\dots ,{\ell }_s,r$ do not form an arithmetic progression. We study the asymptotical result of $\hat{I}{¨}_r(n,C_r,L)$, and determined the asymptotically optimal result when ${\ell }_1,\dots ,{\ell }_s,r$ form an arithmetic progression and take certain values. We also study the generalized Turán problem, determining the maximum number of $H$, where the copies of $H$ are $L$-intersecting as a family of $r$-subsets. The entropy method is used to prove our results.