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

József Balogh, Andrzej Dudek, Lina Li

Research output: Contribution to journalArticlepeer-review


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 Pn-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.

Original languageEnglish (US)
Article number103200
JournalEuropean Journal of Combinatorics
StatePublished - Jan 2021

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'An analogue of the Erdős–Gallai theorem for random graphs'. Together they form a unique fingerprint.

Cite this