42
$\begingroup$

A standard way of demonstrating that two collections of combinatorial objects have the same cardinality is to exhibit a bijection between them. Browsing through some examples (here, there, yonder) quickly reveals that combinatorialists call such bijections explicit, presumably to differentiate them from other less palpable kinds of bijections. Wikipedia speaks of the method of bijective proof.

It seems that we have here a typical example of an informal mathematical notion that is quite familiar to most mathematicians, however it is difficult to pin down a proper and satisfying mathematical definition. I asked the local combinatorialists and did not really get a good answer.

Question: What is a proper mathematical definition of an explicit bijection?

Often we ask for an explicit bijection between two families of combinatorial objects, i.e., bijections $b_n : A_n \to B_n$, one for each $n \in \mathbb{N}$. Here $(A_n)_n$ and $(B_n)_n$ are two families of combinatorial objects, parametrized by $n$. The parameter need not be a single number.

Here are some unsatisfactory answers:

  1. "A bijection is explicit if it is computable." This definition is too wide, because it allows silly algorithms that order combinatorial objects according to the layout of the sequences of bits that represent them, and use the order to establish a bijection. Bit representations typically have nothing to do with the combinatorial content of the objects under consideration.

  2. "A bijection is explicit if it can be written down as an expression." This takes us back several centuries in terms of level of mathematical abstraction, and also varies a lot depending on what expressions are allowed. We really should be looking for a combinatorially meaningful notion, not a syntactic surrogate.

  3. "A bijection is explicit if we can give a constructive proof of its existence." Well, a constructive proof certainly guarantees that a computable bijection exists, and can moreover be extracted from the proof, but this still feels too permissive. For example, we can always compose an explicit bijection so obtained with a computable automorphism of one of the sets, and still have a constructive proof. But such an automorphism could completely obfuscate the combinatorial structure of the set.

  4. "Well-order $V_\omega$ (as all combinatorial objects easily live in it) and take the first bijection under the well ordering." Only a set theorist would have such thoughts. Again, we should strive for a definition which will be accepted as natural by combinatorialists.

Let me also say that I would prefer to not generalize the question to "what is an explicit thing?" At least in combinatorics "explicit bijections" are a well-established and useful notion, whereas mathematicians in general do not posses a universally agreed upon notion of "explicit thing".

Supplemental: After having a look at Igor Pak's paper, I am somewhat convinced that computational complexity plays a certain role, but it cannot be the only answer (as Pak himself notes). For example, an explicit bijection may require factoring of numbers, which I feel most people would find unproblematic even though the computational complexity of factoring is not resolved.

$\endgroup$
  • 8
    $\begingroup$ in math.ucla.edu/~pak/papers/ICM-paper9.pdf one finds some studies on the subject. $\endgroup$ – Dima Pasechnik Feb 21 at 22:11
  • 11
    $\begingroup$ My feeling is that when one writes "We define an explicit bijection ..." one means a bijection whose computation depends only on the description of an individual object in the domain -- in particular the main dichotomy for me is between explicit and recursively defined bijections. Having said all that I'll also say that I'd be happier if "explicit bijection" were left as an informal notion! Especially since I suspect that I've been entirely inconsistent in its use. $\endgroup$ – Michael Albert Feb 21 at 22:29
  • 16
    $\begingroup$ I think this question makes a mistake about what the terminology means. Specifically, the "explicit" in "explicit bijection" isn't a property of the bijection itself. It's more like the "explicit" in "explicit nudity"; a bijection (or nudity) is explicit if we show it, rather than implying that a bijection (or nudity) must exist. The same bijection may be explicit in one proof or left implicit in another. $\endgroup$ – user2357112 Feb 22 at 5:21
  • 6
    $\begingroup$ @MonroeEskew Mathematicians like to formalize informal notions. A pay-off could be that (perhaps) down the line someone could use a formal definition to e.g. show that for some combinatorial objects of the same cardinality an explicit bijection can't be found. Who knows? I see no reason to censor the question itself. $\endgroup$ – John Coleman Feb 22 at 12:33
  • 9
    $\begingroup$ @MonroeEskew But this isn't "just for fun" -- explicit bijection is an important albeit informal notion in combinatorics. There very well might be mathematical significance in formalizing such a notion, in much the same way that e.g. defining elementary functions as (one possible) formalization of "closed form" function definitions is manifestly a mathematically fruitful definition. $\endgroup$ – John Coleman Feb 22 at 12:43
