Abstract
If is a graph, , its induced subgraphs and is an isomorphism, we say that is a partial automorphism of . 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 , there is a finite graph , its EPPA-witness, such that is an induced subgraph of and every partial automorphism of extends to an automorphism of . The EPPA number of a graph , denoted by , is the smallest number ofvertices of an EPPA-witness for , and we put . In this talk we will review the state of the area and prove several new lower bounds. In particular, we will show that . We will also briefly discuss EPPA numbers ofhypergraphs.
This is joint work with Bradley-Williams, Cameron, and Hubička.