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 条
  • [31] Additive Approximation of Generalized Turan Questions
    Alon, Noga
    Shikhelman, Clara
    ALGORITHMICA, 2022, 84 (02) : 464 - 481
  • [32] On the variational problem for upper tails in sparse random graphs
    Lubetzky, Eyal
    Zhao, Yufei
    RANDOM STRUCTURES & ALGORITHMS, 2017, 50 (03) : 420 - 436
  • [33] The generalized acyclic edge chromatic number of random regular graphs
    Gerke, Stefanie
    Greenhill, Catherine
    Wormald, Nicholas
    JOURNAL OF GRAPH THEORY, 2006, 53 (02) : 101 - 125
  • [34] Some sharp results on the generalized Turan numbers
    Ma, Jie
    Qiu, Yu
    EUROPEAN JOURNAL OF COMBINATORICS, 2020, 84
  • [35] Some results on k-Turan-good graphs
    Qian, Bingchen
    Xie, Chengfei
    Ge, Gennian
    DISCRETE MATHEMATICS, 2021, 344 (09)
  • [36] Inverting the Turan problem with chromatic number
    Zhu, Xiutao
    Chen, Yaojun
    DISCRETE MATHEMATICS, 2021, 344 (09)
  • [37] Generalized Turan Number of Even Linear Forests
    Zhu, Xiutao
    Zhang, Fangfang
    Chen, Yaojun
    GRAPHS AND COMBINATORICS, 2021, 37 (04) : 1437 - 1449
  • [38] Phase Transitions for the Cavity Approach to the Clique Problem on Random Graphs
    Gaudilliere, Alexandre
    Scoppola, Benedetto
    Scoppola, Elisabetta
    Viale, Massimiliano
    JOURNAL OF STATISTICAL PHYSICS, 2011, 145 (05) : 1127 - 1155
  • [39] Phase Transitions for the Cavity Approach to the Clique Problem on Random Graphs
    Alexandre Gaudillière
    Benedetto Scoppola
    Elisabetta Scoppola
    Massimiliano Viale
    Journal of Statistical Physics, 2011, 145 : 1127 - 1155
  • [40] CYCLE SATURATION IN RANDOM GRAPHS
    Demidovich, Yury
    Skorkin, Arkadiy
    Zhukovskii, Maksim
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2023, 37 (03) : 1359 - 1385