3 contrast with other concepts edited Feb 23 at 15:05 Martin Rubey 2,88211 gold badge1616 silver badges2828 bronze badges I would say that a bijection $$\pi: A\to B$$ is explicit, if for every $$a\in A$$ the image $$\pi(a)$$ can be computed without reference to $$B$$ itself. More precisely, suppose that $$A$$ and $$B$$ are not known, but only an element $$a\in A$$, then it should still be possible to construct $$\pi(a)$$. In particular, sorting $$B$$, or iterating over $$B$$ to find a particular object, is not possible with this definition. On the other hand, this allows algorithms whose well-definedness or injectivity is not obvious from the algorithm. I think that this is in fact desirable. Let me contrast this definition with other concepts, which I believe should be orthogonal to being explicit. computational complexity: a bijection may be computable in polynomial time and memory, but still be not explicit. For example, Dyck paths of semilength $$n$$ with exactly one valley are in bijection with subsets of size $$2$$ in $$\{1,\dots,n\}$$. A non-explicit bijection which is computable in polynomial time is to fix an order on the Dyck paths, and an order on the subsets and match elements with the same index. simplicity: a bijection may be very complicated, but still be explicit. A (biased) example is Jagenteufel's bijection between Riordan paths and standard Young tableaux with three rows, whose row lengths are either all odd or all even, see Algorithm 3 in https://arxiv.org/abs/1801.03780, or Algorithm 3 in https://arxiv.org/abs/1902.03843 for a generalisation to fans of Riordan paths. Although this bijection is really complicated, it allows to deduce a refinement of the equinumeration result, that is otherwise unavailable. apparently bijective: The sweep maps on lattice paths were defined by Armstrong, Loehr and Warrington in https://arxiv.org/abs/1406.1196. It took quite a while to show that they are bijective, see Thomas and Williams https://arxiv.org/abs/1512.01483. I think that the maps were bijective already in June 2014, and did not become bijective in December 2015, but philosophy might disagree. I am sure there are also examples where the only known proof of bijectivity uses enumeration, but the map itself yields other properties. apparently well defined: Consider Prüfer's bijection between $$(n-2)$$-tuples of integers in $$\{1,\dots,n\}$$ and labelled trees on $$n$$ vertices. Although not hard to see, it is not a priori clear that given a tuple one actually obtains a tree: from the definition of the algorithm itself one might think that the result could be forest. I would say that a bijection $$\pi: A\to B$$ is explicit, if for every $$a\in A$$ the image $$\pi(a)$$ can be computed without reference to $$B$$ itself. More precisely, suppose that $$A$$ and $$B$$ are not known, but only an element $$a\in A$$, then it should still be possible to construct $$\pi(a)$$. In particular, sorting $$B$$, or iterating over $$B$$ to find a particular object, is not possible with this definition. On the other hand, this allows algorithms whose well-definedness or injectivity is not obvious from the algorithm. I think that this is in fact desirable. I would say that a bijection $$\pi: A\to B$$ is explicit, if for every $$a\in A$$ the image $$\pi(a)$$ can be computed without reference to $$B$$ itself. More precisely, suppose that $$A$$ and $$B$$ are not known, but only an element $$a\in A$$, then it should still be possible to construct $$\pi(a)$$. In particular, sorting $$B$$, or iterating over $$B$$ to find a particular object, is not possible with this definition. On the other hand, this allows algorithms whose well-definedness or injectivity is not obvious from the algorithm. I think that this is in fact desirable. Let me contrast this definition with other concepts, which I believe should be orthogonal to being explicit. computational complexity: a bijection may be computable in polynomial time and memory, but still be not explicit. For example, Dyck paths of semilength $$n$$ with exactly one valley are in bijection with subsets of size $$2$$ in $$\{1,\dots,n\}$$. A non-explicit bijection which is computable in polynomial time is to fix an order on the Dyck paths, and an order on the subsets and match elements with the same index. simplicity: a bijection may be very complicated, but still be explicit. A (biased) example is Jagenteufel's bijection between Riordan paths and standard Young tableaux with three rows, whose row lengths are either all odd or all even, see Algorithm 3 in https://arxiv.org/abs/1801.03780, or Algorithm 3 in https://arxiv.org/abs/1902.03843 for a generalisation to fans of Riordan paths. Although this bijection is really complicated, it allows to deduce a refinement of the equinumeration result, that is otherwise unavailable. apparently bijective: The sweep maps on lattice paths were defined by Armstrong, Loehr and Warrington in https://arxiv.org/abs/1406.1196. It took quite a while to show that they are bijective, see Thomas and Williams https://arxiv.org/abs/1512.01483. I think that the maps were bijective already in June 2014, and did not become bijective in December 2015, but philosophy might disagree. I am sure there are also examples where the only known proof of bijectivity uses enumeration, but the map itself yields other properties. apparently well defined: Consider Prüfer's bijection between $$(n-2)$$-tuples of integers in $$\{1,\dots,n\}$$ and labelled trees on $$n$$ vertices. Although not hard to see, it is not a priori clear that given a tuple one actually obtains a tree: from the definition of the algorithm itself one might think that the result could be forest. 2 attempt a more formal definition edited Feb 22 at 14:28 Martin Rubey 2,88211 gold badge1616 silver badges2828 bronze badges I would say that a bijection $$\pi: A\to B$$ is explicit, if for every $$a\in A$$ the image $$\pi(a)$$ can be computed without reference to $$B$$ itself. In particular More precisely, I believesuppose that one should$$A$$ and $$B$$ are not require that well-definedness or injectivity is obvious from the algorithm. Unfortunatelyknown, I am unable to make the phrase 'without reference tobut only an element $$B$$' precise. However$$a\in A$$, to illustratethen it should still be possible to construct $$\pi(a)$$. In particular, sorting $$B$$, or iterating over $$B$$ to find a particular object, is clearly not allowedpossible with this definition. On the other hand, this allows algorithms whose well-definedness or injectivity is not obvious from the algorithm. I think that this is in fact desirable.  I would say that a bijection $$\pi: A\to B$$ is explicit, if for every $$a\in A$$ the image $$\pi(a)$$ can be computed without reference to $$B$$ itself. In particular, I believe that one should not require that well-definedness or injectivity is obvious from the algorithm. Unfortunately, I am unable to make the phrase 'without reference to $$B$$' precise. However, to illustrate it, sorting $$B$$, or iterating over $$B$$ to find a particular object, is clearly not allowed. I would say that a bijection $$\pi: A\to B$$ is explicit, if for every $$a\in A$$ the image $$\pi(a)$$ can be computed without reference to $$B$$ itself. More precisely, suppose that $$A$$ and $$B$$ are not known, but only an element $$a\in A$$, then it should still be possible to construct $$\pi(a)$$. In particular, sorting $$B$$, or iterating over $$B$$ to find a particular object, is not possible with this definition. On the other hand, this allows algorithms whose well-definedness or injectivity is not obvious from the algorithm. I think that this is in fact desirable. 1 answered Feb 22 at 11:34 Martin Rubey 2,88211 gold badge1616 silver badges2828 bronze badges I would say that a bijection $$\pi: A\to B$$ is explicit, if for every $$a\in A$$ the image $$\pi(a)$$ can be computed without reference to $$B$$ itself. In particular, I believe that one should not require that well-definedness or injectivity is obvious from the algorithm. Unfortunately, I am unable to make the phrase 'without reference to $$B$$' precise. However, to illustrate it, sorting $$B$$, or iterating over $$B$$ to find a particular object, is clearly not allowed.