Premium
A generalized Turán problem in random graphs
Author(s) -
Samotij Wojciech,
Shikhelman Clara
Publication year - 2020
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20873
Subject(s) - combinatorics , hypergraph , generalization , mathematics , random graph , value (mathematics) , expected value , discrete mathematics , type (biology) , graph , statistics , mathematical analysis , ecology , biology
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.