EPPA numbers of graphs

If \(G\) is a graph, \(A\), \(B\) its induced subgraphs and \(f\colon A \to 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\), its EPPA-witness, 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 \(\operatorname{eppa}(G)\), is the smallest number of vertices of an EPPA-witness for \(G\), and we put \(\operatorname{eppa}(n) = \max\{\operatorname{eppa}(G) \mid \|G\| = n\}\). In this talk, we will review the state of the area and prove several new lower bounds. In particular, we will show that \(2^n/\sqrt{n} ≤ \operatorname{eppa}(n) ≤ n\cdot2^n\). We will also briefly discuss EPPA numbers of hypergraphs. This is joint work with Bradley-Williams, Cameron, and Hubička.