23
$\begingroup$

This is not at all intended as a complete answer to the question, but one criterion that feels important is that for a bijection $f$ to count as explicit, one shouldn't need to know in advance that there exists a bijection in order to prove that $f$ is a well-defined bijection. So for example if you order the elements of two sets $A$ and $B$ in some way that has nothing to do with why $|A|=|B|$, then you need to know that $|A|=|B|$ in order to conclude that the bijection that maps the $k$th element of $A$ to the $k$th element of $B$ is indeed a well-defined bijection.

I think this criterion rules out 1 and 4 (or would do if one could make it more formal, which might itself not be wholly easy).

$\endgroup$
  • $\begingroup$ Hmm, what about "map the $k$-th smallest element of $A$ to the $k$-th smallest element of $B$ or to the largest one if there is no $k$-th smallest one"? I am being somewhat tongue-in-cheek here, as we are clearly looking for a rule to follow in spirit rather than in letter. On the other hand, if we take this idea too far in the other direction, then a bijection $f : A \to B$ whose bijectivity is only proven using the pigeonhole principle (i.e., by showing that it is injective or surjective, and that $\left|A\right| = \left|B\right|$) should not count as explicit either. (Perhaps rightfully!) $\endgroup$ – darij grinberg Feb 21 at 22:25
  • 1
    $\begingroup$ Yes, this is definitely an important aspect of the question. But note that we already have trouble formally expressing "one shouldn't need to know in advance that there exists a bijection". Given a proof, what does it mean that the proof "first proves existence"? $\endgroup$ – Andrej Bauer Feb 22 at 7:13
  • 2
    $\begingroup$ Indeed -- that is the difficulty I alluded to in my final sentence. $\endgroup$ – gowers Feb 22 at 7:28
  • 2
    $\begingroup$ So for example, the map $V \to V^{**}$, $v \mapsto (\phi \mapsto \phi(v))$, is not explicit? (It goes without saying, I'm not a logician or a combinatorist, so maybe I'm being hare-brained.) $\endgroup$ – Najib Idrissi Feb 22 at 13:41
  • 2
    $\begingroup$ I always imagined that an explicit bijection would have an explicit inverse, but maybe I am wrong. $\endgroup$ – Andrej Bauer Feb 22 at 22:41
17
$\begingroup$

One criterion not mentioned yet is naturality in the categorical sense, which can also be phrased as equivariance with respect to permutation actions. This approach has been extensively developed by André Joyal and others, under the name of combinatorial species.

In almost all natural examples (I’m tempted to remove the “almost”), the sets $A_n$ and $B_n$ aren’t just $\mathbb{N}$-indexed families of sets; they also come with natural permutation actions, with $\Sigma_n$ acting on $A_n$ and $B_n$. Equivalently, $A_\bullet$ and $B_\bullet$ can be seen as functors on the category $\mathrm{FinSet}_{\cong}$ of finite sets and isomorphisms; this representation is often clearest to work with. E.g. if $A_n$ is “finite trees with $n$ leaves”, one can generalise it to a functor on $\mathrm{FinSet}_{\cong}$ by taking $A_X$ to be “finite trees with leaves labelled by $X$”; an isomorphism $\varphi : X \to Y$ gives an action $A_X \to A_Y$ by relabelling leaves.

One can then require the functions $f_n$ to be natural, in the categorical sense, with respect to this functoriality. That is, for an isomorphism $\varphi : X \to Y$ of finite sets, and $a \in A_X$, one should have $f_Y(\varphi \cdot x) = \varphi \cdot (f_X a)$. In terms of permutation actions, this is equivariance: $f_n(\sigma \cdot x) = \sigma \cdot f_n(x)$.

The effect of this, roughly, is to rule out constructions that involve arbitrary or non-uniform choices at any stage. I think all examples that would traditionally be considered “natural” or “canonical” by combinatorialists are natural in this or some closely related sense — I’d be very interested to see a counterexample to that. On the other hand, one can produce contrived examples that are natural in this sense without being “natural”: e.g. take some example with two different natural bijections $f$, $g$, and define a new one by using $f$ for even $n$, and $g$ for odd $n$.

