On the sizes of large subgraphs of the binomial random graph

József Balogh, Maksim Zhukovskii

Research output: Contribution to journalArticlepeer-review


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/ln⁡n, and, for every ωn→∞, a.a.s. it is smaller than ωnn/ln⁡n. 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 languageEnglish (US)
Article number112675
JournalDiscrete Mathematics
Issue number2
StatePublished - Feb 2022


  • Induced subgraphs
  • Large subgraphs
  • Random graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'On the sizes of large subgraphs of the binomial random graph'. Together they form a unique fingerprint.

Cite this