A generalized Turán problem in random graphs. Issue 2 (10th June 2019)

• Record Type: Journal Article
• Authors: Samotij, Wojciech; Shikhelman, Clara
• Is Part Of: Random structures & algorithms. Volume 56:Issue 2(2020)
• Page Start: 283
• Page End: 305
• Publication Date: 2019-06-10
• Subjects: random graphs -- thresholds -- Turán's theorem; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20873
• Languages: English
• ISSNs: 1042-9832

Abstract

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.