TY - JOUR

T1 - Maximum induced subgraphs of the binomial random graph

AU - Balogh, J.

AU - Zhukovskii, M.

N1 - Funding Information:
Acknowledgment. The first author’s research is partially supported by NSF Grant DMS-1500121 and DMS-1764123, Arnold O. Beckman Research Award (UIUC Campus Research Board RB 18132) and the Langan Scholar Fund (UIUC). The second authors’s research is supported by the grant 16-11-10014 of Russian Science Foundation.
Publisher Copyright:
© 2019, Univerzita Komenskeho. All rights reserved.

PY - 2019/9/2

Y1 - 2019/9/2

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=85073775808&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85073775808&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:85073775808

VL - 88

SP - 423

EP - 427

JO - Acta Mathematica Universitatis Comenianae

JF - Acta Mathematica Universitatis Comenianae

SN - 0862-9544

IS - 3

ER -