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

József Balogh, Andrzej Dudek, Lina Li

Research output: Contribution to journalArticlepeer-review

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 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
Volume91
DOIs
StatePublished - Jan 2021

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

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