EPPA numbers of graphs

Matěj Konečný

TU Dresden

May 9, 2024, 12:20 in S6


If G is a graph, A, 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, 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 eppa(G), is the smallest number of vertices of an EPPA-witness for G, and we put eppa(n) = max{eppa(G) : |G| = n}.

I plan to introduce the area and many of its (nice if I may say so) open problems, and discuss some recent advances. This is joint work with Bradley-Williams, Cameron, and Hubička.