Trees in random graphs (Q790843): Difference between revisions

The probability space consisting of all graphs on a set of \(n\) vertices where each edge occurs with probability \(p\), independently of all other edges, is denoted by \(G(n,p)\). Theorem: For each \(\epsilon>0\) almost every graph \(G\in G(n,p)\) is such if \((1+\epsilon)\log n/\log d<r<(2- \epsilon)\log n/\log d\) where \(d=1/(1-p),\) then \(G\) contains a maximal induced tree of order \(d\). Problem: Let \(p\) be a function of \(n\), find such a value of \(p\) for which a graph \(G\in G(n,p)\) has the greatest induced tree.