Name
Abstract | ||
|---|---|---|
We consider the binomial random graph G(n, p), where p is a constant, and answer the following two questions. First, given e(k) = p((k)(2))+ O(k), what is the maximum k such that a.a.s. the binomial random 2 graph G(n, p) has an induced subgraph with k vertices and e(k) edges? We prove that this maximum is not concentrated in any finite set (in contrast to the case of a small e(k)). Moreover, for every constant C > 0, with probability bounded away from 0, the size of the concentration set is bigger than C root n/ lnn, and, for every omega(n) -> infinity, a.a.s. it is smaller than omega root nn/ lnn. Second, given k > epsilon n, what is the maximum mu such that a.a.s. the set of sizes of k vertex subgraphs of G(n, p) contains a full interval of length mu? The answer is mu = Theta(root(n - k)n ln ((n)(k)) (c) 2021 Published by Elsevier B.V. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1016/j.disc.2021.112675 | DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
Random graph, Induced subgraphs, Large subgraphs | Journal | 345 |
Issue | ISSN | Citations |
2 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| József Balogh | 1 | 862 | 89.91 |
| Maksim Zhukovskii | 2 | 2 | 4.51 |