Maximum sparse induced subgraphs of the binomial random graph with given number of edges (Q2214056)

The paper under review considers the largest induced subtree in the Erdős-Rényi random graph \(G(n,p)\) with vertex set \(\{1,2,\ldots, n\}\) and each pair of vertices adjacent with probability \(p=p(n)\) independent of all other pairs. The main result of the paper is that there is an \(\varepsilon >0\) such that the order of the largest induced tree is either \(f_{\varepsilon}(n)\) or \(f_{\varepsilon}(n)+1\) where \(f_{\varepsilon}(n)=\lfloor 2\log_{1/(1-p)}(enp)+2+\varepsilon \rfloor\) -- a two-point concentration result. This generalises a result from [\textit{K. Dutta} and \textit{C. R. Subramanian}, in: Proceedings of the 15th workshop on analytic algorithmics and combinatorics, ANALCO '18, New Orleans, LA, January 8--9, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 168--177 (2018; Zbl 1433.05279)] for induced paths (and cycles). The argument is basically a quite involved second moment method argument, technicalities arising from the fact that there are four different regimes for where the maximum of a key function is attained. The authors also consider a two-point concentration result for the maximum order of a set of \(k\) vertices which induces exactly \(t(k)\) edges where \(t(k)<\varepsilon k^{2}\) for some \(\varepsilon >0\). Summarising the result slightly imprecisely, it is that provided \(t\) has some mild smoothness properties, there is a function \(f(n)\), close to \(2\log_{1/(1-p)}(n)\), for which this maximum order is either \(f(n)\) or \(f(n)+1\). Again the calculation depends on quite delicate estimation of relevant quantities.