TY - JOUR

T1 - On the sizes of large subgraphs of the binomial random graph

AU - Balogh, József

AU - Zhukovskii, Maksim

N1 - Funding Information:
The first author's research is partially supported by NSF Grants DMS-1500121 and DMS-1764123 , Arnold O. Beckman Research Award ( UIUC Campus Research Board RB 18132 ) and the Langan Scholar Fund ( UIUC ). The second author's research is supported by the Ministry of Science and Higher Education of the Russian Federation in the framework of MegaGrant no 075-15-2019-1926 .
Publisher Copyright:
© 2021

PY - 2022/2

Y1 - 2022/2

N2 - 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/lnn, and, for every ωn→∞, a.a.s. it is smaller than ωnn/lnn. 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)).

AB - 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/lnn, and, for every ωn→∞, a.a.s. it is smaller than ωnn/lnn. 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)).

KW - Induced subgraphs

KW - Large subgraphs

KW - Random graph

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

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

U2 - 10.1016/j.disc.2021.112675

DO - 10.1016/j.disc.2021.112675

M3 - Article

AN - SCOPUS:85117955654

SN - 0012-365X

VL - 345

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

M1 - 112675

ER -