Please use this identifier to cite or link to this item: https://doi.org/10.15480/882.3047
DC FieldValueLanguage
dc.contributor.authorAllen, Peter-
dc.contributor.authorBöttcher, Julia-
dc.contributor.authorEhrenmüller, Julia-
dc.contributor.authorTaraz, Anusch-
dc.date.accessioned2020-11-09T09:42:45Z-
dc.date.available2020-11-09T09:42:45Z-
dc.date.issued2020-05-15-
dc.identifier.citationAdvances in Combinatorics 1 (2020): 6, 1-60 (2020)de_DE
dc.identifier.issn2517-5599de_DE
dc.identifier.urihttp://hdl.handle.net/11420/7750-
dc.description.abstractThe 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.isoende_DE
dc.publisherAlliance of Diamond Open Access Journalsde_DE
dc.relation.ispartofAdvances in combinatoricsde_DE
dc.rights.urihttps://creativecommons.org/licenses/by/3.0/de_DE
dc.subject.ddc510: Mathematikde_DE
dc.titleThe bandwidth theorem in sparse graphsde_DE
dc.typeArticlede_DE
dc.identifier.doi10.15480/882.3047-
dc.type.diniarticle-
dcterms.DCMITypeText-
tuhh.identifier.urnurn:nbn:de:gbv:830-882.0111642-
tuhh.oai.showtruede_DE
tuhh.abstract.englishThe 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.doi10.19086/aic.12849-
tuhh.publication.instituteMathematik E-10de_DE
tuhh.identifier.doi10.15480/882.3047-
tuhh.type.opus(wissenschaftlicher) Artikel-
dc.type.driverarticle-
dc.type.casraiJournal Article-
tuhh.container.issue1de_DE
tuhh.container.volume2020de_DE
tuhh.container.startpage1de_DE
tuhh.container.endpage60de_DE
dc.rights.nationallicensefalsede_DE
dc.identifier.arxiv1612.00661v2de_DE
dc.identifier.scopus2-s2.0-85090527679de_DE
tuhh.container.articlenumber6de_DE
local.status.inpressfalsede_DE
local.type.versionpublishedVersionde_DE
item.grantfulltextopen-
item.openairetypeArticle-
item.fulltextWith Fulltext-
item.languageiso639-1en-
item.creatorOrcidAllen, Peter-
item.creatorOrcidBöttcher, Julia-
item.creatorOrcidEhrenmüller, Julia-
item.creatorOrcidTaraz, Anusch-
item.cerifentitytypePublications-
item.creatorGNDAllen, Peter-
item.creatorGNDBöttcher, Julia-
item.creatorGNDEhrenmüller, Julia-
item.creatorGNDTaraz, Anusch-
item.openairecristypehttp://purl.org/coar/resource_type/c_6501-
crisitem.author.deptMathematik E-10-
crisitem.author.deptMathematik E-10-
crisitem.author.orcid0000-0002-4104-3635-
crisitem.author.parentorgStudiendekanat Elektrotechnik, Informatik und Mathematik-
crisitem.author.parentorgStudiendekanat Elektrotechnik, Informatik und Mathematik-
Appears in Collections:Publications with fulltext
Files in This Item:
File Description SizeFormat
1612.00661v2.pdfVerlags-PDF567,51 kBAdobe PDFThumbnail
View/Open
Show simple item record

Page view(s)

58
Last Week
0
Last month
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 Creative Commons