An analogue of the Erdős-Gallai theorem for random graphs

József Balogh, Andrzej Dudek, Lina Li

Published 2019-08-31Version 1

Recently, variants of many classical extremal theorems are proved in random environment. We, complementing existing results, extend the Erd\H{o}s-Gallai Theorem in random graphs. In particular, we determine, up to a constant factor, the extremal function in $G(N,p)$ for containing a path $P_n$, practically for all values of $N,n$ and $p$. Our work is also motivated by the recent progress on the size-Ramsey number of paths.