PC Seminar: Maximum induced subgraphs in Erdős-Rényi random graph model

Abstract: In the Erdős--Rényi random graph model \( G(n, p) \), a two-point concentration phenomenon is observed for the maximum size of induced subgraphs from various graph classes when \( p = \text{const} \). These include independent sets, forests, trees, cycles, bounded-degree graphs, and graphs with a bounded number of edges. When \( p \to 0 \), the same classes exhibit precise asymptotic behavior.

In this talk, I present new results for \emph{bounded-degree trees and forests}, showing that they also exhibit two-point concentration. Furthermore, we prove that for general forests, the maximum induced size is concentrated in a window of width \( o(1/p) \), provided \( \frac{1}{n} \ll p \ll 1 \).

These results are based on joint work with Vladislav Kozhevnikov and Maxim Zhukovskii.

This is a seminar in our seminar series on Probability and Combinatorics (PC).