An analogue of the Erdős–Gallai theorem for random graphs. (January 2021)

• Record Type: Journal Article
• Authors: Balogh, József; Dudek, Andrzej; Li, Lina
• Is Part Of: European journal of combinatorics. Volume 91(2021)
• Publication Date: 2021-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2020.103200
• Languages: English
• ISSNs: 0195-6698

Abstract

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.