A generalized Turan problem in random graphs

被引:4
|
作者
Samotij, Wojciech [1 ]
Shikhelman, Clara [1 ]
机构
[1] Tel Aviv Univ, Sch Math Sci, IL-6997801 Tel Aviv, Israel
基金
以色列科学基金会;
关键词
random graphs; thresholds; Turan's theorem; RAMSEY PROPERTIES; EXTREMAL PROBLEM; NUMBER; SUBGRAPHS;
D O I
10.1002/rsa.20873
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
We study a generalization of the Turan 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 Erdos-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 Turan-type problems that we are unable to solve in full generality.
引用
收藏
页码:283 / 305
页数:23
相关论文
共 50 条
  • [21] Continuous spin models on annealed generalized random graphs
    Dommers, S.
    Kuelske, C.
    Schriever, P.
    STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2017, 127 (11) : 3719 - 3753
  • [22] Generalized Random Sequential Adsorption on Erdős–Rényi Random Graphs
    Souvik Dhara
    Johan S. H. van Leeuwaarden
    Debankur Mukherjee
    Journal of Statistical Physics, 2016, 164 : 1217 - 1232
  • [23] Limit laws for the number of triangles in the generalized random graphs with random node weights
    Liu, Qun
    Dong, Zhishan
    STATISTICS & PROBABILITY LETTERS, 2020, 161
  • [24] Generalized Random Sequential Adsorption on ErdAs-R,nyi Random Graphs
    Dhara, Souvik
    van Leeuwaarden, Johan S. H.
    Mukherjee, Debankur
    JOURNAL OF STATISTICAL PHYSICS, 2016, 164 (05) : 1217 - 1232
  • [25] Chromatic Thresholds in Dense Random Graphs
    Allen, Peter
    Bottcher, Julia
    Griffiths, Simon
    Kohayakawa, Yoshiharu
    Morris, Robert
    RANDOM STRUCTURES & ALGORITHMS, 2017, 51 (02) : 185 - 214
  • [26] Chromatic Thresholds in Sparse Random Graphs
    Allen, Peter
    Bottcher, Julia
    Griffiths, Simon
    Kohayakawa, Yoshiharu
    Morris, Robert
    RANDOM STRUCTURES & ALGORITHMS, 2017, 51 (02) : 215 - 236
  • [27] A HYPERGRAPH TURAN PROBLEM WITH NO STABILITY
    Liu, Xizhi
    Mubayi, Dhruv
    COMBINATORICA, 2022, 42 (03) : 433 - 462
  • [28] GENERALIZED TURAN PROBLEMS FOR EVEN CYCLES
    Gerbner, D.
    Gyori, E.
    Methuku, A.
    Vizer, M.
    ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, 2019, 88 (03): : 723 - 728
  • [29] The upper tail problem for induced 4-cycles in sparse random graphs
    Antonir, Asaf
    RANDOM STRUCTURES & ALGORITHMS, 2024, 64 (02) : 401 - 459
  • [30] Turan and Ramsey Properties of Subcube Intersection Graphs
    Johnson, J. Robert
    Markstrom, Klas
    COMBINATORICS PROBABILITY & COMPUTING, 2013, 22 (01): : 55 - 70