A generalized Turán problem in random graphs. Issue 2 (10th June 2019) - Samotij, Wojciech; Shikhelman, Clara
Abstract : We study a generalization of the Turán problem in random graphs. Given graphs T and H, let ex( G ( n, p ), T, H ) be the largest number of copies of T in an H ‐free subgraph of G ( n, p ). We study the threshold phenomena arising in the evolution of the typical value of this random variable, for every H and every 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 ), proved several years ago by Conlon‐Gowers and Schacht; the case T  =  K m was previously resolved by Alon, Kostochka, and Shikhelman. The case when m 2 ( H ) ≤  m 2 ( T ) exhibits a more complex behavior. Here, 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 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.