Comparing to the other criteria suggested: this one is pretty much orthogonal to computational complexity. It’s a bit linked to logical constructivity: there are metatheorems saying that anything definable in certain constructive logics must be natural in this sense.

$\endgroup$
  • 5
    $\begingroup$ The bijection between permutations and linear orders is not natural in this sense, but I do think it should be called explicit. $\endgroup$ – Martin Rubey Feb 22 at 12:13
  • 2
    $\begingroup$ This is exercise 1.1.10 in the book by Bergeron, Labelle and Leroux: the natural action of the symmetric group $\mathfrak S_n$ on linear orders of $\{1,\dots,n\}$ has one orbit, whereas that the natural action of the symmetric group $\mathfrak S_n$ on permutations of $\{1,\dots,n\}$ has as orbits the conjugacy classes. $\endgroup$ – Martin Rubey Feb 22 at 13:49
  • 3
    $\begingroup$ Martin Rubey: Good point, that’s a very elementary example that’s not natural in the sense I stated. It is still natural when stated in the right way — writing $L$ and $P$ for the species of linear orders and permutations respectively, we have $L \not \cong P$, but the standard bijection is natural as a bijection $L \times L \cong L \times P$ over $L$, which can be seen as an $L$-parametrised natural bijection $L \cong P$. But yes, it shows that I overstated the claim of ubiquity; I’ll edit the answer. $\endgroup$ – Peter LeFanu Lumsdaine Feb 22 at 13:59
  • 11
    $\begingroup$ I'm afraid that the assumption of having a symmetric group action on $A_n$ and $B_n$ is also rather demanding. There are plenty of very beautiful natural bijections between various kinds of integer partitions, and there is no action in sight. An example might be Sylvester's bijection, see Igor Pak's slides mentioned in the question. $\endgroup$ – Martin Rubey Feb 22 at 14:22
  • 1
    $\begingroup$ Whether or not this idea pans out, category theory is a good example of how questions of this type can be fruitful. Saunders Mac Lane said that he invented category theory to study natural transformations, and you can find usage of phrases like "natural transformation" and "natural isomorphism" prior to the original papers in category theory in the early 40s. The notion of "natural" in abstract algebra prior to category theory must have been an informal one. Category theory provided a way to formalize it. $\endgroup$ – John Coleman Feb 22 at 15:04
11
$\begingroup$

This should perhaps be a comment on the answer by Peter LeFanu Lumsdaine, but it's too long and might be relevant in connection with other answers as well. Long ago, Bruce Sagan and I wrote a paper,

Bijective proofs of two broken circuit theorems. J. Graph Theory 10 (1986), no. 1, 15–21,

in which we explicitly claimed, already in the title, to give bijective proofs. As far as I know, no one has yet objected to this claim, so I'll assume, in this answer, that the proofs given there are considered bijective. (Non-bijective proofs of the same results were known much earlier.)

Each of our results exhibits a bijection between two sets, say $A_G$ and $B_G$, associated to a finite graph $G$. As already hinted in the title, the definitions of these sets involve the notion of "broken circuit". That notion, in turn, depends on a linear ordering of the set of edges of $G$. So the $G$ subscript in $A_G$ and $B_G$ should be understood as referring not just to the graph $G$ but to the graph together with such an ordering.

Unfortunately, a finite graph-with-edge-ordering has no nontrivial automorphisms except in some trivial cases. In fact (again excepting trivial situations), a linear ordering of the edges is enough information to uniquely determine, in a purely combinatorial way, linear orderings of the finite sets $A_G$ and $B_G$. So we could, with the same information (and the same naturality) as in our construction, have defined the bijection between $A_G$ and $B_G$ that preserves the linear orderings. Yet no combinatorialist would call that a bijective proof.

$\endgroup$
11
$\begingroup$

Here's an example (credit: Paul Russell) of the sort of bijection you want to rule out.

Question: Find an explicit bijection $f$ between the size-$k$ and size-$(k + 1)$ subsets of $\{1, 2, \dots, 2k+1\}$, such that $x \subset f(x)$ for all $x$.

Answer: Consider the bipartite graph with a vertex class $X$ for the size-$k$ subsets and a vertex class $Y$ for the size-$(k + 1)$ subsets; let edges $x, y$ denote $x \subset y$. The graph is regular, so a matching exists by Hall. Take the lexicographically first such matching (represented as a binary adjacency matrix).

