Combinatorics Seminar

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.

w3c valid   accessible website
redesigned by barak soreq