Back to Search
Start Over
The largest hole in sparse random graphs.
- Source :
- Random Structures & Algorithms; Dec2022, Vol. 61 Issue 4, p666-677, 12p
- Publication Year :
- 2022
-
Abstract
- We show that for any d=d(n) with d0(ϵ)≤d=o(n), with high probability, the size of a largest induced cycle in the random graph G(n,d/n) is (2±ϵ)ndlogd. This settles a long‐standing open problem in random graph theory. [ABSTRACT FROM AUTHOR]
- Subjects :
- SPARSE graphs
RANDOM graphs
GRAPH theory
Subjects
Details
- Language :
- English
- ISSN :
- 10429832
- Volume :
- 61
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- Random Structures & Algorithms
- Publication Type :
- Academic Journal
- Accession number :
- 159936397
- Full Text :
- https://doi.org/10.1002/rsa.21078