Almost spanning subgraphs of random graphs after adversarial edge removal

DOI10.1016/j.endm.2009.11.055zbMath1268.05176arXiv1003.0890OpenAlexW2075689026WikidataQ105585014 ScholiaQ105585014MaRDI QIDQ2840559

Julia Böttcher, Anusch Taraz, Yoshiharu Kohayakawa

Publication date: 19 July 2013

Published in: Electronic Notes in Discrete Mathematics, Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

graph theoryrandom graphsextremal problemssparse regularityalmost spanning bipartite graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (16)

Dirac-type theorems in random hypergraphs ⋮ Long cycles in subgraphs of (pseudo)random directed graphs ⋮ Properly coloured copies and rainbow copies of large graphs with small maximum degree ⋮ Pancyclic subgraphs of random graphs ⋮ Local resilience of spanning subgraphs in sparse random graphs ⋮ Generating random graphs in biased Maker-Breaker games ⋮ Robust Hamiltonicity of random directed graphs ⋮ Triangle resilience of the square of a Hamilton cycle in random graphs ⋮ On resilience of connectivity in the evolution of random graphs ⋮ A Dirac-type theorem for Berge cycles in random hypergraphs ⋮ Independent Sets in Hypergraphs and Ramsey Properties of Graphs and the Integers ⋮ The bandwidth theorem for locally dense graphs ⋮ A Dirac-type theorem for Hamilton Berge cycles in random hypergraphs ⋮ Almost‐spanning universality in random graphs ⋮ Local resilience of almost spanning trees in random graphs ⋮ Bandwidth theorem for random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparse partition universal graphs for graphs of bounded degree
• Polychromatic Hamilton cycles
• Bandwidth theorem for random graphs
• Small subsets inherit sparse \(\varepsilon\)-regularity
• Embedding nearly-spanning bounded degree trees
• 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
• Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
• Corrádi and Hajnal's Theorem for Sparse Random Graphs
• Properly coloured copies and rainbow copies of large graphs with small maximum degree
• Local resilience of almost spanning trees in random graphs
• Local resilience of graphs
• Szemerédi’s Regularity Lemma for Sparse Graphs
• Regular pairs in sparse random graphs I
• Hypergraph Packing and Graph Embedding
• Sparse universal graphs for bounded‐degree graphs
• Some Theorems on Abstract Graphs

This page was built for publication: Almost spanning subgraphs of random graphs after adversarial edge removal