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 16:29 | comment | added | LSpice | Wouldn't any suggestion of the form "if one combines no more than $x$ such components … then the resulting bijection … is explicit" automatically run up against some version of the sorites paradox? (EDIT: I just saw @RussWoodroofe's comment, which I think provides a way around this; one can have a degree of explicitness without an (ha!) explicit binary cut-off.) | |
| Feb 25, 2019 at 13:57 | comment | added | Russ Woodroofe | 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. | |
| Feb 23, 2019 at 8:01 | comment | added | Andrej Bauer | I don't know if this helps you guys at all, but in the programming language community there is bidirectional programming where people design programming languages in which every algorithms is invertible by design. | |
| Feb 23, 2019 at 7:15 | comment | added | Martin Rubey | 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? | |
| Feb 23, 2019 at 7:12 | comment | added | Martin Rubey | @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. | |
| Feb 22, 2019 at 23:28 | comment | added | Timothy Chow | 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. | |
| Feb 22, 2019 at 22:47 | comment | added | Andrej Bauer | 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". | |
| Feb 22, 2019 at 21:51 | history | answered | Timothy Chow | CC BY-SA 4.0 |