Bandwidth theorem for random graphs

Hao Huang, Choongbum Lee, Benny Sudakov

Research output: Contribution to journalArticle

18 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)14-37
Number of pages24
JournalJournal of Combinatorial Theory. Series B
Volume102
Issue number1
DOIs
StatePublished - Jan 1 2012

Keywords

  • H-packings
  • Random graphs
  • Resilience

Fingerprint Dive into the research topics of 'Bandwidth theorem for random graphs'. Together they form a unique fingerprint.

Cite this