Timeline for What is an explicit bijection in combinatorics?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 28, 2019 at 17:29 | comment | added | LSpice | @AdamP.Goucher, right, but you could take that as my argument against computability being the relevant notion here. After all, the elements of two sets in bijection can always be coded in such a way that the bijection is the identity on encodings. | |
| Feb 28, 2019 at 16:31 | comment | added | Adam P. Goucher | @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. | |
| Feb 28, 2019 at 16:25 | comment | added | LSpice | 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? | |
| Feb 25, 2019 at 13:37 | history | edited | Adam P. Goucher | CC BY-SA 4.0 |
Parentheses for clarity
|
| Feb 25, 2019 at 1:22 | comment | added | Michael Hardy | 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$ | |
| Feb 22, 2019 at 17:53 | comment | added | Martin Rubey | For the record, the solution passing the expliciticity test is mathoverflow.net/a/188298/3032 (and perhaps youtube.com/watch?v=E8AEUfgQibc) | |
| Feb 22, 2019 at 14:39 | comment | added | Fedor Petrov | 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$. | |
| Feb 22, 2019 at 11:30 | history | answered | Adam P. Goucher | CC BY-SA 4.0 |