Research

My research interests lie at the confluence of (universal) algebra, combinatorics, and discrete mathematics. A recurrent theme in much of my work is the minor relation of functions and minor-closed classes, also known as minions, as well as clones and clonoids. Broad research themes that I have worked on include the following:

• various aspects of minors, minions, clonoids, clones,
• Galois connections,
• reflections, minions, and varieties of multisorted algebras,
• \(n\)-ary semigroups,
• permutation patterns and their interplay with permutation groups,
• graph algebras and graph varieties,
• associative spectra of groupoids,
• reconstruction problems.

In the following, I will expand a bit on the main themes of my recent and current research, providing also some background to the topic.

Minors, minions, clonoids, clones

Given a function \(f \colon A^n \to B\) of several arguments, the functions that can be obtained from \(f\) by manipulation of arguments — permutation of arguments, introduction or deletion of fictitious arguments, and identification of arguments — are called minors of \(f\). Classes of functions closed under formation of minors are called minor-closed classes or minions. Minions may have additional closure properties. In particular, a class of operations on a set \(A\) is called a clone on \(A\) if it contains all projections on \(A\) and is closed under functional composition.

In universal algebra, clones and minions arise naturally as sets of all term operations of algebras and set of all term operations of algebras that are induced by terms of height 1, respectively. Clones and minions have recently played an important role in the analysis of the complexity of constraint satisfaction problems (CSP), minions especially in a new variant known as promise CSP (see [BarBulKroOpr-2019]).

Let us formulate this in precise terms. Let \(A\) and \(B\) be sets. A mapping of the form \(f \colon A^n \to B\) for some \(n \in \mathbb{N}\) is called a function of several arguments from \(A\) to \(B\). The number \(n\) is called the arity of \(f\). If \(A = B\) then we speak of operations on \(A\). Operations on \(\{0, 1\}\) are called Boolean functions. We denote by \(\mathcal{F}_{AB}\) the set of all functions of several arguments from \(A\) to \(B\) and by \(\mathcal{O}_A\) the set of all operations on \(A\). For any \(F \subseteq \mathcal{F}_{AB}\) and \(n \in \mathbb{N}\), we denote by \(F^{(n)}\) the set of all \(n\)-ary members of \(F\).

A function \(f \colon A^n \to B\) is called a minor of a function \(g \colon A^m \to B\), denoted \(f \leq g\), if there exists a map \(\sigma \colon \{1, \dots, m\} \to \{1, \dots, n\}\) such that \(f(a_1, \dots, a_n) = g(a_{\sigma(1)}, \dots, a_{\sigma(m)})\) for all \(a_1, \dots, a_n \in A\). The functions \(f\) and \(g\) are equivalent, denoted \(f \equiv g\), if \(f \leq g\) and \(g \leq f\). The minor relation \(\leq\) is a quasi-order (a reflexive and transitive relation) on \(\mathcal{F}_{AB}\), and, as usual, it induces a partial order on the quotient \(\mathcal{F}_{AB} / \mathord{\equiv}\). The downsets of this order are called minor-closed classes or minions.

The composition of \(f \in \mathcal{F}_{BC}^{(n)}\) with \(g_1, \dots, g_n \in \mathcal{F}_{AB}^{(m)}\) is the function \(f(g_1, \dots, g_n) \in \mathcal{F}_{AC}^{(m)}\) given by the rule \(f(g_1, \dots, g_n)(\mathbf{a}) := f(g_1(\mathbf{a}), \dots, g_n(\mathbf{a}))\) for all \(\mathbf{a} \in A^m\). For \(1 \leq i \leq n\), the \(i\)-th \(n\)-ary projection on \(A\) is the operation \(\mathrm{pr}_i^{(n)} \colon A^n \to A\), \((a_1, \dots, a_n) \mapsto a_i\) for all \((a_1, \dots, a_n) \in A^n\). We denote by \(\mathsf{J}_A\) the class of all projections on \(A\). A class \(C \subseteq \mathcal{O}_A\) is called a clone on \(A\) if \(\mathsf{J}_A \subseteq C\) and \(C\) is closed under composition.

An operation \(f\) on a set \(A\) preserves a relation \(R\) on \(A\) if the componentwise application of \(f\) to tuples from \(R\) results in a tuple in \(R\). In this case we say that \(f\) is a polymorphism of \(R\) and that \(R\) is an invariant of \(f\). The preservation relation between operations and relations induces a Galois connection, known as \(\operatorname{Pol}\)–\(\operatorname{Inv}\), and its closed sets of operations are the (locally closed) clones; the closed sets of relations are called relational clones (see [BodKalKotRom-1969, Gei-1968]). An analogous Galois theory for minions was developed by Pippenger [Pip-2002]; instead of relations we now need pairs of relations.

On the structure of the minor poset

The minor poset \((\mathcal{F}_{AB}/{\equiv}, {\leq})\) has a rich structure that is not fully understood, and it has given rise to several studies. For instance, \(\mathcal{F}_{AB}\) is partitioned into blocks such that there are no comparabilities between distinct blocks; each block comprises the functions having the same diagonal (see [CouPou-2008]). Its principal downsets are finite, and it is countable if \(A\) and \(B\) are finite. Moreover, if \(A\) and \(B\) are finite and \(\lvert B \rvert \geq \min(3, \lvert A \rvert)\), then the poset is past-finite-universal (this was shown for Boolean functions in [CouPou-2008] and in generality in [LehSze-2012]).

