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 条
  • [21] ESTIMATING MEAN OF A RANDOM BINOMIAL PARAMETER WITH TRIAL SIZE RANDOM
    VANRYZIN, J
    SANKHYA-THE INDIAN JOURNAL OF STATISTICS SERIES B, 1975, 37 (FEB): : 10 - 27
  • [22] On the maximum degree of a random planar graph
    McDiarmid, Colin
    Reed, Bruce
    COMBINATORICS PROBABILITY & COMPUTING, 2008, 17 (04): : 591 - 601
  • [23] THE DISTRIBUTION OF THE MAXIMUM DEGREE OF A RANDOM GRAPH
    BOLLOBAS, B
    DISCRETE MATHEMATICS, 1980, 32 (02) : 201 - 203
  • [24] ON THE MAXIMUM SIZE OF RANDOM TREES
    PROTASI, M
    TALAMO, M
    LECTURE NOTES IN COMPUTER SCIENCE, 1985, 185 : 139 - 144
  • [25] ON THE SIZE OF A RANDOM MAXIMAL GRAPH
    ERDOS, P
    SUEN, S
    WINKLER, P
    RANDOM STRUCTURES & ALGORITHMS, 1995, 6 (2-3) : 309 - 318
  • [26] MAXIMUM SIZE OF AN INDEPENDENT SET IN A GRAPH
    ALBERTSON, MO
    HUTCHINSON, JP
    NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY, 1975, 22 (01): : A39 - A40
  • [27] RANDOM GRAPH PROCESSES WITH MAXIMUM DEGREE 2
    Rucinski, A.
    Wormald, N. C.
    ANNALS OF APPLIED PROBABILITY, 1997, 7 (01): : 183 - 199
  • [28] THE SIZE OF THE LARGEST HOLE IN A RANDOM GRAPH
    LUCZAK, T
    DISCRETE MATHEMATICS, 1993, 112 (1-3) : 151 - 163
  • [29] On the size of a random sphere of influence graph
    Chalker, TK
    Godbole, AP
    Hitchzenko, P
    Radcliff, J
    Ruehr, OG
    ADVANCES IN APPLIED PROBABILITY, 1999, 31 (03) : 596 - 609
  • [30] On Estimating Maximum Matching Size in Graph Streams
    Assadi, Sepehr
    Khanna, Sanjeev
    Li, Yang
    PROCEEDINGS OF THE TWENTY-EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2017, : 1723 - 1742