A generalized Turán problem in random graphs

Abstract

We study the following generalization of the Turán problem in sparse random graphs. Given graphs $T$ and $H$, let $\mathrm{ex}(G(n,p),T,H)$ be the random variable that counts the largest number of copies of $T$ in a subgraph of $G(n,p)$ that does not contain $H$. We study the threshold phenomena arising in the evolution of the typical value of this random variable, for every $H$ and an arbitrary $2$-balanced $T$. Our results in the case when $m_2(H)>m_2(T)$ are a natural generalization of the Erdős--Stone theorem for $G(n,p)$, which was proved several years ago by Conlon and Gowers and by Schacht; the case $T=K_m$ has been recently resolved by Alon, Kostochka, and Shikhelman. More interestingly, the case when $m_2(H)\le m_2(T)$ exhibits a more complex and subtle behavior. Namely, the location(s) of the (possibly multiple) threshold(s) are determined by densities of various coverings of $H$ with copies of $T$ and the typical value(s) of $\mathrm{ex}(G(n,p),T,H)$ are given by solutions to deterministic hypergraph Turán-type problems that we are unable to solve in full generality.