Maximum induced subgraphs of the binomial random graph

Main Article Content

Jozsef Balogh Maksim Zhukovskii

Abstract

We prove that a.a.s. the maximum size of an induced tree in the binomial 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 $e=o(\frac{k\ln k}{\ln\ln k})$, we prove that a.a.s. this maximum size is concentrated in two consecutive points. In contrast, for $e(k)=p{k\choose 2}+O(k)$, we prove that this size is not concentrated in any finite set. Moreover, we prove that for an $\omega_n\to\infty$, a.a.s.~the size of the concentration set is smaller than $\omega_n\sqrt{n/\ln n}$. Otherwise, for an arbitrary constant $C>0$, a.a.s.~it is bigger than $C\sqrt{n/\ln n}$.

Article Details

How to Cite
Balogh, J., & Zhukovskii, M. (2019). Maximum induced subgraphs of the binomial random graph. Acta Mathematica Universitatis Comenianae, 88(3), 423-427. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1217/666
Section
EUROCOMB 2019