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

József Balogh; Andrzej Dudek; Lina Li

doi:10.1016/j.ejc.2020.103200

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

József Balogh
, Andrzej Dudek
, Lina Li

Mathematics

Research output: Contribution to journal › Article › peer-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 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.

Original language	English (US)
Article number	103200
Journal	European Journal of Combinatorics
Volume	91
DOIs	https://doi.org/10.1016/j.ejc.2020.103200
State	Published - Jan 2021

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Online availability

10.1016/j.ejc.2020.103200

Library availability

Discover UIUC Full Text

Cite this

@article{a45e54fdc172465894ec041ff44930da,

title = "An analogue of the Erd{\H o}s–Gallai theorem for random graphs",

abstract = "Recently, variants of many classical extremal theorems have been proved in the random environment. We, complementing existing results, extend the Erd{\H o}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.",

author = "J{\'o}zsef Balogh and Andrzej Dudek and Lina Li",

note = "Partially supported by NSF, USA Grant DMS-1764123 and Arnold O. Beckman Research Award (UIUC) Campus Research Board 18132, USA and the Langan Scholar Fund (UIUC), USA.Partially supported by Simons Foundation, USA Grant \#522400.",

year = "2021",

month = jan,

doi = "10.1016/j.ejc.2020.103200",

language = "English (US)",

volume = "91",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

}

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 - Partially supported by NSF, USA Grant DMS-1764123 and Arnold O. Beckman Research Award (UIUC) Campus Research Board 18132, USA and the Langan Scholar Fund (UIUC), USA.Partially supported by Simons Foundation, USA Grant #522400.

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 - https://www.scopus.com/pages/publications/85089825274

UR - https://www.scopus.com/pages/publications/85089825274#tab=citedBy

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 -

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

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this