• Calendar

March 25, Tuesday
12:00 – 14:00

Let $M$ be some finite graph or a finite metric space and assume that some of the automorphisms of $M$ are stored together with the structure of $M$. Let $N$ be some substructure of $N$. A partial automorphism $p$ of $N$ is implemented by an automorphism $f$ of $M$, if the automorphism $f$ extends $p$. For example, an automorphism of $M$ which moves point $a$ in $N$ to point $b$ in $N$ (but may take other points of $N$ out of $N$) implements the partial automorphims $amapsto b$. Consider the following problem: given a structure $N$ and a list $L_0$ of partial automorphisms of $N$, can you find a larger structure $M$ which cotains (a copy of) $N$ as a substructure so that every partial automorphism $p$ in $L_0$ is implemented in $M$. For example, can you find a graph $M$ extending the graph $N$ such that every vertex of $N$ can be moved to any other vertex of $N$ by an automorphisms of $M$ (here the answer is YES, by a theorem of Babai and Sos). The new results I will present assure that in some cases (including the case of the example above) one can find, for given $N$ and $L_0$, a structure $M$ with a list $L_1$ of (full) automorphisms of $M$, such that: (1) the size of $M$ and the size of $L$ are polynomial in the the size of $N$. (2) every partial automorphism in $L_0$ is implemented by some automorphisms from $L_1$. (3) Property (2) is indestructible by partitions: whenever $M$ is partitioned into two disjoint parts, at least one of the parts contains a copy of $N$ for which (2) holds. I will discuss some open problems at the end of the talk. The results are joint with Stefan Geschke.