Graphs with small EPPA witnesses

A graph H is an EPPA-witness for a graph G if G is an induced subgraph of H and every isomorphism between induced subgraphs of G extends to an automorphism of H. We classify the finite graphs G which have an EPPA-witness of at most twice their order. This is a natural regime, and can be seen as a generalisation of Gardiner's well-known classification of finite ultrahomogeneous graphs. Along the way, we find a new family of graphs with small EPPA-witnesses.

This is an ongoing project with David Bradley-Williams, Peter Cameron, and Jan Hubička.