Bandwidth theorem for random graphs

DOI10.1016/J.JCTB.2011.03.002zbMATH Open1238.05248arXiv1005.1947OpenAlexW1995457760WikidataQ105583658 ScholiaQ105583658MaRDI QIDQ765187FDOQ765187

Authors: Hao Huang, Choongbum Lee, Benny Sudakov 

Publication date: 19 March 2012

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: A graph $G$ is said to have extit{bandwidth} at most $b$, if there exists a labeling of the vertices by $1,2,\mathrm{...},n$, so that $|i-j|leqb$ whenever $i,j$ is an edge of $G$. Recently, B"{o}ttcher, Schacht, and Taraz verified a conjecture of Bollob'{a}s and Koml'{o}s which says that for every positive $r,Delta,gamma$, there exists $$ such that if $H$ is an $n$-vertex $r$-chromatic graph with maximum degree at most $Delta$ which has bandwidth at most $$, then any graph $G$ on $n$ vertices with minimum degree at least $(1-1/r+gamma)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"{o}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 $H_0$ which one can find in a spanning subgraph of $G(n,p)$ with minimum degree $(1-1/r+gamma)np$.

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

Recommendations

• scientific article; zbMATH DE number 3979113
• A spanning bandwidth theorem in random graphs
• Lattice bandwidth of random graphs
• The bandwidth theorem in sparse graphs
• scientific article; zbMATH DE number 867648
• scientific article; zbMATH DE number 3859182
• scientific article; zbMATH DE number 3861212
• scientific article
• The bandwidth theorem for locally dense graphs

zbMATH Keywords

random graphsresilience\(H\)-packings

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Proof of the Seymour conjecture for large graphs
• Tiling Turán theorems
• \(H\)-factors in dense graphs
• The minimum degree threshold for perfect graph packings
• Embedding large subgraphs into dense graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the structure of linear graphs
• Proof of the Alon-Yuster conjecture
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Blow-up lemma
• Extremal results for random discrete structures
• Combinatorial theorems in sparse random sets
• Pseudo-random graphs
• On the resilience of long cycles in random graphs
• Almost spanning subgraphs of random graphs after adversarial edge removal
• Local resilience of almost spanning trees in random graphs
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• Spanning 3-colourable subgraphs of small bandwidth in dense graphs
• Proof of the bandwidth conjecture of Bollobás and Komlós
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Local resilience of graphs
• Resilient pancyclicity of random and pseudorandom graphs
• The sparse regularity lemma and its applications
• The Blow-up Lemma
• On two Hamilton cycle problems in random graphs
• Proof of a tiling conjecture of Komlós
• On the asymmetry of random regular graphs and random graphs
• On a tiling conjecture of Komlós for 3-chromatic graphs.

Cited In (21)

• The bandwidth theorem in sparse graphs
• Almost spanning subgraphs of random graphs after adversarial edge removal
• Dirac-type theorems in random hypergraphs
• Pancyclic subgraphs of random graphs
• A Dirac-type theorem for Berge cycles in random hypergraphs
• Transference for loose Hamilton cycles in random 3-uniform hypergraphs
• Bandwidth of chain graphs
• Embedding spanning bipartite graphs of small bandwidth
• An extension of the blow-up lemma to arrangeable graphs
• Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
• The bandwidth theorem for locally dense graphs
• Title not available (Why is that?)
• Local resilience of spanning subgraphs in sparse random graphs
• The threshold bias of the clique-factor game
• Triangle resilience of the square of a Hamilton cycle in random graphs
• A spanning bandwidth theorem in random graphs
• Spanning 3-colourable subgraphs of small bandwidth in dense graphs
• Corrádi and Hajnal's theorem for sparse random graphs
• On the KŁR conjecture in random graphs
• Dirac's theorem for random graphs
• A Dirac-type theorem for Hamilton Berge cycles in random hypergraphs

This page was built for publication: Bandwidth theorem for random graphs

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