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)
Journal or Series Name: Advances in combinatorics 
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
Institute: Mathematik E-10 
Type: (wissenschaftlicher) Artikel
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 PDFThumbnail
View/Open
Show full item record

Page view(s)

52
Last Week
5
Last month
checked on Dec 2, 2020

Download(s)

16
checked on Dec 2, 2020

Google ScholarTM

Check

Note about this record

Export

This item is licensed under a Creative Commons License Creative Commons