Verlagslink DOI: 10.1017/S0963548321000481
Titel: A spanning bandwidth theorem in random graphs
Sprache: Englisch
Autor/Autorin: Allen, Peter 
Böttcher, Julia 
Ehrenmüller, Julia 
Schnitzer, Jakob 
Taraz, Anusch 
Schlagwörter: random graphs; spanning subgraphs; sparse regularity
Erscheinungs­datum: 2021
Quellenangabe: Combinatorics Probability and Computing (in Press) : (2021)
Zusammenfassung (englisch): 
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.
URI: http://hdl.handle.net/11420/11418
ISSN: 0963-5483
Zeitschrift: Combinatorics, probability & computing 
Institut: Mathematik E-10 
Dokumenttyp: Artikel/Aufsatz
Enthalten in den Sammlungen:Publications without fulltext

Zur Langanzeige

Seitenansichten

34
Letzte Woche
1
Letzten Monat
checked on 04.10.2022

Google ScholarTM

Prüfe

Volltext ergänzen

Feedback zu diesem Datensatz

Diesen Datensatz zitieren

Export

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.