If you try to rule this out by stipulating 'polynomial time' in your definition of explicit, then Russell's construction can be modified by replacing the last sentence with:

"Apply the Hopcroft-Karp algorithm to the initially empty matching"

Another attempt to rule out Russell's construction is to disallow someone from mentioning 'the set of all matchings', such as by type-theoretically restricting the answer to only mention sets of integers. But this approach doesn't work either, because finite sets can be encoded as integers.

Gowers' answer would rule this out if it could be made precise: by the time we invoke Hall, we know a matching exists. But if we didn't know about Hall's marriage theorem and avoided proving it until after applying the Hopcroft-Karp algorithm, we could 'cheat' the Gowers test. Also, a proof could be obfuscated, IOCCC-style, to hide the part that proves the existence of at least one matching.

What would rule out the Russell construction, whilst allowing the genuine explicit construction, is to stipulate that the bijection is computable with polynomial memory as a function of the description length of the individual objects being bijected: the full bipartite graph is exponential in $k$, whereas the objects (sets of integers) are expressible in $O(k \log k)$ symbols.

I'm going to suggest this definition unless anyone can provide a non-contrived example of an explicit combinatorial bijection that fails my test.

$\endgroup$
  • 1
    $\begingroup$ As for me, "the explicit regular bipartite graph with parts $A$ and $B$" is in general no worse than "the explicit bijection between $A$ and $B$". Analogously, the explicit graph on the ground set $V$ with odd degrees is no worse proof that $|V|$ is even than the coupling of vertices of $V$. $\endgroup$ – Fedor Petrov Feb 22 at 14:39
  • 1
    $\begingroup$ For the record, the solution passing the expliciticity test is mathoverflow.net/a/188298/3032 (and perhaps youtube.com/watch?v=E8AEUfgQibc) $\endgroup$ – Martin Rubey Feb 22 at 17:53
  • 1
    $\begingroup$ You wrote: "Consider the bipartite graph with a vertex class $X$ for the size-$k$ subsets and a vertex class $Y$ for the size-$k + 1$ subsets". It took me 10 seconds to realize that you meant the members of $X$ are the size-$k$ subsets and those of $Y$ are the size-$(k+1)$ subsets. $\qquad$ $\endgroup$ – Michael Hardy Feb 25 at 1:22
  • $\begingroup$ Surely "the description length of the individual objects being bijected" depends so much on the encoding that it shouldn't occur in a formal definition? $\endgroup$ – LSpice Feb 28 at 16:25
  • $\begingroup$ @LSpice It does depend on the encoding, yes, but if two encoding schemes are such that one is only polynomially more inefficient than the other, then it doesn't affect the definition of 'explicit bijection'. Also, any definition which includes 'computable' requires that the sets be encoded in some way. $\endgroup$ – Adam P. Goucher Feb 28 at 16:31
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I wonder whether this is essentially the same as @Adam P. Goucher's answer! $\endgroup$ – Martin Rubey Feb 22 at 14:57
  • $\begingroup$ (as my first example shows, it is not the same) $\endgroup$ – Martin Rubey Feb 23 at 17:09
6
$\begingroup$

I would like to adopt a slightly contrarian viewpoint:

There is no formal mathematical definition of "explicit bijection."

Of course, I can't formally prove this assertion, but I would say that the reason you're having trouble finding a satisfactory formal definition is precisely because there isn't one.

A similar issue comes up in the Razborov–Rudich theory of natural proofs. Quoting from their paper:

Note that the definition of a natural proof, unlike that of a natural combinatorial property, is not precise. This is because while the notion of a property being explicitly defined in a journal paper is perfectly clear to the working mathematician, it is a bit slippery to formalize. This lack of precision will not affect the precision of our general statements about natural proofs because they will appear only in the form "there exists (no) natural proof…", and should be understood as equivalent to "there exists (no) natural combinatorial property $C_n$…"

Taking a cue from the above, I think that what may be more productive than trying to pin down an exact definition of an explicit bijection is finding sufficient conditions for being an explicit bijection. I say this because I have a secret agenda: performing automated searches for explicit bijections. For this purpose, I think it would be useful to compile a list of "atomic" components of an explicit bijection and say that if one combines no more than $x$ such components in certain specified ways, then the resulting bijection (or map, if we don't know in advance that it is bijective) is explicit.

By the way, here's an analogous issue from recreational mathematics. What does it mean to say that a Sudoku puzzle (let's assume that it has a unique solution) can be "solved without guessing"? I don't think that there is a canonical answer to this question, because what looks like guessing to you or me might just be a "standard trick" to a sufficiently powerful brain. On the other hand, it is possible to compile a specific long list of known tricks, and then you can automate the generation of "Sudokus solvable without guessing."

