An analogue of the Erdős–Gallai theorem for random graphs. (January 2021) - Balogh, József
Abstract: Recently, variants of many classical extremal theorems have been proved in the random environment. We, complementing existing results, extend the Erdős–Gallai Theorem in random graphs. In particular, we determine, up to a constant factor, the maximum number of edges in a P n -free subgraph of G ( N, p ), 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.