Verlagslink DOI: 10.19086/aic.12849
arXiv ID: 1612.00661v2
Titel: The bandwidth theorem in sparse graphs
Sprache: Englisch
Autor/Autorin: Allen, Peter 
Böttcher, Julia 
Ehrenmüller, Julia 
Taraz, Anusch 
Erscheinungs­datum: 15-Mai-2020
Verlag: Alliance of Diamond Open Access Journals
Quellenangabe: Advances in Combinatorics 1 (2020): 6, 1-60 (2020)
Zusammenfassung (englisch): 
The bandwidth theorem [Mathematische Annalen, 343(1):175–205, 2009] states that any n-vertex graph G with minimum degree [Formula Presented] contains all n-vertex k-colourable graphs H with bounded maximum degree and bandwidth o(n). We provide sparse analogues of this statement in random graphs as well as pseudorandom graphs. More precisely, we show that for p ≫[Formula Presented] asymptotically almost surely each spanning subgraph G of G(n, p) with minimum degree [Formula Presented] pn contains all n-vertex k-colourable graphs H with maximum degree ∆, bandwidth o(n), and at least Cp−2 vertices not contained in any triangle. A similar result is shown for sufficiently bijumbled graphs, which, to the best of our knowledge, is the first resilience result in pseudorandom graphs for a rich class of spanning subgraphs. Finally, we provide improved results for H with small degeneracy, which in particular imply a resilience result in G(n, p) with respect to the containment of spanning bounded degree trees for p ≫[Formula Presented].
URI: http://hdl.handle.net/11420/7750
DOI: 10.15480/882.3047
ISSN: 2517-5599
Zeitschrift: Advances in combinatorics 
Institut: Mathematik E-10 
Dokumenttyp: Artikel/Aufsatz
Lizenz: CC BY 3.0 (Attribution) CC BY 3.0 (Attribution)
Enthalten in den Sammlungen:Publications with fulltext

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat
1612.00661v2.pdfVerlags-PDF567,51 kBAdobe PDFÖffnen/Anzeigen
Miniaturbild
Zur Langanzeige

Seitenansichten

136
Letzte Woche
1
Letzten Monat
1
checked on 01.10.2022

Download(s)

67
checked on 01.10.2022

SCOPUSTM   
Zitate

6
Letzte Woche
0
Letzten Monat
0
checked on 11.07.2022

Google ScholarTM

Prüfe

Feedback zu diesem Datensatz

Diesen Datensatz zitieren

Export

Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons Creative Commons