Publisher DOI: 10.1017/S0963548321000481
Title: A spanning bandwidth theorem in random graphs
Language: English
Authors: Allen, Peter 
Böttcher, Julia 
Ehrenmüller, Julia 
Schnitzer, Jakob 
Taraz, Anusch 
Keywords: random graphs; spanning subgraphs; sparse regularity
Issue Date: 2021
Source: Combinatorics Probability and Computing (in Press) : (2021)
Abstract (english): 
The bandwidth theorem of Böttcher, Schacht and Taraz states that any n-vertex graph G with minimum degree contains all n-vertex k-colourable graphs H with bounded maximum degree and bandwidth o(n). Recently, a subset of the authors proved a random graph analogue of this statement: for a.a.s. each spanning subgraph G of G(n,p) with minimum degree contains all n-vertex k-colourable graphs H with maximum degree , bandwidth o(n), and at least vertices not contained in any triangle. This restriction on vertices in triangles is necessary, but limiting. In this paper, we consider how it can be avoided. A special case of our main result is that, under the same conditions, if additionally all vertex neighbourhoods in G contain many copies of then we can drop the restriction on H that vertices should not be in triangles.
ISSN: 0963-5483
Journal: Combinatorics, probability & computing 
Institute: Mathematik E-10 
Document Type: Article
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

Last Week
Last month
checked on Jul 5, 2022

Google ScholarTM


Add Files to Item

Note about this record

Cite this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.