Extending partial automorphisms of graphs

Even though almost all finite graphs are rigid, it is possible to embed every finite graph into a significantly more symmetric graph with a rich automorphism group. Namely E. Hrushovski proved in the early 90’s that every finite graph G can be embedded into a finite graph H such that every partial automorphism of G extends to a automorphism of H. We are interested in how small a graph H can be - - and in the optimal cases of such H, make use of the agebraic properties the permutation group Aut(H) has in order to reason about the optimality of the graph H. This talk will include results of joint work with S. Brenner, P. J. Cameron, J. Hubička, and M. Konečný.