Maximum induced subgraphs of the binomial random graph
Main Article Content
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
Issue
Section
EUROCOMB 2019