Please use this identifier to cite or link to this item: https://doi.org/10.15480/882.3047
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].
URI: http://hdl.handle.net/11420/7750
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
Thumbnail
Show full item record

Page view(s)

114
Last Week
1
Last month
1
checked on Jul 6, 2022

Download(s)

60
checked on Jul 6, 2022

SCOPUSTM   
Citations

6
Last Week
0
Last month
0
checked on Jun 29, 2022

Google ScholarTM

Check

Note about this record

Cite this record

Export

This item is licensed under a Creative Commons License Creative Commons