The Bandwidth Theorem in sparse graphs

DOI10.19086/AIC.12849zbMATH Open1450.05048arXiv1612.00661OpenAlexW3025168281MaRDI QIDQ5126757

No author found.

Publication date: 20 October 2020

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

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

D e l t a

, 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

.

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

zbMATH Keywords

pseudorandom graphs

Mathematics Subject Classification ID

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

Related Items (12)

A spanning bandwidth theorem in random graphs ⋮ Dirac-type theorems in random hypergraphs ⋮ Triangle resilience of the square of a Hamilton cycle in random graphs ⋮ Local resilience for squares of almost spanning cycles in sparse random graphs ⋮ Covering cycles in sparse graphs ⋮ On sufficient conditions for spanning structures in dense graphs ⋮ A Dirac-type theorem for Berge cycles in random hypergraphs ⋮ Bandwidth on AT-free graphs ⋮ The bandwidth theorem for locally dense graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dirac’s theorem for random regular graphs

This page was built for publication: The Bandwidth Theorem in sparse graphs