Maximum sparse induced subgraphs of the binomial random graph with given number of edges (Q2214056): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Changed an Item |
||
Property / arXiv ID | |||
Property / arXiv ID: 1910.09044 / rank | |||
Normal rank |
Revision as of 03:21, 19 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Maximum sparse induced subgraphs of the binomial random graph with given number of edges |
scientific article |
Statements
Maximum sparse induced subgraphs of the binomial random graph with given number of edges (English)
0 references
4 December 2020
0 references
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.
0 references
random graph
0 references
maximum induced subgraphs
0 references
maximum induced tree
0 references