What is an explicit bijection in combinatorics? - MathOverflowmost recent 30 from mathoverflow.net2019-09-19T01:00:17Zhttps://mathoverflow.net/feeds/question/323779https://creativecommons.org/licenses/by-sa/4.0/rdfhttps://mathoverflow.net/q/32377943What is an explicit bijection in combinatorics?Andrej Bauerhttps://mathoverflow.net/users/11762019-02-21T21:44:53Z2019-02-25T13:37:59Z
<p>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 (<a href="https://mathoverflow.net/questions/769/exhibit-an-explicit-bijection-between-irreducible-polynomials-over-finite-fields">here</a>, <a href="https://math.stackexchange.com/questions/66221/explicit-bijection-between-ordered-trees-with-n1-vertices-and-binary-trees-wi">there</a>, <a href="http://www-math.mit.edu/~rstan/bij.pdf" rel="noreferrer">yonder</a>) quickly reveals that combinatorialists call such bijections <em>explicit</em>, presumably to differentiate them from other less palpable kinds of bijections. Wikipedia speaks of the method of <a href="https://en.wikipedia.org/wiki/Bijective_proof" rel="noreferrer">bijective proof</a>.</p>
<p>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.</p>
<p><strong>Question:</strong> <em>What is a proper mathematical definition of an explicit bijection?</em></p>
<p>Often we ask for an explicit bijection between two <em>families</em> of combinatorial objects, i.e., bijections <span class="math-container">$b_n : A_n \to B_n$</span>, one for each <span class="math-container">$n \in \mathbb{N}$</span>. Here <span class="math-container">$(A_n)_n$</span> and <span class="math-container">$(B_n)_n$</span> are two families of combinatorial objects, parametrized by <span class="math-container">$n$</span>. The parameter need not be a single number.</p>
<p>Here are some <em>unsatisfactory</em> answers:</p>
<ol>
<li><p><em>"A bijection is explicit if it is computable."</em> 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.</p></li>
<li><p><em>"A bijection is explicit if it can be written down as an expression."</em> 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.</p></li>
<li><p><em>"A bijection is explicit if we can give a constructive proof of its existence."</em> 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.</p></li>
<li><p>"Well-order <span class="math-container">$V_\omega$</span> (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.</p></li>
</ol>
<p>Let me also say that I would prefer to <em>not</em> 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".</p>
<p><strong>Supplemental:</strong> After having a look at Igor Pak's <a href="http://www.math.ucla.edu/~pak/papers/ICM-paper9.pdf" rel="noreferrer">paper</a>, 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.</p>
https://mathoverflow.net/questions/323779/-/323783#32378325Answer by gowers for What is an explicit bijection in combinatorics?gowershttps://mathoverflow.net/users/14592019-02-21T22:18:07Z2019-02-21T22:50:46Z<p>This is not at all intended as a complete answer to the question, but one criterion that feels important is that for a bijection <span class="math-container">$f$</span> to count as explicit, one shouldn't need to know in advance that there exists a bijection in order to prove that <span class="math-container">$f$</span> is a well-defined bijection. So for example if you order the elements of two sets <span class="math-container">$A$</span> and <span class="math-container">$B$</span> in some way that has nothing to do with why <span class="math-container">$|A|=|B|$</span>, then you need to know that <span class="math-container">$|A|=|B|$</span> in order to conclude that the bijection that maps the <span class="math-container">$k$</span>th element of <span class="math-container">$A$</span> to the <span class="math-container">$k$</span>th element of <span class="math-container">$B$</span> is indeed a well-defined bijection.</p>
<p>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). </p>
https://mathoverflow.net/questions/323779/-/323813#3238132Answer by Christian Stump for What is an explicit bijection in combinatorics?Christian Stumphttps://mathoverflow.net/users/212912019-02-22T08:46:34Z2019-02-22T08:57:30Z<p>My suggestion has quite some overlap with other comments and also @gowers answer:</p>
<p>Let <span class="math-container">$A$</span>, <span class="math-container">$B$</span> be two sets. An <strong>explicit bijection</strong> between <span class="math-container">$A$</span> and <span class="math-container">$B$</span> is a deterministic algorithm taking elements of <span class="math-container">$A$</span> as input and for which outputs are elements of <span class="math-container">$B$</span>, such that an analysis of the algorithm yield its bijectivity.</p>
<p>Several notes:</p>
<ul>
<li><p>In most cases I have been looking at, the sets <span class="math-container">$A$</span> and <span class="math-container">$B$</span> were finite.</p></li>
<li><p>A typical way of satisfying this criterion is to provide two deterministic algorithms <span class="math-container">$A \to B$</span> and <span class="math-container">$B \to A$</span> 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.</p></li>
<li><p>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".</p></li>
<li><p>I have often seen the following relaxation, namely that one knows already that <span class="math-container">$|A| = |B|$</span>, 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...</p></li>
</ul>
https://mathoverflow.net/questions/323779/-/323826#32382612Answer by Adam P. Goucher for What is an explicit bijection in combinatorics?Adam P. Goucherhttps://mathoverflow.net/users/395212019-02-22T11:30:51Z2019-02-25T13:37:59Z<p>Here's an example (credit: Paul Russell) of the sort of bijection you want to rule out.</p>
<p>Question: Find an explicit bijection <span class="math-container">$f$</span> between the size-<span class="math-container">$k$</span> and size-<span class="math-container">$(k + 1)$</span> subsets of <span class="math-container">$\{1, 2, \dots, 2k+1\}$</span>, such that <span class="math-container">$x \subset f(x)$</span> for all <span class="math-container">$x$</span>.</p>
<p>Answer: Consider the bipartite graph with a vertex class <span class="math-container">$X$</span> for the size-<span class="math-container">$k$</span> subsets and a vertex class <span class="math-container">$Y$</span> for the size-<span class="math-container">$(k + 1)$</span> subsets; let edges <span class="math-container">$x, y$</span> denote <span class="math-container">$x \subset y$</span>. The graph is regular, so a matching exists by Hall. Take the lexicographically first such matching (represented as a binary adjacency matrix).</p>
<p>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:</p>
<p>"Apply the Hopcroft-Karp algorithm to the initially empty matching"</p>
<p>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.</p>
<p>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.</p>
<p>What <em>would</em> 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 <span class="math-container">$k$</span>, whereas the objects (sets of integers) are expressible in <span class="math-container">$O(k \log k)$</span> symbols.</p>
<p>I'm going to suggest this definition unless anyone can provide a non-contrived example of an explicit combinatorial bijection that fails my test.</p>
https://mathoverflow.net/questions/323779/-/323827#3238278Answer by Martin Rubey for What is an explicit bijection in combinatorics?Martin Rubeyhttps://mathoverflow.net/users/30322019-02-22T11:34:10Z2019-02-23T15:05:34Z<p>I would say that a bijection <span class="math-container">$\pi: A\to B$</span> is explicit, if for every <span class="math-container">$a\in A$</span> the image <span class="math-container">$\pi(a)$</span> can be computed without reference to <span class="math-container">$B$</span> itself. More precisely, suppose that <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are not known, but only an element <span class="math-container">$a\in A$</span>, then it should still be possible to construct <span class="math-container">$\pi(a)$</span>.</p>
<p>In particular, sorting <span class="math-container">$B$</span>, or iterating over <span class="math-container">$B$</span> to find a particular object, is not possible with this definition.</p>
<p>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. </p>
<p>Let me contrast this definition with other concepts, which I believe
should be orthogonal to being explicit.</p>
<ul>
<li><p>computational complexity: a bijection may be computable in
polynomial time and memory, but still be not explicit.</p>
<p>For example, Dyck paths of semilength <span class="math-container">$n$</span> with exactly one valley are
in bijection with subsets of size <span class="math-container">$2$</span> in <span class="math-container">$\{1,\dots,n\}$</span>. 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.</p></li>
<li><p>simplicity: a bijection may be very complicated, but still be
explicit.</p>
<p>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
<a href="https://arxiv.org/abs/1801.03780" rel="noreferrer">https://arxiv.org/abs/1801.03780</a>, or Algorithm 3 in
<a href="https://arxiv.org/abs/1902.03843" rel="noreferrer">https://arxiv.org/abs/1902.03843</a> for a generalisation to fans of
Riordan paths.</p>
<p>Although this bijection is really complicated, it allows to deduce a
refinement of the equinumeration result, that is otherwise
unavailable.</p></li>
<li><p>apparently bijective:</p>
<p>The sweep maps on lattice paths were defined by Armstrong, Loehr and
Warrington in <a href="https://arxiv.org/abs/1406.1196" rel="noreferrer">https://arxiv.org/abs/1406.1196</a>. It took quite a while
to show that they are bijective, see Thomas and Williams
<a href="https://arxiv.org/abs/1512.01483" rel="noreferrer">https://arxiv.org/abs/1512.01483</a>. I think that the maps were
bijective already in June 2014, and did not become bijective in
December 2015, but philosophy might disagree.</p>
<p>I am sure there are also examples where the only known proof of bijectivity uses enumeration, but the map itself yields other properties.</p></li>
<li><p>apparently well defined:</p>
<p>Consider <a href="https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence" rel="noreferrer">Prüfer's bijection</a> between <span class="math-container">$(n-2)$</span>-tuples of integers in
<span class="math-container">$\{1,\dots,n\}$</span> and labelled trees on <span class="math-container">$n$</span> 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.</p></li>
</ul>
https://mathoverflow.net/questions/323779/-/323832#32383218Answer by Peter LeFanu Lumsdaine for What is an explicit bijection in combinatorics?Peter LeFanu Lumsdainehttps://mathoverflow.net/users/22732019-02-22T12:06:24Z2019-02-22T15:05:41Z<p>One criterion not mentioned yet is <strong>naturality in the categorical sense</strong>, which can also be phrased as <strong>equivariance with respect to permutation actions</strong>. This approach has been extensively developed by André Joyal and others, under the name of <em>combinatorial species</em>.</p>
<p>In almost all natural examples (I’m tempted to remove the “almost”), the sets <span class="math-container">$A_n$</span> and <span class="math-container">$B_n$</span> aren’t just <span class="math-container">$\mathbb{N}$</span>-indexed families of sets; they also come with natural permutation actions, with <span class="math-container">$\Sigma_n$</span> acting on <span class="math-container">$A_n$</span> and <span class="math-container">$B_n$</span>. Equivalently, <span class="math-container">$A_\bullet$</span> and <span class="math-container">$B_\bullet$</span> can be seen as functors on the category <span class="math-container">$\mathrm{FinSet}_{\cong}$</span> of finite sets and isomorphisms; this representation is often clearest to work with. E.g. if <span class="math-container">$A_n$</span> is “finite trees with <span class="math-container">$n$</span> leaves”, one can generalise it to a functor on <span class="math-container">$\mathrm{FinSet}_{\cong}$</span> by taking <span class="math-container">$A_X$</span> to be “finite trees with leaves labelled by <span class="math-container">$X$</span>”; an isomorphism <span class="math-container">$\varphi : X \to Y$</span> gives an action <span class="math-container">$A_X \to A_Y$</span> by relabelling leaves.</p>
<p>One can then require the functions <span class="math-container">$f_n$</span> to be natural, in the categorical sense, with respect to this functoriality. That is, for an isomorphism <span class="math-container">$\varphi : X \to Y$</span> of finite sets, and <span class="math-container">$a \in A_X$</span>, one should have <span class="math-container">$f_Y(\varphi \cdot x) = \varphi \cdot (f_X a)$</span>. In terms of permutation actions, this is equivariance: <span class="math-container">$f_n(\sigma \cdot x) = \sigma \cdot f_n(x)$</span>.</p>
<p>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 <span class="math-container">$f$</span>, <span class="math-container">$g$</span>, and define a new one by using <span class="math-container">$f$</span> for even <span class="math-container">$n$</span>, and <span class="math-container">$g$</span> for odd <span class="math-container">$n$</span>.</p>
<p>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.</p>
https://mathoverflow.net/questions/323779/-/323836#32383611Answer by Andreas Blass for What is an explicit bijection in combinatorics?Andreas Blasshttps://mathoverflow.net/users/67942019-02-22T13:57:07Z2019-02-22T13:57:07Z<p>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,</p>
<p>Bijective proofs of two broken circuit theorems.
J. Graph Theory 10 (1986), no. 1, 15–21,</p>
<p>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.) </p>
<p>Each of our results exhibits a bijection between two sets, say <span class="math-container">$A_G$</span> and <span class="math-container">$B_G$</span>, associated to a finite graph <span class="math-container">$G$</span>. 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 <span class="math-container">$G$</span>. So the <span class="math-container">$G$</span> subscript in <span class="math-container">$A_G$</span> and <span class="math-container">$B_G$</span> should be understood as referring not just to the graph <span class="math-container">$G$</span> but to the graph together with such an ordering. </p>
<p>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 <span class="math-container">$A_G$</span> and <span class="math-container">$B_G$</span>. So we could, with the same information (and the same naturality) as in our construction, have defined the bijection between <span class="math-container">$A_G$</span> and <span class="math-container">$B_G$</span> that preserves the linear orderings. Yet no combinatorialist would call that a bijective proof.</p>
https://mathoverflow.net/questions/323779/-/323875#3238756Answer by Timothy Chow for What is an explicit bijection in combinatorics?Timothy Chowhttps://mathoverflow.net/users/31062019-02-22T21:51:35Z2019-02-22T21:51:35Z<p>I would like to adopt a slightly contrarian viewpoint:</p>
<blockquote>
<p>There is no formal mathematical definition of "explicit bijection."</p>
</blockquote>
<p>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.</p>
<p>A similar issue comes up in the Razborov–Rudich theory of <a href="https://www.karlin.mff.cuni.cz/~krajicek/rr.pdf" rel="noreferrer">natural proofs</a>. Quoting from their paper:</p>
<blockquote>
<p>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 <span class="math-container">$C_n$</span>…"</p>
</blockquote>
<p>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 <b>sufficient</b> conditions for being an explicit bijection. I say this because I have a secret agenda: performing <a href="https://mathoverflow.net/questions/288051/automated-search-for-bijective-proofs">automated searches for explicit bijections</a>.
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 <span class="math-container">$x$</span> 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.</p>
<p>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."</p>