EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Finding Long Cycles in Percolated Expander Graphs

Lawrence Hollom

Random Structures & Algorithms · 2026-05 · 68 (3)

DOI: 10.1002/rsa.70070 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 14.05.2026. Verfasst von Lawrence Hollom. Die Arbeit nennt 12 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Trinity College, University of Cambridge.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Given a graph , the percolated graph is formed by retaining each edge independently with probability . Collares, Diskin, Erde, and Krivelevich initiated the study of large structures in percolated single‐scale vertex‐expander graphs, wherein every set of exactly vertices of has at least neighbors before percolation. We extend their result to a conjectured stronger form, proving that if and is a graph on at least vertices which expands as above, then contains a cycle of length with probability at least as .

Förderung

  • Trinity College, University of Cambridge

Zitieren

APA

Hollom, L. (2026). Finding Long Cycles in Percolated Expander Graphs. Random Structures & Algorithms, 68(3). https://doi.org/10.1002/rsa.70070

Vancouver

Hollom L. Finding Long Cycles in Percolated Expander Graphs. Random Structures & Algorithms. 2026;68(3). doi:10.1002/rsa.70070

BibTeX
@article{Hollom2026,
  author = {Hollom, Lawrence},
  title = {Finding Long Cycles in Percolated Expander Graphs},
  journal = {Random Structures & Algorithms},
  year = {2026},
  volume = {68},
  number = {3},
  doi = {10.1002/rsa.70070}
}
Kostenlos starten →