Multidimensional Necklaces: Counting, Generation and Ranking

5^th August 2020, 14:00 Online MT CSACTOO365Team
Duncan Adamson
University of Liverpool

Abstract

Crystals are highly periodic structures, defined by a unit cell which periodically tiles an infinite three dimensional space. Due to this tiling of space, there are many functionally identical unit cells, most obviously those that are the same up to translation. To explore the space of possible unit cells within a discrete unit space it is necessary to capture these symmetries.

In a single dimension these symmetries can be easily captured by representing the unit cell as a necklace -lexicographically minimal representation of a cyclic strings- therefore it seems reasonable to generalise this structure to multiple dimensions. This talk will focus on the generalisation of several key results on one dimensional necklaces to the multidimensional case. These are the classical problem of counting, as well algorithms for the efficient generation and ranking of all necklaces.