On the reconstructibility of functions from identification minors

Datum

22.05.2015

Zeit

13:15 - 14:15

Sprecher

Erkko Lehtonen

Zugehörigkeit

University of Lisbon

Sprache

en

Hauptthema

Mathematik

Andere Themen

Mathematik

Host

Jun.-Prof. Dr. Martin Schneider

Beschreibung

We consider functions of several arguments from $A$ to $B$, i.e., mappings $f \colon A^n \to B$ for some $n \geq 1$. For any $I = \{i, j\} \subseteq \{1, \dots, n\}$ with $i < j$, let $f_I \colon A^{n-1} \to B$ be the function given by the rule $f_I(a_1, \dots, a_{n-1}) = f(a_1, \dots, a_{j-1}, a_i, a_j, \dots, a_{n-1})$ for all $a_1, \dots, a_{n-1} \in A$. (Note that $a_i$ occurs twice on the right side of the above equality: both at the $i$-th and the $j$-th position.) Such a function $f_I$ is called an \emph{identification minor} of $f$. We present some results -- both positive and negative -- and open problems concerning the following reconstruction problem: Is a function $f \colon A^n \to B$ uniquely determined, up to permutation of arguments, by the collection of its identification minors? A related open problem is to determine which functions have a unique identification minor. The speaker conjectures that for sufficiently large arity, the only functions with a unique identification minor are those which are 2-set-transitive or determined by the order of first occurrence, up to permutation of arguments. This talk is partly based on joint work with Miguel Couceiro and Karsten Schölzel.

Letztmalig verändert: 09.04.2015, 17:36:08