TY - JOUR

T1 - Bandwidth theorem for random graphs

AU - Huang, Hao

AU - Lee, Choongbum

AU - Sudakov, Benny

PY - 2012/1/1

Y1 - 2012/1/1

N2 - A graph G is said to have bandwidth at most b, if there exists a labeling of the vertices by 1, 2,...,n, so that |i-j|≤b whenever {i, j} is an edge of G. Recently, Böttcher, Schacht, and Taraz verified a conjecture of Bollobás and Komlós which says that for every positive r, δ, γ, there exists β such that if H is an n-vertex r-chromatic graph with maximum degree at most δ which has bandwidth at most βn, then any graph G on n vertices with minimum degree at least (1-1/r+γ)n contains a copy of H for large enough n. In this paper, we extend this theorem to dense random graphs. For bipartite H, this answers an open question of Böttcher, Kohayakawa, and Taraz. It appears that for non-bipartite H the direct extension is not possible, and one needs in addition that some vertices of H have independent neighborhoods. We also obtain an asymptotically tight bound for the maximum number of vertex disjoint copies of a fixed r-chromatic graph H0 which one can find in a spanning subgraph of G(n, p) with minimum degree (1-1/r+γ)np.

AB - A graph G is said to have bandwidth at most b, if there exists a labeling of the vertices by 1, 2,...,n, so that |i-j|≤b whenever {i, j} is an edge of G. Recently, Böttcher, Schacht, and Taraz verified a conjecture of Bollobás and Komlós which says that for every positive r, δ, γ, there exists β such that if H is an n-vertex r-chromatic graph with maximum degree at most δ which has bandwidth at most βn, then any graph G on n vertices with minimum degree at least (1-1/r+γ)n contains a copy of H for large enough n. In this paper, we extend this theorem to dense random graphs. For bipartite H, this answers an open question of Böttcher, Kohayakawa, and Taraz. It appears that for non-bipartite H the direct extension is not possible, and one needs in addition that some vertices of H have independent neighborhoods. We also obtain an asymptotically tight bound for the maximum number of vertex disjoint copies of a fixed r-chromatic graph H0 which one can find in a spanning subgraph of G(n, p) with minimum degree (1-1/r+γ)np.

KW - H-packings

KW - Random graphs

KW - Resilience

UR - http://www.scopus.com/inward/record.url?scp=81455131793&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=81455131793&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2011.03.002

DO - 10.1016/j.jctb.2011.03.002

M3 - Article

AN - SCOPUS:81455131793

VL - 102

SP - 14

EP - 37

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

IS - 1

ER -