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 条
  • [1] Random polynomial graphs for random Turan problems
    Spiro, Sam
    JOURNAL OF GRAPH THEORY, 2024, 105 (02) : 192 - 208
  • [2] A Turan-Type Problem on Distances in Graphs
    Tyomkyn, Mykhaylo
    Uzzell, Andrew J.
    GRAPHS AND COMBINATORICS, 2013, 29 (06) : 1927 - 1942
  • [3] A Generalized Turan Problem and its Applications
    Gishboliner, Lior
    Shapira, Asaf
    INTERNATIONAL MATHEMATICS RESEARCH NOTICES, 2020, 2020 (11) : 3417 - 3452
  • [4] A Generalized Turan Problem and Its Applications
    Gishboliner, Lior
    Shapira, Asaf
    STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2018, : 760 - 772
  • [5] Turan-type problems for long cycles in random and pseudo-random graphs
    Krivelevich, Michael
    Kronenberg, Gal
    Mond, Adva
    JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 2023, 107 (04): : 1519 - 1551
  • [6] Turan's theorem for pseudo-random graphs
    Kohayakawa, Yoshiharu
    Roedl, Vojtech
    Schacht, Mathias
    Sissokho, Papa
    Skokan, Jozef
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2007, 114 (04) : 631 - 657
  • [7] Unified approach to the generalized Turan problem and supersaturation
    Gerbner, Daniel
    Nagy, Zoltan Lorant
    Vizer, Mate
    DISCRETE MATHEMATICS, 2022, 345 (03)
  • [8] Inverting the Turan problem
    Briggs, Joseph
    Cox, Christopher
    DISCRETE MATHEMATICS, 2019, 342 (07) : 1865 - 1884
  • [9] An Extremal Property of Turan Graphs
    Lazebnik, Felix
    Tofts, Spencer
    ELECTRONIC JOURNAL OF COMBINATORICS, 2010, 17 (01):
  • [10] Limit laws in the generalized random graphs with random vertex weights
    Hu, Zhishui
    Bi, Wei
    Feng, Qunqiang
    STATISTICS & PROBABILITY LETTERS, 2014, 89 : 65 - 76