The maximum size of an induced forest in the binomial random graph

被引:0
|
作者
Akhmejanova, Margarita [1 ]
Kozhevnikov, Vladislav [2 ]
机构
[1] King Abdullah Univ Sci & Technol KAUST, Comp Elect & Math Sci & Engn Div, Thuwal 239556900, Saudi Arabia
[2] Moscow Inst Phys & Technol, Lab Combinatorial & Geometr Struct, Dolgoprudnyi, Russia
基金
俄罗斯科学基金会;
关键词
Random graph; Induced forest; Frieze; G(n; p); Induced graph; Maximum induced forest; LARGEST INDUCED TREE;
D O I
10.1016/j.disc.2024.114030
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
The celebrated Frieze's result about the independence number of G ( n , p ) states that it is concentrated in an interval of size o ( 1 / p ) for all C- epsilon / n < p = o ( 1 ) . We show concentration in an interval of size o ( 1 / p ) for the maximum size (number of vertices) of an induced forest in G ( n , p ) for all C- epsilon / n < p < 1 - epsilon . Presumably, it is the first generalization of Frieze's result to another class of induced subgraphs for such a range of p .
引用
收藏
页数:11
相关论文
共 50 条
  • [1] MAXIMUM INDUCED SUBGRAPHS OF THE BINOMIAL RANDOM GRAPH
    Balogh, J.
    Zhukovskii, M.
    ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, 2019, 88 (03): : 423 - 427
  • [2] Maximum sparse induced subgraphs of the binomial random graph with given number of edges
    Kamaldinov, Dmitry
    Skorkin, Arkadiy
    Zhukovskii, Maksim
    DISCRETE MATHEMATICS, 2021, 344 (02)
  • [3] On the Distribution of the Maximum k-Degrees of the Binomial Random Graph
    Zhukovskii, M. E.
    Rodionov, I. V.
    DOKLADY MATHEMATICS, 2018, 98 (03) : 619 - 621
  • [4] On the Distribution of the Maximum k-Degrees of the Binomial Random Graph
    M. E. Zhukovskii
    I. V. Rodionov
    Doklady Mathematics, 2018, 98 : 619 - 621
  • [5] The maximum tree of a random forest in the configuration graph
    Pavlov, Yu L.
    SBORNIK MATHEMATICS, 2021, 212 (09) : 1329 - 1346
  • [6] The size of the giant joint component in a binomial random double graph
    Jerrum, Mark
    Makai, Tamas
    ELECTRONIC JOURNAL OF COMBINATORICS, 2021, 28 (01): : 1 - 23
  • [7] Limit distributions of the maximum size of a tree in a random forest
    Pavlov, Yu.L.
    Discrete Mathematics and Applications, 5 (04):
  • [8] On the maximum size of a tree in a random unlabelled unrooted forest
    Bernikovich, E. S.
    Pavlov, Yu. L.
    DISCRETE MATHEMATICS AND APPLICATIONS, 2011, 21 (01): : 1 - 21
  • [9] The Size of a Maximum Subgraph of the Random Graph with a Given Number of Edges
    N. M. Derevyanko
    M. E. Zhukovskii
    M. Rassias
    A. Yu. Skorkin
    Doklady Mathematics, 2019, 100 : 478 - 479
  • [10] The Size of a Maximum Subgraph of the Random Graph with a Given Number of Edges
    Derevyanko, N. M.
    Zhukovskii, M. E.
    Rassias, M.
    Skorkin, A. Yu.
    DOKLADY MATHEMATICS, 2019, 100 (02) : 478 - 479