Maximum Induced Trees and Forests of Bounded Degree in Random Graphs

ABSTRACT

The asymptotic behavior of the maximum sizes of induced trees and forests has been studied extensively in the last few decades, though the overall picture is far from being complete. In this paper, we close several significant gaps: (1) We prove 2‐point concentration of the maximum sizes of an induced forest and an induced tree with maximum degree at most in dense binomial random graphs with constant probability . (2) We show concentration in an explicit interval of size for the maximum size of an induced forest with maximum degree at most for . Our proofs rely on both a fairly standard second moment approach, with the probabilistic part involving Talagrand's concentration inequality and the analytical part involving saddle‐point analysis. Additionally, we present new results on the enumeration of labeled trees and forests, which might be of independent interest.