Projekte pro Jahr
Abstract
Given a large graph H, does the binomial random graph G(n, p) contain a copy of H as an induced subgraph with high probability? This classical question has been studied extensively for various graphs H, going back to the study of the independence number of G(n, p) by Erd\H os and Bollob\'as and by Matula in 1976. In this paper we prove an asymptotically best possible result for induced matchings by showing that if C/n \leq p \leq 0.99 for some large constant C, then G(n, p) contains an induced matching of order approximately 2 logq(np), where q = 1 1 p .
Originalsprache | englisch |
---|---|
Seiten (von - bis) | 267-280 |
Seitenumfang | 14 |
Fachzeitschrift | SIAM Journal on Discrete Mathematics |
Jahrgang | 35 |
Ausgabenummer | 1 |
DOIs | |
Publikationsstatus | Veröffentlicht - 2021 |
ASJC Scopus subject areas
- Allgemeine Mathematik
Fields of Expertise
- Information, Communication & Computing
Fingerprint
Untersuchen Sie die Forschungsthemen von „Large Induced Matchings in Random Graphs“. Zusammen bilden sie einen einzigartigen Fingerprint.Projekte
- 1 Abgeschlossen
-
FWF - Cores - Zufallsgraphen: Kerne, Färbungen und Ausbreitung
1/09/18 → 30/06/22
Projekt: Forschungsprojekt