TY - JOUR
T1 - An analogue of the Erdős–Gallai theorem for random graphs
AU - Balogh, József
AU - Dudek, Andrzej
AU - Li, Lina
N1 - Publisher Copyright:
© 2020 Elsevier Ltd
PY - 2021/1
Y1 - 2021/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85089825274&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089825274&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2020.103200
DO - 10.1016/j.ejc.2020.103200
M3 - Article
AN - SCOPUS:85089825274
SN - 0195-6698
VL - 91
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
M1 - 103200
ER -