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 条
  • [11] On the independent set problem in random graphs
    Song, Yinglei
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2015, 92 (11) : 2233 - 2242
  • [12] Large cycles in random generalized Johnson graphs
    Kozhevnikov, V. S.
    Raigorodskii, A. M.
    Zhukovskii, M. E.
    DISCRETE MATHEMATICS, 2022, 345 (03)
  • [13] Applications of the Semi-Definite Method to the Turan Density Problem for 3-Graphs
    Falgas-Ravry, Victor
    Vaughan, Emil R.
    COMBINATORICS PROBABILITY & COMPUTING, 2013, 22 (01): : 21 - 54
  • [14] Generalized rainbow Turan problems
    Gerbner, Daniel
    Methuku, Abhishek
    Meszaros, Tamas
    Palmer, Cory
    ELECTRONIC JOURNAL OF COMBINATORICS, 2022, 29 (02):
  • [15] Canonical colourings in random graphs
    Kamcev, Nina
    Schacht, Mathias
    XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023, 2023, 224 : 5 - 12
  • [16] THE EVOLUTION OF RANDOM GRAPHS ON SURFACES
    Dowden, Chris
    Kang, Mihyun
    Spruessel, Philipp
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (01) : 695 - 727
  • [17] Spanning trees in random graphs
    Montgomery, Richard
    ADVANCES IN MATHEMATICS, 2019, 356
  • [18] An Extremal Property of Turan Graphs, II
    Tofts, Spencer N.
    JOURNAL OF GRAPH THEORY, 2014, 75 (03) : 275 - 283
  • [19] On Turan densities of small triple graphs
    Shi, Lingsheng
    EUROPEAN JOURNAL OF COMBINATORICS, 2016, 52 : 95 - 102
  • [20] ON WEAKLY TURAN-GOOD GRAPHS
    Gerbner, Daniel
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2024, 44 (04) : 1539 - 1550