Packing the discrete torus

Thursday, November 2, 2017 -
3:00pm to 4:30pm
Let H be an induced subgraph of the toroidal grid Z_k^m and suppose that| V(H)| divides some power of k. We show that if k is even then (forlarge m) the torus has a perfect vertex-packing with induced copies of H.This extends a result of Gruslys.  On the other hand, when k is odd and not a prime power, we disprove a conjecture of Gruslys: we show that there are choices of H such that there is no m for which Z_k^m has a perfect vertex-packing with copies of H.We also discuss edge-packings, and disprove a conjecture of Gruslys, Leader and Tan by exhibiting a graph H such that H embeds in a hypercube, but no hypercube has a perfect edge-packing with copies of H.Joint work with Marthe Bonamy and Natasha Morrison.   Next week: Greta Panova
Speaker: 
Alex Scott
Oxford University
Event Location: 
Fine Hall 224