Combinatorics Seminar
Julia Ehrenmuller
Technical University of Munich
Spanning subgraphs of sparse random graphs after adversarial edge removal
Abstract: The local resilience of a graph G with respect to some monotone increasing graph property
P is the minimum number r such that by deleting at most r\deg(v) edges at each vertex
v of G one can obtain a graph not in P. A theorem proved by Böttcher, Schacht, and Taraz
asserts that the local resilience of the complete graph K_n with respect to containing all n-vertex k-colorable graphs of sublinear bandwidth and bounded maximum degree is 1/r - o(1).
In this talk we discuss an extension of this theorem to sparse random graphs. More precisely, we show that given \Delta and k, the random graph G(n,p) with p > > (\log n/n)^{1/\Delta} has a.a.s. local resilience 1/k- o(1) with respect to containing all n-vertex k-colorable graphs of sublinear bandwidth, maximum degree at most \Delta and with at least p^{-2} vertices that are not contained in any triangles.
This is joint work with Peter Allen, Julia Böttcher, and Anusch Taraz.
Monday June 23, 2014 at 11:00 AM in SEO 612