Maximum induced subgraphs of the binomial random graph

J. Balogh, M. Zhukovskii

Research output: Contribution to journalArticlepeer-review


We prove that a.a.s. the maximum size of an induced tree in the bi- nomial random graph G(n, p) is concentrated in four consecutive points. We also consider the following problem. Given e(k), what is the maximum k such that G(n, p) has an induced subgraph with k vertices and e(k) edges? For (Formula presented), we prove that a.a.s. this maximum size is concentrated in two consecutive points. In contrast, for e(k) = p(k/2)+O(k), we prove that this size is not concentrated in any finite set. Moreover, we prove that for an ωn→ ∞, a.a.s. the size of the concentration set is smaller than (Formula presented). Otherwise, for an arbitrary constant C > 0, a.a.s. it is bigger than (Formula presented).

Original languageEnglish (US)
Pages (from-to)423-427
Number of pages5
JournalActa Mathematica Universitatis Comenianae
Issue number3
StatePublished - Sep 2 2019

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'Maximum induced subgraphs of the binomial random graph'. Together they form a unique fingerprint.

Cite this