Department of
Applied
Mathematics

Partitioning the vertices of a torus into isomorphic subgraphs

Marthe Bonamy

Abstract

(joint work with Natasha Morrison (University of Cambridge) and Alex Scott (University of Oxford))

Let H be an induced subgraph of the m-dimensional k-torus C_m^k. We show that when k >= 3 is even and |V(H)| divides k^m, then for sufficiently large n the vertices of C_n^k can be partitioned into disjoint copies of H. We also show that when k is the product of two coprime odd integers, then there exists H where |V(H)| divides k m but for no n can the vertices of C_n^k be partitioned into disjoint copies of H. This disproves a conjecture of Gruslys. We also disprove a conjecture of Gruslys, Leader and Tan by exhibiting a subgraph H of the k-dimensional hypercube Q_k, such that there is no n for which the edges of Q_n can be partitioned into copies of H.