## 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(k2)+O(k), what is the maximum k such that a.a.s. the binomial random 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 Cn/lnn, and, for every ω_{n}→∞, a.a.s. it is smaller than ω_{n}n/lnn. Second, given k>εn, what is the maximum μ such that a.a.s. the set of sizes of k-vertex subgraphs of G(n,p) contains a full interval of length μ? The answer is μ=Θ((n−k)nln(nk)).

Original language | English (US) |
---|---|

Article number | 112675 |

Journal | Discrete Mathematics |

Volume | 345 |

Issue number | 2 |

DOIs | |

State | Published - Feb 2022 |

## Keywords

- Induced subgraphs
- Large subgraphs
- Random graph

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics