Random induced graphs (Q1598829)

A property \(P\) of graphs is monotone if, whenever a graph \(G\) has \(P\), so does every subgraph of \(G\). Given a graph \(H\), the random induced graph \(G_{1/2}(H)\) is obtained by selecting vertices of \(H\) independently, with probability \(1/2\), and taking the subgraph of \(H\) induced by the selected vertex set. The authors are interested in the general question of how large \(d(n)\) should be to ensure that, for a given monotone property \(Q\), if \((H_n)\) is any sequence of graphs such that \(H_n\) has \(n\) vertices and minimum degree at least \(d(n)\), then almost every \(G_{1/2}(H_n)\) has property \(Q\). They prove essentially best-possible results when \(Q\) is the property that the graph is \(k\)-connected and when \(Q\) is the property that the graph is Hamiltonian showing that, in latter case, one can take \(d(n)\) to be \(n/2 + (2n\log n)^{1/2}\).