EPPA numbers of graphs

If G is a graph, A and B its induced subgraphs, and f : A → B an isomorphism, we say that f is a partial automorphism of G . In 1992, Hrushovski proved that graphs have the extension property for partial automorphisms ( EPPA , also called the Hrushovski property ), that is, for every finite graph G there is a finite graph H , an EPPA-witness for G , such that G is an induced subgraph of H and every partial automorphism of G extends to an automorphism of H . The EPPA number of a graph G , denoted by eppa ( G ) , is the smallest number of vertices of an EPPA-witness for G , and we put eppa ( n ) = max ⁡ { eppa ( G ) : | G | = n } . In this note we review the state of the area, prove several lower bounds (in particular, we show that eppa ( n ) ≥ 2 n n , thereby identifying the correct base of the exponential) and pose many open questions. We also briefly discuss EPPA numbers of hypergraphs, directed graphs, and K k -free graphs.