Let \(f \colon A^n \to B\), and let \(i \in \{1, \dots, n\}\). The \(i\)-th argument of \(f\) is essential (or \(f\) depends on the \(i\)-th argument) if there exist elements \(a_1, \dots, a_n, a'_i \in A\) such that \[f(a_1, \dots, a_{i-1}, a_i, a_{i+1}, \dots, a_n) \neq f(a_1, \dots, a_{i-1}, a'_i, a_{i+1}, \dots, a_n).\] Arguments that are not essential are fictitious. The number of essential arguments of \(f\) is called the essential arity of \(f\) and is denoted by \(\operatorname{ess} f\).

If \(\lvert A \rvert = 2\), then the lower covers of each function \(f \in \mathcal{F}_{AB}\) have the same essential arity (see [BouCouPou-2010]). This is no longer true when \(\lvert A \rvert \geq 3\), as witnessed by the constructions provided in [CouLehWal-2013], [CouLeh-2018]. In [CouLeh-2018] we show that two functions \(f, g \in \mathcal{F}_{AB}\), say \(n\)-ary and \(m\)-ary, have an upper bound with respect to the minor order if and only if they have the same diagonal; moreover, if an upper bound exists, then there is one of essential arity \(n + m - 1\). We also describe the possible essential arities of the upper covers of a function \(f \in \mathcal{F}_{AB}\).

As mentioned above, for any \(f \in \mathcal{F}_{AB}\) the principal downset \({\downarrow} f\) of the minor poset \((\mathcal{F}_{AB} / {\equiv}, {\leq})\) is finite. Moreover, it is a bounded poset, the greatest and the least elements of which are \(f\) and the diagonal function of \(f\), respectively. Let us call \({\downarrow} f\) the poset of minors of \(f\). The question which finite bounded posets are isomorphic to the poset of minors of some function \(f \in \mathcal{F}_{AB}\), for some sets \(A\) and \(B\), was investigated in [LehWal-2019]. We presented an abstract characterization of posets of minors as quotients of partition lattices corresponding to so-called admissible colourings, as well as constructions for building posets of minors from known ones. Unfortunately, the condition is quite technical and not very easy to verify for a concrete poset. It remains an open problem to find a finite bounded poset that is not the poset of minors of any function, if there exists such a poset at all.

Arity gap

The arity gap of a function \(f \colon A^n \to B\) is the minimum decrease in the number of essential arguments when proper minors are formed; formally, \(\operatorname{gap} f := \min_{g < f} \operatorname{ess} g\). This notion was first studied by Salomaa [Sal-1963], who showed that the arity gap of any Boolean function is at most 2. Willard [Wil-1996] extended this result to functions defined and valued on finite sets \(A\) and \(B\): it holds that \(\operatorname{gap} f \leq 2\) for any function \(f \colon A^n \to B\) with \(n > \lvert A \rvert\). The picture was completed in [CouLeh-2009] and [CouLehWal-2012] in which all functions of several arguments were classified according to their arity gap as follows.

Theorem. Let \(A\) and \(B\) be arbitrary, possibly infinite sets with at least two elements. Suppose that \(f \colon A^n \to B\) depends on all of its arguments and \(n \geq 2\).

1. For \(3 \leq p \leq n\), \(\operatorname{gap} f = p\) if and only if \(\operatorname{qa} f = n - p\).
2. For \(n \neq 3\), \(\operatorname{gap} f = 2\) if and only if \(\operatorname{qa} f = n - 2\) or \(\operatorname{qa} f = n\) and \(f|_{A^n_{=}}\) is determined by \(\operatorname{oddsupp}\).
3. For \(n = 3\), \(\operatorname{gap} f = 2\) if and only if there is a nonconstant unary function \(h \colon A \to B\) and \(i_1, i_2, i_3 \in \{0, 1\}\) such that \[ f(x_1, x_0, x_0) = h(x_{i_1}), \quad f(x_0, x_1, x_0) = h(x_{i_2}), \quad f(x_0, x_0, x_1) = h(x_{i_3}). \]
4. Otherwise \(\operatorname{gap} f = 1\).

In the above, \(A^n_{=} := \{(a_1, \dots, a_n) \in A^n \mid \exists i, j \colon i \neq j, a_i = a_j\}\). The quasi-arity of \(f \colon A^n \to B\) is defined as \(\operatorname{qa} f := \min_g \operatorname{ess} g\), where \(g\) ranges over the set of all functions \(g \colon A^n \to B\) such that \(f|_{A^n_{=}} = g|_{A^n_{=}}\). A partial function \(f \colon S \to B\), \(S \subseteq A^n\), is determined by \(\operatorname{oddsupp}\) if there exists a map \(f^* \colon \mathcal{P}(A) \to B\) such that \(f = f^* \circ \operatorname{oddsupp}|_S\), where the function \(\operatorname{oddsupp} \colon \bigcup_{n \geq 1} A^n \to \mathcal{P}(A)\) is defined by \[ \operatorname{oddsupp}(a_1, \dots, a_n) = \{a_i : \lvert \{j \in \{1, \dots, n\} : a_j = a_i\} \rvert \text{ is odd}\}. \]

