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: | ![]() |
Appears in Collections: | Publications with fulltext |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
1612.00661v2.pdf | Verlags-PDF | 567,51 kB | Adobe PDF | View/Open![]() |
Page view(s)
114
Last Week
1
1
Last month
1
1
checked on Jul 6, 2022
Download(s)
60
checked on Jul 6, 2022
SCOPUSTM
Citations
6
Last Week
0
0
Last month
0
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