RUS  ENG
Full version
JOURNALS // Doklady Rossijskoj Akademii Nauk. Mathematika, Informatika, Processy Upravlenia // Archive

Dokl. RAN. Math. Inf. Proc. Upr., 2024 Volume 516, Pages 83–86 (Mi danma517)

MATHEMATICS

Maximum induced trees in sparse random graphs

J. C. Buitrago Oropeza

Moscow Institute of Physics and Technology (National Research University), Dolgoprudny, Moscow Region

Abstract: We prove that for any $\varepsilon>0$ and $n^{-(e-2)/(3e-2)+\varepsilon}\le p = o(1)$ the maximum size of an induced subtree of the binomial random graph $G{n,p}$ is concentrated in 2 consecutive points.

Keywords: binomial random graph, maximum subgraph, concentration.

UDC: 519.175.4

Presented: V. V. Kozlov
Received: 13.03.2024
Revised: 28.03.2024
Accepted: 01.04.2024

DOI: 10.31857/S2686954324020133


 English version:
Doklady Mathematics, 2024, 109:2, 167–169

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025