Reconstruction of functions from minors

habilitation thesis, Technische Universität Dresden, Dresden, 2018
http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-237864

The central notion of this thesis is the minor relation on functions of several arguments. A function f: A^n?B is called a minor of another function g: A^m?B if f can be obtained from g by permutation of arguments, identification of arguments, and introduction of inessential arguments. We first provide some general background and context to this work by presenting a brief survey of basic facts and results concerning different aspects of the minor relation, placing some emphasis on the author’s contributions to the field. The notions of functions of several arguments and minors give immediately rise to the following reconstruction problem: Is a function f: A^n?B uniquely determined, up to permutation of arguments, by its identification minors, i.e., the minors obtained by identifying a pair of arguments? We review known results – both positive and negative – about the reconstructibility of functions from identification minors, and we outline the main ideas of the proofs, which often amount to formulating and solving reconstruction problems for other kinds of mathematical objects. We then turn our attention to functions determined by the order of first occurrence, and we are interested in the reconstructibility of such functions. One of the main results of this thesis states that the class of functions determined by the order of first occurrence is weakly reconstructible. Some reconstructible subclasses are identified; in particular, pseudo-Boolean functions determined by the order of first occurrence are reconstructible. As our main tool, we introduce the notion of minor of permutation. This is a quotient-like construction for permutations that parallels minors of functions and has some similarities to permutation patterns. We develop the theory of minors of permutations, focusing on Galois connections induced by the minor relation and on the interplay between permutation groups and minors of permutations. Our results will then find applications in the analysis of the reconstruction problem of functions determined by the order of first occurrence.