Random Necklaces, Graphs and Molecules: The Challenge of Unlabelled Sampling

Leslie Goldberg


Informally, an "unlabelled combinatorial structure" is an object such as an unlabelled graph (in which the vertices are indistinguishable) or a structural isomer in chemistry (which shows how the various atoms of a molecule should be connected, without further distinguishing between different atoms of the same type). This talk is concerned with the question ``How do you sample uniformly at random from a set of unlabelled combinatorial structures?'' The talk will survey known algorithmic methods which apply to such problems, and will point out limitations of the known methods. Some of the many open problems in this area will be discussed.