$\endgroup$
  • $\begingroup$ Of course a sufficiently useful sufficient condition would already be quite an accomplishment. I never imagined we could come up with a formal definition that would cover all the corners and make everyone happy. Regarding Sudoku, I think it's something like: "using these five simple strategies for making the next step (the ones that normal humans use) we cannot get stuck in whatever way we use them". $\endgroup$ – Andrej Bauer Feb 22 at 22:47
  • 1
    $\begingroup$ The most interesting idea I've seen for Sudoku is Wei-Hwa Huang's "Sledgehammer": onigame.livejournal.com/20626.html I think that for combinatorics, one would want to do something similar. Start by defining the two types of combinatorial data structures that you want to biject. Then specify a short list of available atomic operations. It's similar to defining an algorithm except that the point is to avoid too much generality. This is tough to do, at least psychologically, since mathematicians have a conditioned reflex to generalize. $\endgroup$ – Timothy Chow Feb 22 at 23:28
  • $\begingroup$ @TimothyChow: concerning (semi)automated search for bijections, my biggest obstacle is currently that I need a definition for "simplicity" of a map. A requirement is that the simplicity can be determined for a given algorithm. Evidently, it should distinguish some simple maps from not so simple ones, eg. inverse of a permutation should be simpler than Foata's map findstat.org/Mp00067. I would prefer a definition that depends only on the map, and not the algorithm. $\endgroup$ – Martin Rubey Feb 23 at 7:12
  • $\begingroup$ Of course, computational complexity (say, worst case among objects of a given size) comes to mind, but this seems both hard to determine in praxis, and does not seem to distinguish many maps. In fact, what is the complexity of Foata's map? $\endgroup$ – Martin Rubey Feb 23 at 7:15
  • 2
    $\begingroup$ Does it make sense to talk about one bijection being more explicit than another? I'm of the opinion that it does, and that this supports @TimothyChow's position. $\endgroup$ – Russ Woodroofe Feb 25 at 13:57
2
$\begingroup$

My suggestion has quite some overlap with other comments and also @gowers answer:

Let $A$, $B$ be two sets. An explicit bijection between $A$ and $B$ is a deterministic algorithm taking elements of $A$ as input and for which outputs are elements of $B$, such that an analysis of the algorithm yield its bijectivity.

Several notes:

  • In most cases I have been looking at, the sets $A$ and $B$ were finite.

  • A typical way of satisfying this criterion is to provide two deterministic algorithms $A \to B$ and $B \to A$ and showing that they are inverses of each other. Or showing that both are injective. I would also call this "explicit" though one might need to slightly reword to include this situation.

  • I did not include anything about complexity of the algorithm because I do not think its actual computation time is relevant for it being "explicit".

  • I have often seen the following relaxation, namely that one knows already that $|A| = |B|$, and only deduces injectivity or surjectivity from the algorithm. The problem with this relaxation is that it would allow just listing the elements of both sets...

$\endgroup$
  • $\begingroup$ I don't see how this works with, say, A and B being two isomorphic finite groups - then certainly there is an algorithm giving a bijection, but it would be in general very ugly. An example of this would be arxiv.org/abs/1405.0113 - it's not something one would call explicit... $\endgroup$ – Dima Pasechnik Feb 22 at 9:18
  • 5
    $\begingroup$ I disagree, because there are explicit bijections, which are beautiful, but bijectivity was very hard to prove or only follows because one knows for different reasons that the sets in question have the same cardinality. $\endgroup$ – Martin Rubey Feb 22 at 9:37
  • $\begingroup$ I think this falls under my first counter-example. But more importantly, how do you precisely define "such that an analysis of the algoithm yields its bijectivity"? $\endgroup$ – Andrej Bauer Feb 22 at 13:42
  • $\begingroup$ If you can't prove that an algorithm implements a bijection, it just means that you can't prove that you have an explicit bijection. I don't think it has anything to do with the definition of an explicit bijection. $\endgroup$ – Brendan McKay Feb 22 at 22:58

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.