Spring 2017

Packing Degenerate Graphs Using Pseudorandomness

Monday, March 6th, 2017 2:00 pm3:00 pm

Add to Calendar


Calvin Lab Auditorium

A family of graphs G_1,...,G_k is said to pack into a host graph H if there is a colouring of the edges of H with colours 0,...,k such that the edges of colour i form a copy of G_i for i=1,...,k. Packing problems have a long and interesting history in (hyper)graph theory.
In particular, there has recently been much progress on various long-standing conjectures on packing families of large graphs into the complete graph. In this talk I will outline this progress, and introduce a new result on (near-perfect) packings of families of graphs with constant degeneracy which generalises several previous results. The proof of this new result uses a very natural randomised greedy packing algorithm and relies on the fact that this algorithm preserves certain pseudorandomness properties. I will sketch the ideas.
Based on joint work with Peter Allen, Jan Hladk\'y, and Diana Piguet.