Robert Gray (CAUL/FCUL, Portugal)
18/11/2011 Sexta-feira, 18 de Novembro de 2011, 14 horas, Sala B3-01
Institute for Interdisciplinary Research
Structures with lots of symmetry
A relational structure is homogeneous if every isomorphism between finite substructures extends to an automorphism. Countable homogeneous structures arise as Fraïssé limits of amalgamation classes of finite structures. The subject has connections to model theory, to permutation group theory, and to combinatorics.
Following terminology of Fraïssé, a countable relational structure M is said to be set-homogeneous if, whenever two finite substructures U and V of M are isomorphic, there is an automorphism of M that sends U to V (setwise). Clearly every homogeneous structure is set-homogeneous, and Ronse (1978) showed that for finite graphs the converse is also true. He did this by classifying the finite set-homogeneous graphs and then observing that each of them also happens to be homogeneous. Following this, Enomoto (1981) reproved Ronse's result by giving a very elegant direct proof of the fact that every finite set-homogeneous graph is homogeneous.
In this talk I will present Enomoto's argument and go on to explain how it inspired some joint with Dugald Macpherson, Cheryl Praeger and Gordon Royle, which began with the question of whether a similar approach might be applied to other kinds of relational structure. Specifically I will talk about set-homogeneous directed graphs, outlining a classification in the finite case.