Function class composition and \((C_1,C_2)\)-clonoids

The notion of functional composition can be extended to function classes as follows: for classes \(I \subseteq \mathcal{F}_{BC}\) and \(J \subseteq \mathcal{F}_{AB}\), the composition of \(I\) with \(J\) is the class \(IJ := \{ f(g_1, \dots, g_n) \mid n, m \in \mathbb{N}, f \in I^{(n)}, g_1, \dots, g_n \in J^{(m)} \}\). With this notion at hand, we can express many concepts in a simple way. For example, \(f \in \mathcal{F}_{AB}\) is a minor of \(g \in \mathcal{F}_{AB}\) if and only if \(f \in \{g\} \mathsf{J}_A\), where \(\mathsf{J}_A\) denotes the class of all projections on \(A\). For another example, a class \(C \subseteq \mathcal{O}_A\) is a clone on \(A\) if and only if \(\mathsf{J}_A \subseteq C\) and \(C C \subseteq C\).

Let \(F \subseteq \mathcal{F}_{AB}\), and let \(C_1\) and \(C_2\) be clones on \(A\) and \(B\), respectively. We say that \(F\) is stable under right composition with \(C_1\) if \(F C_1 \subseteq F\), and that \(F\) is stable under left composition with \(C_2\) if \(C_2 F \subseteq F\). We say that \(F\) is \((C_1,C_2)\)-stable or that \(F\) is a \((C_1,C_2)\)-clonoid if \(F\) is stable under right composition with \(C_1\) and stable under left composition with \(C_2\). Some noteworthy particular cases of this notion include the following. If both \(C_1\) and \(C_2\) are clones of projections, i.e., \(C_1 = \mathsf{J}_A\), \(C_2 = \mathsf{J}_B\), then we get exactly minions. If \(C_1\) is the clone of projections on \(A\) and \(C_2\) is arbitrary, then we get so-called clonoids, as defined by Aichinger and Mayr [AicMay-2016]. If \(C_1\) is arbitrary and \(C_2 = \mathsf{J}_B\), then we get so-called \(C_1\)-minor-closed classes, which were studied in a series of papers [Leh-2006, LehSze-2009, LehSze-2010, LehNeš-2010, LehSze-2012].

The set of all \((C_1,C_2)\)-clonoids constitutes a closure system which will be denoted by \(\mathcal{L}_{(C_1,C_2)}\). Couceiro and Foldes [CouFol-2009] characterized \((C_1,C_2)\)-clonoids in terms of a Galois connection between functions and relation pairs, where we require that the two relations are invariants of the clones \(C_1\) and \(C_2\). Although this is a great theoretical tool, it does not quite reveal the structure of \(\mathcal{L}_{(C_1,C_2)}\) nor does it provide an explicit description of the \((C_1,C_2)\)-clonoids. This inevitably leads us to the problem of describing the \((C_1,C_2)\)-clonoids for fixed clones \(C_1\) and \(C_2\).

A convenient starting point for a systematic study of lattices of \((C_1,C_2)\)-clonoids is suggested by the following result due to Sparks [Spa-2019]: if \(A\) is a finite set with \(\lvert A \rvert \geq 2\), \(B = \{0,1\}\), and \(C\) is a clone on \(B\), then \(\mathcal{L}_{(\mathsf{J}_A,C)}\) is finite if and only if \(C\) contains a near-unanimity operation; \(\mathcal{L}_{(\mathsf{J}_A,C)}\) is countably infinite if and only if \(C\) contains a Malʹcev operation but no majority operation; and \(\mathcal{L}_{(\mathsf{J}_A,C)}\) has the cardinality of the continuum if and only if \(C\) contains neither a near-unanimity operation nor a Malʹcev operation.

Guided by Sparks’s theorem, we looked into \((C_1,C_2)\)-clonoids of Boolean functions for those cases in which \(\mathcal{L}_{(C_1,C_2)}\) is at most countably infinite – there is a good chance of finding an explicit description of the \((C_1,C_2)\)-clonoids in those cases. In [CouLeh-2024, Leh-2024], we described all \((\mathsf{J}_{\{0,1\}},\mathsf{L}_{01})\)-clonoids and all \((\mathsf{J}_{\{0,1\}},\mathsf{SM})\)-clonoids of Boolean functions. Here \(\mathsf{L}_{01}\) and \(\mathsf{SM}\) denote the clone of idempotent linear functions and the clone of self-dual monotone functions, respectively. As an easy consequence, making use of the monotonicity of function class composition, all \((C_1,C_2)\)-clonoids of Boolean functions were also described for every pair of clones \(C_1\) and \(C_2\), where \(C_1\) is arbitrary and \(C_2\) contains either \(\mathsf{L}_{01}\) or \(\mathsf{SM}\). In a series of sequel papers [Leh-2025, Leh-pre-2024a, Leh-pre-2024b], the cardinality and structure of \((C_1,C_2)\)-clonoid lattices for further pairs \((C_1,C_2)\) of clones were detemined.

Reflections, minions, and varieties of multisorted algebras

