When: Sunday, May 8, 10am
Where: Schreiber 309
Speaker: Mykhaylo Tyomkyn, Tel Aviv U.
Title: Approximate edge-decompositions and the Blow-up lemma
The Blow-up lemma of Komlos, Sarkozy and Szemeredi states, very roughly speaking, that a quasi-random graph G contains any bounded degree graph H as a subgraph.
In a recent paper we proved that in fact G can be almost decomposed into any collection of uniformly bounded degree graphs H_1,...,H_m. In particular, if n>n_0(\alpha,k), any n-vertex graphs H_1,...,H_m of degree at most k satisfying \sum e(H_i)<(1-\alpha)\binom{n}{2} can be packed into K_n edge-disjointy.
Joint work with Jaehoon Kim, Daniela Kuhn and Deryk Osthus.
