The bandwidth theorem in sparse graphs

DOI10.19086/AIC.12849MaRDI QIDQ5126757zbMATH OpenOpenAlexFDO

Authors

Publication date 20 October 2020

Published in Advances in Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1612.00661

zbMATH Keywords

pseudorandom graphs

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

Abstract: The bandwidth theorem [Mathematische Annalen, 343(1):175--205, 2009] 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)$. We provide sparse analogues of this statement in random graphs as well as pseudorandom graphs. More precisely, we show that for $$ asymptotically almost surely each spanning subgraph $G$ of $G(n,p)$ with minimum degree $$ contains all $n$-vertex $k$-colourable graphs $H$ with maximum degree $Delta$, bandwidth $o(n)$, and at least $C{p}^{-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 $$.

Recommendations

• A spanning bandwidth theorem in random graphs
• Bandwidth theorem for random graphs
• The bandwidth theorem for locally dense graphs
• Spanning embeddings of arrangeable graphs with sublinear bandwidth
• Local resilience of spanning subgraphs in sparse random graphs

Cited in

(17)

• Dirac-type theorems in random hypergraphs
• A Dirac-type theorem for Berge cycles in random hypergraphs
• Local resilience for squares of almost spanning cycles in sparse random graphs
• Triangle resilience of the square of a Hamilton cycle in random graphs
• Spanning embeddings of arrangeable graphs with sublinear bandwidth
• scientific article; zbMATH DE number 434870 (Why is no real title available?)
• Local resilience of spanning subgraphs in sparse random graphs
• Dirac's theorem for random regular graphs
• The bandwidth theorem for locally dense graphs
• scientific article; zbMATH DE number 279660 (Why is no real title available?)
• A spanning bandwidth theorem in random graphs
• Covering cycles in sparse graphs
• On sufficient conditions for spanning structures in dense graphs
• Bandwidth on AT-free graphs
• Dirac's theorem for graphs of bounded bandwidth
• Saturation numbers of bipartite graphs in random graphs
• Bandwidth theorem for random graphs

This page was built for publication: The bandwidth theorem in sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5126757)