Seminář G²OAT: EPPA numbers of graphs

Abstrakt

If $G$ is a graph, $A$, $B$ its induced subgraphs and $f:A\to B$ is 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 $\mathrm{eppa}(G)$, is the smallest number ofvertices of an EPPA-witness for $G$, and we put $\mathrm{eppa}(n)=max\{\mathrm{eppa}(G)\mid \Vert G\Vert =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}\le \mathrm{eppa}(n)\le n\cdot 2^n$. We will also briefly discuss EPPA numbers ofhypergraphs.

This is joint work with Bradley-Williams, Cameron, and Hubička.

Další události