Reflections of algebras were introduced by Barto, Opršal, and Pinsker [BarOprPin-2018] for the purpose of investigating the complexity of CSPs. Given an algebra \(\mathbf{A} = (A,F^\mathbf{A})\) of type \(\tau\), a set \(B\), and maps \(h \colon B \to A\) and \(h' \colon A \to B\), the algebra \(\mathbf{B} = (B,F^\mathbf{B})\) of type \(\tau\), where the fundamental operations are given by the rule \(f^\mathbf{B}(x_1, \dots, x_n) := h'(f^\mathbf{A}(h(x_1), \dots, h(x_n))\), is called a reflection of \(\mathbf{A}\). From the algebraic point of view, reflections generalize at the same time both subalgebras and homomorphic images. However, they do not preserve arbitrary identities, but only minor identities, i.e., identities of height 1.

Multisorted algebras generalize the notion of an algebra so as to include functions that take arguments and values from possibly different sets. Much of the general theory of usual one-sorted algebras generalize to multisorted algebras. In [LehPösWal-2018a], we generalized the notion of reflection to multisorted algebras, and we characterized reflection-closed varieties of multisorted algebras as those definable by minor identities. (For usual one-sorted algebras, this was proved by Barto, Opršal, and Pinsker [BarOprPin-2018].) We also characterized the minor-equational theories of multisorted algebras by explicit closure conditions. (For usual one-sorted algebras, this was done by Čupona and Markovski [ČupMar-1997].)

In [LehPösWal-2018b], we proved some facts about the structure of the minor poset of multisorted operations. We also generalized Pippenger’s Galois theory of minions and relation pairs to multisorted operations. This is quite straightforward but some technicalities arise due to the fact that some components of the multisorted universe may be empty. Nullary relations are nevertheless needed, in contrast to the one-sorted case. Reflections of multisorted minions are again minions, and we also described how the invariant reflection pairs are affected by reflections.

With the help of the above results, we generalized one of the main results of [BarOprPin-2018] also to the multisorted setting, namely the characterization of the \(\mathsf{ERP}\)-closure of a set of operations, i.e., the closure under extensions, reflections, and direct powers. In particular, we described the \(\mathsf{ERP}\)-closure from the relational point of view. To this end, we introduced reflections (and coreflections) also for relation pairs, and these turned out a suitable tool for such a description.

Permutation patterns and permutation groups

The theory of permutation patterns and pattern avoidance has been an active field of research over the past decades. The basic notion of this theory is the pattern involvement relation. Let \(\pi = \pi_1 \pi_2 \dots \pi_n \in S_n\) and \(\tau = \tau_1 \tau_2 \dots \tau_k \in S_k\) with \(n \geq k\). We say that \(\pi\) involves \(\tau\) if there exists a subsequence \(\pi_{i_1} \pi_{i_2} \dots \pi_{i_k}\) with \(1 \leq i_1 < i_2 < \dots < i_k \leq n\) that is order-isomorphic to \(\tau_1 \tau_2 \dots \tau_k\). In this case, the permutation \(\tau\) is called a pattern of \(\pi\), and we write \(\tau \leq \pi\). If \(\pi\) does not involve \(\tau\), we say that \(\pi\) avoids \(\tau\). For a set \(T\) of finite permutations, we denote by \(\operatorname{Av}(T)\) the set of permutations that avoid every permutation \(\tau \in T\). We also denote \(\operatorname{Av}_n(T) := \operatorname{Av}(T) \cap S_n\).

The pattern involvement relation is a partial order on the set of all finite permutations. The downsets of this order are called permutation classes, and they can be described as sets of the form \(\operatorname{Av}(T)\) for some set \(T\) of forbidden patterns.

Permutation groups are a classical topic in algebra and require no further introduction here. At first sight it might seem that permutation patterns do not have much to do with permutation groups. In fact, there is a perhaps surprising connection. It was observed in [LehPös-2017] that if \(G\) is a subgroup of the symmetric group \(S_k\), then for each positive integer \(n\), the set \(\operatorname{Av}_n(S_k \setminus G)\) is a subgroup of \(S_n\). We described the permutation groups that arise in this way as sets of permutations avoiding some patterns as automorphism groups of relations of a special prescribed form.

Atkinson and Beals [AtkBea-2001] studied group classes, i.e., permutation classes \(C\) in which every level \(C \cap S_n\) is a permutation group. They described the eventual behaviour of the level sequences of group classes. Furthermore, they described those group classes in which every level is a transitive group. In [Leh-2020], we refined Atkinson and Beals’s results on group classes, on the one hand, focusing on the local behaviour of the level sequence of \(\operatorname{Av}(S_\ell \setminus G)\) for an arbitrary group \(G \leq S_\ell\), and, on the other hand, determining how fast the level sequence converges to the eventual steady sequence predicted by Atkinson and Beals.

The main technical tool that we employ is the monotone Galois connection \((\operatorname{Comp}^{(n)}, \operatorname{Pat}^{(\ell)})\) between the symmetric groups \(S_\ell\) and \(S_n\) induced by the pattern avoidance relation — this was introduced in [LehPös-2017]. In terms of these operators, the level sequence \(\operatorname{Av}(S_\ell \setminus G)\) for \(G \leq S_\ell\) is given by the closed sets \(\operatorname{Comp}^{(n)}\) for \(n \geq \ell\). Making use of a transitive property of the operators \(\operatorname{Comp}^{(n)}\) and \(\operatorname{Pat}^{(\ell)}\), it is sufficient to determine only \(\operatorname{Comp}^{(n+1)}\) for any \(G \leq S_n\). Accordingly, the main results of [Leh-2020] are of the following form: If \(G \leq S_n\) is a permutation group belonging to a certain class of permutation groups, then \(\operatorname{Comp}^{(n+1)} G\) equals a certain subgroup of \(S_{n+1}\). Repeated applications of such theorems then yield the level sequence of \(\operatorname{Av}(S_\ell \setminus G)\), and the rate of convergence to a steady sequence can be easily determined.

Graph algebras

Graph algebras were introduced by Shallon [Sha-1979]. To each directed graph \(G = (V,E)\), we associate an algebra \(A(G)\) of type \((2,0)\), called a graph algebra, whose universe is the set \(V \cup \{\infty\}\), where \(\infty\) is a new element not in \(V\), considered as a nullary operation, and where the binary operation \(\circ\) is defined as \[ x \circ y := \begin{cases} x, & \text{if $(x,y) \in E$,} \\ \infty, & \text{otherwise.} \end{cases} \] Encoding graphs as algebras in this way, we can view any algebraic property of the graph algebra \(A(G)\) as a property of the graph \(G\) itself.

Although the class of graph algebras does not constitute a variety (as it is not closed under direct products), it makes perfect sense to consider the satisfaction of identities of type \((2,0)\) by graphs (that is, by graph algebras). With respect to the Galois connection induced by the satisfaction relation between graphs and identities, the closed sets of graphs are called graph varieties and the closed sets of identities are called equational theories of graphs. Using quasi-identities (or implications) instead of identities leads to graph quasivarieties and implicational theories of graphs.

Graph varieties were investigated and characterized in terms of graph-theoretical closure conditions in [Pös-1990]; the corresponding equational theories for graph algebras can be found in [Pös-1989]. A similar description of graph quasivarieties was provided by Pöschel and Wessel [PösWes-1987], however only for undirected graphs. The picture was completed by the following characterization of graph quasivarieties of arbitrary directed graphs.

Theorem. ([LehPös-2020]) A class of graphs is a graph quasivariety if and only if it is closed under directed unions of isomorphic copies of finite strong pointed subproducts.

In [LehMan-2020] we explictly described the graph varieties axiomatized by various identities that are of interest in algebra, such as the semimedial and medial identities.

Associative spectrum

Associativity is a well-known property of some binary operations. Many familiar operations are associative, such as addition and multiplication of numbers. However, there are many interesting operations that are not associative, such as subtraction, exponentiation, and the cross product of vectors. Formally, a binary operation \(\circ\) is associative if it satisfies the identity \(x_1 \circ (x_2 \circ x_3) \approx (x_1 \circ x_2) \circ x_3\) (the associative law).

There are several ways of measuring how far a binary operation \(\circ\) on a set \(A\) is from being associative. One such method, proposed by Csákány and Waldhauser [CsáWal-2000], is to look at how many identities that are consequences of the associative law are (not) satisfied. Any term obtained by inserting pairs of parentheses in a valid way in the string \(x_1 x_2 \dots x_n\) is called a bracketing of \(n\) variables. Interpreting terms in the algebra \(\mathbb{A} = (A,\circ)\), each such bracketing induces an \(n\)-ary operation on \(A\). If the operation \(\circ\) is associative, then parentheses do not matter and all bracketings of \(n\) variables induce the same term operation, but for arbitrary \(\circ\) we may get different operations. In fact, we might get as many different \(n\)-ary operations as there are bracketings of \(n\) variables; this number is known to be the \((n-1)\)-st Catalan number \(C_{n-1} = \frac{1}{n} \binom{2n-2}{n-1}\). Denoting by \(s_n(\mathbb{A})\) the number of different term operations induced by the bracketings of \(n\) variables on \(\mathbb{A}\), we define the associative spectrum of \(\mathbb{A}\) as the sequence \((s_n(\mathbb{A}))_{n \in \mathbb{N_{+}}}\). Thus \(1 \leq s_n(\mathbb{A}) \leq C_{n-1}\) for all \(n \in \mathbb{N}_{+}\). Intuitively, the faster the associative spectrum grows, the less associative the operation is considered. We call the operation antiassociative if \(s_n(\mathbb{A}) = C_{n-1}\) holds for all \(n \in \mathbb{N}_{+}\).

In a recent study with Waldhauser [LehWal-2021a, LehWal-2021b], we examined associative spectra of graph algebras with the help of homomorphisms of DFS trees. We classified undirected graphs according to the associatice spectra of their graph algebras; there are only three distinct possibilities: constant 1, powers of 2, and Catalan numbers. We described associative and antiassociative digraphs and determined associative spectra for certain families of digraphs, such as paths, cycles, and graphs on two vertices.

For arbitrary digraphs, the situation is considerably more complicated. We provided a necessary and sufficient condition for a graph algebra to satisfy a given bracketing identity. The condition is expressed in terms of several numerical structural parameters associated, on the one hand, with the digraph, and, on the other hand, with a pair of bracketings. This result seems a first step towards a general description of the associative spectra of graph algebras. Such a general result, however, still eludes us. We nevertheless established bounds for the possible associative spectra of graph algebras: such a spectrum is either a constant sequence bounded above by 2 or it grows exponentially. This stands in stark contrast with associative spectra of arbitrary groupoids, for which other constants and subexponential spectra are possible (see [LieWal-2009]).

Reconstruction problems

Reconstruction problems are a general class of problems concerning whether a mathematical object is uniquely determined by pieces of partial information thereon. An archetypical example of a reconstruction problem is present in a famous unproven conjecture in graph theory, the so-called reconstruction conjecture, due to Kelly [Kel-1957] and Ulam [Ula-1960], which asserts that every finite simple graph with at least three vertices is uniquely determined, up to isomorphism, by the collection of its one-vertex-deleted induced subgraphs. Analogous reconstruction problems have been formulated and studied for many other kinds of mathematical objects.

Reconstructibility of functions from identification minor

The notion of identification minor gives immediately rise to the following reconstruction problem: Is a function \(f \colon A^n \to B\) uniquely determined, up to equivalence, by the collection of its identification minors? This problem was investigated in a series of papers [Leh-2014a], [Leh-2014b], [CouLehSch-2015a], [CouLehSch-2015b] and in my habilitation thesis [Leh-2018]. Both positive and negative results about the reconstructibility of functions were obtained.

The analysis of different types of functions led us into formulating reconstruction problems for other kinds of mathematical objects and finding solutions to them. For example, term functions over a bounded distributive lattice \(\mathbf{L} = (L; {\wedge}, {\vee}, 0, 1)\) can be represented in disjunctive normal form (DNF): \[f(x_1, \dots, x_n) = \bigwedge_{S \in \mathcal{A}} \bigvee_{i \in S} x_i,\] where \(\mathcal{A}\) is an antichain in the power set lattice \((\mathcal{P}(\{1, \dots, n\}), {\subseteq})\), also known as a Sperner system. The reconstruction problem of term functions over \(\mathbf{L}\) translates into a reconstruction problem of Sperner systems. We found in [CouLehSch-2015b] several infinite families of non-reconstructible Sperner systems, which in turn translated into infinite families of non-reconstructible functions.

As an interesting by-product, one of the non-reconstructible families of Sperner systems turned out to serve also as a new example of an infinite non-reconstructible family of hypergraphs with respect to the classical reconstruction problem of hypergraphs from one-vertex-deleted subhypergraphs. Non-reconstructible families of hypergraphs had been presented earlier by Kocay [Koc-1987] and Kocay and Lui [KocLui-1988].

Reconstructibility of permutations from patterns

The problem of reconstructing a permutation from its patterns has been considered by several authors. It is known that, for \(n \geq 5\), every \(n\)-permutation is reconstructible from the multiset of its \((n-1)\)-patterns (Smith [Smi-2006], Raykova [Ray-2006]) and from its set of \((n-1)\)-patterns (Ginsburg [Gin-2007]). Raykova [Ray-2006] and Smith [Smi-2006] also considered decks (i.e., multisets) composed of \((n-k)\)-patterns for \(k \geq 1\), and they proved, for every \(k \geq 1\), the existence of natural numbers \(N_k\) such that all permutations of rank \(n \geq N_k\) are reconstructible from their multisets of \((n-k)\)-patterns, and they found upper and lower bounds for the smallest such numbers \(N_k\).

When a permutation is reconstructible, its deck contains a sufficient amount of information for uniquely determining the permutation. Nonetheless, there may be some redundancy; perhaps some permutations can be reconstructed from only a few cards. In [GouLeh-2021], we shed some light on how much information is needed for permutation reconstruction and succeeded to answer, for \(k=1\), one of the open problems posed by Ginsburg [Gin-2007]: Can we find a non-trivial function \(f_k \colon \{n \in \mathbb{N} \mid n \geq N_k \} \to \mathbb{N}\}\) so that \(f_k(n)\) is the smallest integer \(m\) such that every permutation \(\pi \in S_n\) is uniquely determined by any of its partial \((n-k)\)-decks of cardinality \(m\)? More precisely, we proved that, for \(k=1\), the function \(f_1\) is given by \(f_1(n) = \lceil n / 2 \rceil + 2\).

