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 条
  • [41] Sprinkling with random regular graphs*
    Isaev, Mikhail
    Mckay, Brendan D.
    Southwell, Angus
    Zhukovskii, Maksim
    ELECTRONIC JOURNAL OF PROBABILITY, 2025, 30 : 1 - 20
  • [42] Distributed algorithms for random graphs
    Krzywdzinski, K.
    Rybarczyk, K.
    THEORETICAL COMPUTER SCIENCE, 2015, 605 : 95 - 105
  • [43] ON THE KLR CONJECTURE IN RANDOM GRAPHS
    Conlon, D.
    Gowers, W. T.
    Samotij, W.
    Schacht, M.
    ISRAEL JOURNAL OF MATHEMATICS, 2014, 203 (01) : 535 - 580
  • [44] Random planar graphs and beyond
    Noy, Marc
    PROCEEDINGS OF THE INTERNATIONAL CONGRESS OF MATHEMATICIANS (ICM 2014), VOL IV, 2014, : 407 - 430
  • [45] Spanning universality in random graphs
    Ferber, Asaf
    Nenadov, Rajko
    RANDOM STRUCTURES & ALGORITHMS, 2018, 53 (04) : 604 - 637
  • [46] Note on a Turan-type problem on distances
    Li, Xueliang
    Ma, Jing
    Shi, Yongtang
    Yue, Jun
    ARS COMBINATORIA, 2015, 119 : 211 - 219
  • [47] A Brualdi-Hoffman-Turan problem on cycles
    Li, Xin
    Zhai, Mingqing
    Shu, Jinlong
    EUROPEAN JOURNAL OF COMBINATORICS, 2024, 120
  • [48] A Non-aligning Variant of Generalized Turan Problems
    Gerbner, Daniel
    ANNALS OF COMBINATORICS, 2024, 28 (02) : 351 - 366
  • [49] SOME STABILITY AND EXACT RESULTS IN GENERALIZED TURaN PROBLEMS
    Gerbner, Daniel
    STUDIA SCIENTIARUM MATHEMATICARUM HUNGARICA, 2023, 60 (01) : 16 - 26
  • [50] RANDOM GRAPHS WITH A RANDOM BIJECTION
    Anbo, Yuki
    TSUKUBA JOURNAL OF MATHEMATICS, 2011, 35 (01) : 143 - 151