Please use this identifier to cite or link to this item:
https://doi.org/10.15480/882.3047
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Allen, Peter | - |
dc.contributor.author | Böttcher, Julia | - |
dc.contributor.author | Ehrenmüller, Julia | - |
dc.contributor.author | Taraz, Anusch | - |
dc.date.accessioned | 2020-11-09T09:42:45Z | - |
dc.date.available | 2020-11-09T09:42:45Z | - |
dc.date.issued | 2020-05-15 | - |
dc.identifier.citation | Advances in Combinatorics 1 (2020): 6, 1-60 (2020) | de_DE |
dc.identifier.issn | 2517-5599 | de_DE |
dc.identifier.uri | http://hdl.handle.net/11420/7750 | - |
dc.description.abstract | 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]. | en |
dc.language.iso | en | de_DE |
dc.publisher | Alliance of Diamond Open Access Journals | de_DE |
dc.relation.ispartof | Advances in combinatorics | de_DE |
dc.rights.uri | https://creativecommons.org/licenses/by/3.0/ | de_DE |
dc.subject.ddc | 510: Mathematik | de_DE |
dc.title | The bandwidth theorem in sparse graphs | de_DE |
dc.type | Article | de_DE |
dc.identifier.doi | 10.15480/882.3047 | - |
dc.type.dini | article | - |
dcterms.DCMIType | Text | - |
tuhh.identifier.urn | urn:nbn:de:gbv:830-882.0111642 | - |
tuhh.oai.show | true | de_DE |
tuhh.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]. | de_DE |
tuhh.publisher.doi | 10.19086/aic.12849 | - |
tuhh.publication.institute | Mathematik E-10 | de_DE |
tuhh.identifier.doi | 10.15480/882.3047 | - |
tuhh.type.opus | (wissenschaftlicher) Artikel | - |
dc.type.driver | article | - |
dc.type.casrai | Journal Article | - |
tuhh.container.issue | 1 | de_DE |
tuhh.container.volume | 2020 | de_DE |
tuhh.container.startpage | 1 | de_DE |
tuhh.container.endpage | 60 | de_DE |
dc.rights.nationallicense | false | de_DE |
dc.identifier.arxiv | 1612.00661v2 | de_DE |
dc.identifier.scopus | 2-s2.0-85090527679 | de_DE |
tuhh.container.articlenumber | 6 | de_DE |
local.status.inpress | false | de_DE |
local.type.version | publishedVersion | de_DE |
item.grantfulltext | open | - |
item.openairetype | Article | - |
item.fulltext | With Fulltext | - |
item.languageiso639-1 | en | - |
item.creatorOrcid | Allen, Peter | - |
item.creatorOrcid | Böttcher, Julia | - |
item.creatorOrcid | Ehrenmüller, Julia | - |
item.creatorOrcid | Taraz, Anusch | - |
item.cerifentitytype | Publications | - |
item.creatorGND | Allen, Peter | - |
item.creatorGND | Böttcher, Julia | - |
item.creatorGND | Ehrenmüller, Julia | - |
item.creatorGND | Taraz, Anusch | - |
item.openairecristype | http://purl.org/coar/resource_type/c_6501 | - |
crisitem.author.dept | Mathematik E-10 | - |
crisitem.author.dept | Mathematik E-10 | - |
crisitem.author.orcid | 0000-0002-4104-3635 | - |
crisitem.author.parentorg | Studiendekanat Elektrotechnik, Informatik und Mathematik | - |
crisitem.author.parentorg | Studiendekanat Elektrotechnik, Informatik und Mathematik | - |
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)
58
Last Week
0
0
Last month
7
7
checked on Jan 17, 2021
Download(s)
18
checked on Jan 17, 2021
Google ScholarTM
Check
Note about this record
Export
This item is licensed under a Creative Commons License