Reconstructibility of Young tableaux from \(k\)-minors

Monks [Mon-2009] posed the question which natural numbers \(n\) and \(k\) have the property that any standard Young tableau with \(n\) entries can be reconstructed from its set of \(k\)-minors. A \(k\)-minor of a standard Young tableau with \(n\) entries is a standard Young tableau with \(n - k\) entries obtained by deleting entries using jeu de taquin and renumbering. In [CaiLeh-2021], we took the first steps towards answering Monks’s question by completely characterizing the standard Young tableaux that can be reconstructed from their sets or multisets of \(1\)-minors. In particular, for \(n \geq 5\), any standard Young tableau with \(n\) entries can be reconstructed from its set (and thus from its multiset) of \(1\)-minors; this bound is the best possible.

Bibliography

• [AicMay-2016] E. Aichinger, P. Mayr, Finitely generated equational classes, J. Pure Appl. Algebra 220 (2016) 2816–2827. [DOI]
• [AtkBea-2001] M. D. Atkinson, R. Beals, Permutation involvement and groups, Q. J. Math. 52 (2001) 415–421. [DOI]
• [BarBulKroOpr-2019] L. Barto, J. Bulín, A. Krokhin, J. Opršal, Algebraic approach to promise constraint satisfaction, J. ACM 68 (2021) Art. 28, 66 pp. [DOI]
• [BarOprPin-2018] L. Barto, J. Opršal, M. Pinsker, The wonderland of reflections, Israel J. Math. 223 (2018) 363–398. [DOI]
• [BodKalKotRom-1969] V. G. Bodnarčuk, L. A. Kalužnin, V. N. Kotov, B. A. Romov, Galois theory for Post algebras, I, II, Kibernetika 3 (1969) 1–10, 5 (1969) 1–9 (in Russian); English translation: Cybernetics 5 (1969) 243–252, 531–539.
• [BouCouPou-2010] M. Bouaziz, M. Couceiro, M. Pouzet, Join-irreducible Boolean functions, Order 27 (2010) 261–282. [DOI]
• [CaiLeh-2021] A. J. Cain, E. Lehtonen, Reconstructing Young tableaux, J. Combin. Theory Ser. A 187 (2022) Art. 105578, 9 pp. [DOI]
• [CouFol-2009] M. Couceiro, S. Foldes, Function classes and relational constraints stable under compositions with clones, Discuss. Math. Gen. Algebra Appl. 29 (2009) 109–121. [DOI]
• [CouLeh-2009] M. Couceiro, E. Lehtonen, Generalizations of Świerczkowski’s lemma and the arity gap of finite functions, Discrete Math. 309 (2009) 5905–5912. [DOI]
• [CouLeh-2018] M. Couceiro, E. Lehtonen, Majors of functions, Order 35 (2018) 233–246. [DOI]
• [CouLeh-2024] M. Couceiro, E. Lehtonen, Stability of Boolean function classes with respect to clones of linear functions, Order 41 (2024) 15–64. [DOI] [SharedIt]
• [CouLehSch-2015a] M. Couceiro, E. Lehtonen, K. Schölzel, Set-reconstructibility of Post classes, Discrete Appl. Math. 187 (2015) 12–18. [DOI]
• [CouLehSch-2015b] M. Couceiro, E. Lehtonen, K. Schölzel, Hypomorphic Sperner systems and non-reconstructible functions, Order 32 (2015) 255–292. [DOI]
• [CouLehWal-2012] M. Couceiro, E. Lehtonen, T. Waldhauser, Decompositions of functions based on arity gap, Discrete Math. 312 (2012) 238–247. [DOI]
• [CouLehWal-2013] M. Couceiro, E. Lehtonen, T. Waldhauser, Parametrized arity gap, Order 30 (2013) 557–572. [DOI]
• [CouPou-2008] M. Couceiro, M. Pouzet, On a quasi-ordering on Boolean functions, Theoret. Comput. Sci. 396 (2008) 71–87. [DOI]
• [CsáWal-2000] B. Csákány, T. Waldhauser, Associative spectra of binary operations, Mult.-Valued Log. 5 (2000) 175–200.
• [ČupMar-1997] Ǵ. Čupona, S. Markovski, Primitive varieties of algebras, Algebra Universalis 38 (1997) 226–234. [DOI]
• [Gei-1968] D. Geiger, Closed systems of functions and predicates, Pacific J. Math. 27 (1968) 95–100. [link]
• [Gin-2007] J. Ginsburg, Determining a permutation from its set of reductions, Ars Combin. 82 (2007) 55–67.
• [GouLeh-2021] M. J. Gouveia, E. Lehtonen, Permutation reconstruction from a few large patterns, Electron. J. Combin. 28(3) (2021) #P3.41. [DOI]
• [Kel-1957] P. J. Kelly, A congruence theorem for trees, Pacific J. Math. 7 (1957) 961–968. [link]
• [Koc-1987] W. L. Kocay, A family of nonreconstructible hypergraphs, J. Combin. Theory Ser. B 42 (1987) 46–63. [DOI]
• [KocLui-1988] W. L. Kocay, Z. M. Lui, More non-reconstructible hypergraphs, Discrete Math. 72 (1988) 213–223. [DOI]
• [Leh-2006] E. Lehtonen, Descending chains and antichains of the unary, linear, and monotone subfunction relations, Order 23 (2006) 129–142. [DOI]
• [Leh-2014a] E. Lehtonen, Reconstructing multisets over commutative groupoids and affine functions over nonassociative semirings, Internat. J. Algebra Comput. 24 (2014) 11–31. [DOI]
• [Leh-2014b] E. Lehtonen, Totally symmetric functions are reconstructible from identification minors, Electron. J. Combin. 21(2) (2014) #P2.6. [DOI]
• [Leh-2018] E. Lehtonen, Reconstruction of functions from minors, habilitation thesis, Technische Universität Dresden, Dresden, 2018. [link]
• [Leh-2020] E. Lehtonen, Permutation groups arising from pattern involvement, J. Algebraic Combin. 52 (2020) 251–298. [DOI]
• [Leh-2024] E. Lehtonen, Majority-closed minions of Boolean functions,Algebra Universalis 85 (2024) Art. 6, 48 pp. [DOI] [SharedIt]
• [Leh-2025] E. Lehtonen, Near-unanimity-closed minions of Boolean functions, Algebra Universalis 86 (2025) Art. 2, 51 pp. [DOI]
• [Leh-pre-2024a] E. Lehtonen, Clonoids of Boolean functions with a monotone or discriminator source clone, arXiv:2405.01164.
• [Leh-pre-2024b] E. Lehtonen, Clonoids of Boolean functions with essentially unary, linear, semilattice, or 0- or 1-separating source and target clones, arXiv:2412.01107.
• [LehMan-2020] E. Lehtonen, C. Manyuen, Graph varieties axiomatized by semimedial, medial, and some other groupoid identities, Discuss. Math. Gen. Algebra Appl. 40 (2020) 143–157. [DOI]
• [LehNeš-2010] E. Lehtonen, J. Nešetřil, Minors of Boolean functions with respect to clique functions and hypergraph homomorphisms, European J. Combin. 31 (2010) 1981–1995. [DOI]
• [LehPös-2017] E. Lehtonen, R. Pöschel, Permutation groups, pattern involvement, and Galois connections, Acta Sci. Math. (Szeged) 83 (2017) 355–375. [DOI]
• [LehPös-2020] E. Lehtonen, R. Pöschel, Graph quasivarieties, Acta Sci. Math. (Szeged) 86 (2020) 31–50. [DOI]
• [LehPös-2021] E. Lehtonen, R. Pöschel, Reflections and powers of multisorted minions, Algebra Universalis, 82 (2021) Art. 20. [DOI]
• [LehPösWal-2018a] E. Lehtonen, R. Pöschel, T. Waldhauser, Reflection-closed varieties of multisorted algebras and minor identities, Algebra Universalis 79 (2018) Art. 70. [DOI]
• [LehPösWal-2018b] E. Lehtonen, R. Pöschel, T. Waldhauser, Reflections on and of minor-closed classes of multisorted operations, Algebra Universalis 79 (2018) Art. 71. [DOI]
• [LehSze-2009] E. Lehtonen, Á. Szendrei, Equivalence of operations with respect to discriminator clones, Discrete Math. 309 (2009) 673–685. [DOI]
• [LehSze-2010] E. Lehtonen, Á. Szendrei, The submaximal clones on the three-element set with finitely many relative \(\mathcal{R}\)-classes, Discuss. Math. Gen. Algebra Appl. 30 (2010) 7–33. [DOI]
• [LehSze-2012] E. Lehtonen, Á. Szendrei, Partial orders induced by quasilinear clones, Contributions to General Algebra, vol. 20, Proceedings of the Salzburg Conference 2011 (AAA81), Verlag Johannes Heyn, Klagenfurt, 2012, pp. 51–84. [preprint]
• [LehWal-2019] E. Lehtonen, T. Waldhauser, Minor posets of functions as quotients of partition lattices, Order 36 (2019) 23–41. [DOI]
• [LehWal-2021a] E. Lehtonen, T. Waldhauser, Associative spectra of graph algebras I. Foundations, undirected graphs, antiassociative graphs, J. Algebraic Combin. 53 (2021) 613–638. [DOI]
• [LehWal-2021b] E. Lehtonen, T. Waldhauser, Associative spectra of graph algebras II. Satisfaction of bracketing identities, spectrum dichotomy, J. Algebraic Combin. (2021), DOI: 10.1007/s10801-021-01061-7.
• [LieWal-2009] S. Liebscher, T. Waldhauser, On associative spectra of operations, Acta Sci. Math. (Szeged) 75 (2009) 433–456. [link]
• [Mon-2009] M. Monks, The solution to the partition reconstruction problem, J. Combin. Theory Ser. A 116 (2009) 76–91. [DOI]
• [Pip-2002] N. Pippenger, Galois theory for minors of finite functions, Discrete Math. 254 (2002) 405–419. [DOI]
• [Pös-1989] R. Pöschel, The equational logic for graph algebras, Z. Math. Logik Grundlag. Math. 35 (1989) 273–282. [DOI]
• [Pös-1990] R. Pöschel, Graph algebras and graph varieties, Algebra Universalis 27 (1990) 559–577. [DOI]
• [PösWes-1987] R. Pöschel, W. Wessel, Classes of graphs definable by graph algebra identities or quasi-identities, Comment. Math. Univ. Carolin. 28 (1987) 581–592. [link]
• [Ray-2006] M. Raykova, Permutation reconstruction from minors, Electron. J. Combin. 13 (2006) #R66. [DOI]
• [Sal-1963] A. Salomaa, On essential variables of functions, especially in the algebra of logic, Ann. Acad. Sci. Fenn. Ser. A I 339 (1963) 1–11. [link]
• [Sha-1979] C. R. Shallon, Non-finitely based binary algebras derived from lattices, Ph.D. thesis, University of California, Los Angeles, 1979. [link]
• [Smi-2006] R. Smith, Permutation reconstruction, Electron. J. Combin. 13 (2006) #N11. [DOI]
• [Spa-2019] A. Sparks, On the number of clonoids, Algebra Universalis 80 (2019) Art. 53. [DOI]
• [Ula-1960] S. M. Ulam, A Collection of Mathematical Problems, Interscience Tracts in Pure and Applied Mathematics, no. 8, Interscience Publishers, New York – London, 1960.
• [Wil-1996] R. Willard, Essential arities of term operations in finite algebras, Discrete Math. 149 (1996) 239–259. [DOI]