Please use this identifier to cite or link to this item:
Publisher DOI: 10.19086/aic.12849
arXiv ID: 1612.00661v2
Title: The bandwidth theorem in sparse graphs
Language: English
Authors: Allen, Peter 
Böttcher, Julia 
Ehrenmüller, Julia 
Taraz, Anusch 
Issue Date: 15-May-2020
Publisher: Alliance of Diamond Open Access Journals
Source: Advances in Combinatorics 1 (2020): 6, 1-60 (2020)
Abstract (english): 
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].
DOI: 10.15480/882.3047
ISSN: 2517-5599
Journal: Advances in combinatorics 
Institute: Mathematik E-10 
Document Type: Article
License: CC BY 3.0 (Attribution) CC BY 3.0 (Attribution)
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
1612.00661v2.pdfVerlags-PDF567,51 kBAdobe PDFView/Open
Show full item record

Page view(s)

Last Week
Last month
checked on Jul 6, 2022


checked on Jul 6, 2022


Last Week
Last month
checked on Jun 29, 2022

Google ScholarTM


Note about this record

Cite this record


This item is licensed under a Creative Commons License Creative Commons