ON CERTAIN SPANNING SUBGRAPHS OF RANDOM GRAPHS

Presented by Academician of the RAS V. V. Kozlov. An improvement of Riordan’s result on the threshold probability of the occurrence of a spanning subgraph in a random graph is obtained for some classes of subgraphs, which, in particular, implies an improved bound for the maximum power of a Hamiltonian cycle in a random graph. Moreover, the exact asymptotics of the threshold probability for the occurrence of spanning subgraphs from a wide class of k-degenerate graphs is found.