Bandwidth theorem for random graphs

DOI10.1016/j.jctb.2011.03.002zbMath1238.05248arXiv1005.1947OpenAlexW1995457760WikidataQ105583658 ScholiaQ105583658MaRDI QIDQ765187

Choongbum Lee, Hao Huang, Benjamin Sudakov

Publication date: 19 March 2012

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

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

zbMATH Keywords

random graphsresilience\(H\)-packings

Mathematics Subject Classification ID

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

Related Items (15)

Corrádi and Hajnal's Theorem for Sparse Random Graphs ⋮ Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs ⋮ Dirac-type theorems in random hypergraphs ⋮ Dirac's theorem for random graphs ⋮ Pancyclic subgraphs of random graphs ⋮ Local resilience of spanning subgraphs in sparse random graphs ⋮ Triangle resilience of the square of a Hamilton cycle in random graphs ⋮ The threshold bias of the clique-factor game ⋮ A Dirac-type theorem for Berge cycles in random hypergraphs ⋮ The bandwidth theorem for locally dense graphs ⋮ On the KŁR conjecture in random graphs ⋮ Embedding Spanning Bipartite Graphs of Small Bandwidth ⋮ A Dirac-type theorem for Hamilton Berge cycles in random hypergraphs ⋮ Almost spanning subgraphs of random graphs after adversarial edge removal ⋮ An Extension of the Blow-up Lemma to Arrangeable Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extremal results for random discrete structures
• Combinatorial theorems in sparse random sets
• Spanning 3-colourable subgraphs of small bandwidth in dense graphs
• On two Hamilton cycle problems in random graphs
• Proof of the bandwidth conjecture of Bollobás and Komlós
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• On the resilience of long cycles in random graphs
• Proof of the Seymour conjecture for large graphs
• Blow-up lemma
• On a tiling conjecture of Komlós for 3-chromatic graphs.
• Tiling Turán theorems
• \(H\)-factors in dense graphs
• The minimum degree threshold for perfect graph packings
• 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
• Resilient Pancyclicity of Random and Pseudorandom Graphs
• Local resilience of graphs
• Embedding large subgraphs into dense graphs
• The Blow-up Lemma
• Proof of a tiling conjecture of Komlós
• On the asymmetry of random regular graphs and random graphs
• On the structure of linear graphs
• Proof of the Alon-Yuster conjecture

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